| Instructor: | Alex Alekseyev |
| Lecture: | Wednesdays, 6:00-8:20 pm, CIWW 312 |
| Recitation: | Thursdays, 6:00-7:00 pm, CIWW 312 |
| Instructor office hours: | Wednesdays, 5:00-6:00 pm, CIWW 328 |
| Thursdays, 7:00-8:00 pm, CIWW 328 | |
| Grader: | Ankit Vani |
| Grader office hours: | Mondays, 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/25/2016 | Algorithm Analysis | CLRS 2.1-2.2, 3.1-3.2 | Homework 1 |
| Thu, 05/26/2016 | Recitation | ||
| Wed, 06/01/2016 | Divide and Conquer | CLRS 2.3, 4.3-4.5 | Homework 2 |
| Thu, 06/02/2016 | Recitation | ||
| Wed, 06/08/2016 | Sorting and Selection I | CLRS 6.1-6.5, 8.1-8.4 | Homework 3 |
| Thu, 06/09/2016 | Recitation | ||
| Wed, 06/15/2016 | Sorting and Selection II | CLRS 7.1-7.4, 9.1-9.3 | Homework 4 |
| Thu, 06/16/2016 | Recitation | ||
| Wed, 06/22/2016 | Hash Tables and Disjoint Sets | CLRS 11.1-11.5, 21.1, 21.3 | Homework 5 |
| Thu, 06/23/2016 | Recitation | ||
| Wed, 06/29/2016 | Search Trees | CLRS 12.1-12.3, 13.1-13.4 | Homework 6 |
| Thu, 06/30/2016 | Recitation | ||
| Wed, 07/06/2016 | Graph Algorithms I | CLRS 22.1-22.5, 23.1-23.2 | Homework 7 |
| Thu, 07/07/2016 | Recitation | ||
| Wed, 07/13/2016 | Graph Algorithms II | CLRS 24.1-24.3, 26.1-26.2 | Homework 8 |
| Thu, 07/14/2016 | Recitation | ||
| Wed, 07/20/2016 | Dynamic Programming | CLRS 15.1-15.5 | Homework 9 |
| Thu, 07/21/2016 | Recitation | ||
| Wed, 07/27/2016 | String Algorithms | CLRS 32.1-32.4 | Homework 10 |
| Thu, 07/28/2016 | Recitation | ||
| Wed, 08/03/2016 | Approximation Algorithms | CLRS 34.1, 34.3, 34.5, 35.1-3, 35.5 | Practice Exam |
| Thu, 08/04/2016 | Recitation | ||
| Wed, 08/10/2016 | Final Exam | CLRS | Final Exam |
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 50% homework and 50% final exam.
| Academic Integrity Policy: | http://cs.nyu.edu/web/Academic/Graduate/academic_integrity.html |