| Instructor: | Alex Alekseyev |
| Lecture: | Wednesdays, 6:00-8:20 pm, CIWW 312 |
| Instructor office hours: | Wednesdays, 8:20-9:20 pm, CIWW 312 |
| Recitation leader: | Parth Rao |
| Recitation: | Thursdays, 6:00-7:00 pm, CIWW 312 |
| Recitation leader office hours: | Tuesdays, 5:00-6:00 pm, CIWW 412 |
| Textbook: | T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009 |
| Prerequisites: | Familiarity with common programming (recursion, pointers, arrays) and mathematical (logarithms, induction, probability) concepts. |
This graduate course reviews a number of important algorithms, with emphasis on correctness and efficiency. The topics covered include solution of recurrence equations, sorting algorithms, selection, binary search trees and balanced-tree strategies, tree traversal, partitioning, graphs, spanning trees, shortest paths, connectivity, depth-first and breadth-first search, dynamic programming, and divide-and-conquer techniques.
| Date | Topic | Reading | Notes |
|---|---|---|---|
| Wed, 05/24/2017 | Algorithm Analysis | CLRS 2.1-2.2, 3.1-3.2 | Homework 1 |
| Thu, 05/25/2017 | Recitation | ||
| Wed, 05/31/2017 | Divide and Conquer | CLRS 2.3, 4.1, 4.3-4.5 | Homework 2 |
| Thu, 06/01/2017 | Recitation | ||
| Wed, 06/07/2017 | Sorting Algorithms | CLRS 6.1-6.5, 8.1-8.4 | Homework 3 |
| Thu, 06/08/2017 | Recitation | ||
| Wed, 06/14/2017 | Randomized Algorithms | CLRS 5.1-5.3, 7.1-7.4, 9.2 | Homework 4 |
| Thu, 06/15/2017 | Recitation | ||
| Wed, 06/21/2017 | Lecture moved to 06/29 | CLRS | Prepare for midterm |
| Thu, 06/22/2017 | Recitation | ||
| Wed, 06/28/2017 | Midterm Exam | CLRS | Midterm Exam |
| Thu, 06/29/2017 | Hash Tables | CLRS 11.1-11.5 | Homework 5 |
| Wed, 07/05/2017 | Search Trees | CLRS 12.1-12.3, 13.1-13.4 | Homework 6 |
| Thu, 07/06/2017 | Recitation | ||
| Wed, 07/12/2017 | Graph Algorithms I | CLRS 22.1-22.5, 23.1-23.2 | Homework 7 |
| Thu, 07/13/2017 | Recitation | ||
| Wed, 07/19/2017 | Graph Algorithms II | CLRS 24.1-24.3, 26.1-26.2 | Homework 8 |
| Thu, 07/20/2017 | Recitation | ||
| Wed, 07/26/2017 | Dynamic Programming | CLRS 15.1-15.4 | Homework 9 |
| Thu, 07/27/2017 | Recitation | ||
| Wed, 08/02/2017 | Approximation Algorithms | CLRS 34.1-34.5, 35.1-3 | Practice Exam |
| Thu, 08/03/2017 | Recitation | ||
| Wed, 08/09/2017 | Final Exam | CLRS | Final Exam |
| Thu, 08/10/2017 | Recitation |
Homework is due on the day of the following recitation and should be submitted via NYU Classes (typeset is best, but scanned handwriting is okay too). Solutions will be discussed at the recitation, so the homework cannot be accepted late.
Grade split is 40% homework, 20% midterm, and 40% final exam.
| Academic Integrity Policy: | http://cs.nyu.edu/web/Academic/Graduate/academic_integrity.html |