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.


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 (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 1:00--3:00pm 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 during 1:00--3:00pm to present HW1 solutions). The location will be finalized and announced later.

Syllabus: PDF

Last update: 9/12/19.