COMP 4030/6030 Design/Analysis of Algorithms (Spring 2020)

Lectures: Tu, Th : 9:40 - 11:05 AM DH 124

Textbook

Algorithms by Dasgupta, Papadimitriou and Vazirani. I will be using the online, freely available, version of the book.

Instructor Information

Name: Nirman Kumar
Office: Dunn Hall 307
Phone: (901) 678-3135
Office Hours : F 10-11 AM
Home page : http://www.cs.memphis.edu/~nkumar/

TA's

Anik Khan (akhan9@memphis.edu): Office hours, T 12-1 PM, DH 201. Murshida Rahman Mouree(mmouree@memphis.edu): Office hours, M 2:30-3:30, DH 314.

Course Description

Basics of algorithm analysis. Sorting/Searching algorithms, data structures, graph algorithms, recursion and dynamic programming, greedy algorithms, optionally some special topics (ex. amortized analysis, string matching, computational geometry, linear programming).


See the Course Syllabus here.

Schedule (Tentative)

Date Item Relevant link
Tu Jan 21st Intro, algorithm analysis Ch. 0
Th Jan 23rd Class cancelled
Tu Jan 28th Intro, Sorting alg, analysis contd., and HW1 Ch 0, and HW1
Th Jan 30th Python intro. Python tutorial
Tu Feb 4th Arithmetic algorithms, HW1 due and HW2 Ch. 1, and HW2
Th Feb 6th Divide and conquer Ch. 2
Tu Feb 11th Divide and conquer contd. HW2 due and HW3 Ch. 2, and HW3
Th Feb 13th Divide and conquer contd. Ch. 2
Tu Feb 18th Divide and conquer contd. HW3 due and HW4 Ch. 2 and HW4
Th Feb 20th Graph decompositions Ch. 3
Tu Feb 25th Graph decompositions contd. , HW4 due Ch. 3
Th Feb 27th Graph decompositions contd. Ch. 3
Tu Mar 3rd Graph decompositions wrap-up Ch. 4
Th Mar 5th Mid-term exam
Tu Mar 10th No class - Spring Break!
Th Mar 12th No class - Spring Break!
Tu Mar 17th No class - Spring break extended (COVID-19)
Th Mar 19th No class - Spring break extended (COVID-19)
Tu Mar 24th Paths in graphs and HW5 Ch. 4, and HW5
Th Mar 26th Paths in graphs contd. Ch. 4
Tu Mar 31st Greedy algorithms and HW5 due and HW6 Ch. 5 and HW6
Th Apr 2nd Greedy algorithms contd. Ch. 5
Tu Apr 7th Greedy algorithms contd., HW6 due and HW7 Ch. 5 and HW7
Th Apr 9th Dynamic Programming Ch. 6
Tu Apr 14th Dynamic Prog. contd., HW7 due and HW8 Ch. 6 and HW8
Th Apr 16th Dynamic Prog. contd. Ch. 6
Tu Apr 21st LP/flows, HW8 due and HW9 Ch. 7 and HW9
Th Apr 23th LP/flows contd. Ch. 7
Tu Apr 28th LP/flows contd., HW9 due and HW10 [due May 2nd] Ch. 7 and HW10
Tu May 5th FINAL EXAM (10:30 AM - 12:30 PM)