CS 6043 Design and Analysis of Algorithms II (Fall 2019)


Catalog Description

This course covers techniques in advanced design and analysis of algorithms. Topics: Amortized analysis of algorithms. Advanced data structures: binomial heaps, Fibonacci heaps, data structures for disjoint sets, analysis of union by rank with path compression. Graph algorithms: maximum flow, matching algorithms. Randomized algorithms. Theory of NP-completeness and approaches to finding (approximate) solutions to NP-complete problems. Selected additional topics that may vary.

Prerequisites:

CS6033 (Design and Analysis of Algorithms I) or equivalent. Familiarity with basic sorting/searching algorithms and data structures, recurrence relations, and asymptotic notation will be assumed.


Regularly check the following for the latest updates:

Announcement (12/12/19):
There will be a recitation section tomorrow (Friday 12/13) during 2pm--4pm for the TA to present the HW4 solutions, in the usual location (Conference Room 834 (8th Floor) of 370 Jay Street).

Announcement (11/21/19):
There will be a recitation section tomorrow (Friday 11/22) during 2pm--4pm for the TA to present the HW3 solutions, in the usual location (Conference Room 834 (8th Floor) of 370 Jay Street).

Announcement (10/20/19):
1. HW2 Q.5 has been revised to clarify the question. Please download HW2 again to get the new version --- refresh your browser at this web site first, then click on HW2 below to download. (The only revision is on p.4, starting in line 6, by adding
"(Note: If there is nothing left to return... returns `nothing'.)".)

2. There will be a recitation section on the coming Friday 10/25 during 2pm--4pm (note that there will be 2 hours for each recitation section from now on) for the TA to present the HW2 solutions, in the usual location (Conference Room 834 (8th Floor) of 370 Jay Street).

Announcement (10/9/19):
1. There will be a recitation section on the coming Friday 10/11 during 2pm--3:30pm (note the slight time change) at the Conference Room 834 (8th Floor) of 370 Jay Street. The TA will present the HW1 solutions.

2. I will be out of town in the week of Oct. 21--25, so there will be no class in that week. I will give a make-up class on Saturday 10/19, 10am-12:30pm in RH 304. The lecture will also be video captured (and put to NYU Classes of this course) in case you cannot make it.

3. Note that the Midterm Exam will be on Monday 10/28 in the regular class time and location. We will talk more about it when it comes closer.

Announcement (9/28/19):
HW1 Q1 has been revised to clarify the question. Please download HW1 again to get the new version --- refresh your browser at this web site first, then click on HW1 below to download.

Announcement (9/12/19):
The location of the TA office hours has been finalized: RH 221, effective immediately.

TA: Shi Shu (Email: shushi@nyu.edu. Office Hours --- Time: Thursdays 1:00--3:00pm; Location: RH 221.).

Help/Recitation Sections: The TA will give help/recitation sections to present homework solutions. These sections are on Fridays 2pm--4pm (note that there are 2 hours) in the weeks of the homework due dates (e.g., suppose HW1 is due on Monday 10/7, then there will be a help/recitation section on Friday 10/11 to present HW1 solutions). The location is the Conference Room 834 (8th Floor) of 370 Jay Street.

Syllabus: PDF

Homework 1: PDF

Homework 2: PDF

Homework 3: PDF

Homework 4: PDF

Last update: 12/12/19.