Fundamental Algorithms
CSCI-GA.1170-001/Summer 2018


Description

Instructor: Alex Alekseyev
Lecture: Wednesdays, 6:00-8:20 pm, CIWW 312
Instructor office hours: Wednesdays, 5:00-6:00 pm, CIWW 328
Recitation leader and grader: Sreyas Mohan
Recitation: Thursdays, 6:00-7:00 pm, CIWW 312
Recitation leader 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.


Schedule

Date Topic Reading Notes
Wed, 05/23/2018 Algorithm Analysis CLRS 2.1-2.2, 3.1-3.2 Homework 1
Thu, 05/24/2018 Recitation
Wed, 05/30/2018 Divide and Conquer CLRS 2.3, 4.1, 4.3-4.5 Homework 2
Thu, 05/31/2018 Recitation
Wed, 06/06/2018 Sorting Algorithms CLRS 6.1-6.5, 8.1-8.4 Homework 3
Thu, 06/07/2018 Recitation
Wed, 06/13/2018 Randomized Algorithms CLRS 5.1-5.3, 7.1-7.4, 9.2 Homework 4
Thu, 06/14/2018 Recitation
Wed, 06/20/2018 Hash Tables CLRS 11.1-11.5 Homework 5
Thu, 06/21/2018 Recitation
Wed, 06/27/2018 Midterm Exam CLRS Midterm Exam
Thu, 06/28/2018 Recitation
Wed, 07/05/2018 Search Trees CLRS 12.1-12.3, 13.1-13.4 Homework 6
Mon, 07/09/2018 Recitation
Wed, 07/11/2018 Graph Algorithms I CLRS 22.1-22.5 Homework 7
Thu, 07/12/2018 Recitation
Wed, 07/18/2018 Graph Algorithms II CLRS 23.1-23.2, 24.1-24.3 Homework 8
Thu, 07/19/2018 Recitation
Wed, 07/25/2018 Dynamic Programming CLRS 15.1-15.4 Homework 9
Thu, 07/26/2018 Recitation
Wed, 08/01/2018 Approximation Algorithms CLRS 34.1-34.5, 35.1-3 Practice Exam
Thu, 08/02/2018 Recitation
Wed, 08/08/2018 Final Exam CLRS Final Exam

Grading


See Also

Academic Integrity Policy: http://cs.nyu.edu/web/Academic/Graduate/academic_integrity.html