<
Office Hours | Tue 5:15-6:45pm, WWH 403
Mon Recitation Leader | [Shravas Rao](https://cims.nyu.edu/~rao/)
Recitation | Mon 9:30-10:45am, WWH 512
Office Hours | Thu 6:00-7:00pm, WWH 412
Wed Recitation Leader | Conrad Christensen
Recitation | Wed 9:30-10:45am, WWH 512
Office Hours | Mon 4:00-5:00pm, 60FA 406
Tutor | Urvish Desai
Tutoring room | WWH 412
Tutoring hours | Monday 6:15 - 7:30pm
| Wednesday 2:00 - 4:30pm
| Thursday 4:45 - 6:00pm
## Overview
Reviews a number of important algorithms, with emphasis on correctness and efficiency. The topics covered include solution of recurrence equations, sorting algorithms, binary search trees, partitioning, graphs, spanning trees, shortest paths, connectivity, depth-first and breadth-first search, dynamic programming, and divide-and-conquer techniques.
The somewhat ambitious plan is to cover (most of) chapters 1-4, 6-8, 12, 15, 16, 22-25, 30, 31, 34 of CLRS (see below).
## Prerequisites
At least one year of experience with a high-level language such as Pascal, C, C++, or Java; and familiarity with recursive programming methods and with data structures (arrays, pointers, stacks, queues, linked lists, binary trees).
## Resources
- Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press.
- Algorithm Design by Jon Kleinberg and ƒva Tardos, Published by Pearson.
- [Lecture Slides](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/) for Algorithm Design by Kevin Wayne, distributed by Pearson.
- [Web site at NYU classes](https://newclasses.nyu.edu/portal/site/a4180f98-050b-4a54-8579-2aadc2b22f24)
- [Piazza forum for questions]( https://piazza.com/class/jljlg2zq47e378)
- Lecture notes of fundamental algorithm that cover most of the material.
## Summary of Recitations
[Notes](https://cs.nyu.edu/~conradbc/lecture_notes_all.pdf) of recitations. The file will be updated weekly.
## Summary of lectures
Class | Date | Topics | Read | Notes | Assignments
--- | --- | --- | --- | ---
1 | Sep 4 | Administrata, insertion sort, run time analysis | chapters 1 , 2.1,2.2 of CLRS | pages 1.2-1.5 of [Lecture 1](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture1.pdf) |
2 | Sep 6 | Big Oh notation, merger sort | Chapters 3, 2.3 of CLRS | pages 2.1-2.4.1 of [Lecture 2](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture2.pdf), slides 2-11 of [KT Chapter 5a](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf) | [HW 1](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_1.pdf)
3 | Sep 11 | Analysis of merge sort, master theorem | Chapters 2.3, 4.3-4.6 of CLRS | pages 2.5 - 2.7 of [Lecture 2](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture2.pdf) and [Master theorem](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/MT.pdf), slides 2-11 of [KT Chapter 5a](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf) |
4 | Sep 13 | Karatsuba's algorithm, Quick Sort | Chapter 7 of CLRS | pages 3.1-3.4 and 3.6-3.7 of [Lecture 3](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture3.pdf), slides 4-12 of [KT Chapter 5b](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05Multiplication.pdf) | [HW 2](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_2.pdf)
5 | Sep 18 | Closest pair in the plane | Chapter 5 of KT | slides 21-34 of [KT Chapter 5a](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf) |
6 | Sep 20 | More on solving recurrences | Chapters 4.3-4.6 of CLRS | pages 2.5 - 2.7 of [Lecture 2](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture2.pdf) and [Master theorem](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/MT.pdf) | [HW 3](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_3.pdf)
7 | Sep 25 | Heaps, Max-Heapify, Build-Maxheap | Chapters 6.1-6.3 of CLRS | pages 4.1-4.4 of [Lecture 4](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture4.pdf) |
8 | Sep 27 | Analysis of Build-Maxheap, heapsort, priority queues | Chapter 6 of CLRS | [Lecture 4](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture4.pdf) | [HW 4](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_4.pdf)
9 | Oct 2 | Lower bound for comparison sort, counting sort | Chapters 8.1-8.2 of CLRS | pages 5.1-5.4 of [Lecture 5](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture5.pdf) |
10 | Oct 4 | Finding order statistics in linear time | Chapter 9 of CLRS | pages 5.5-5.7 of [Lecture 5](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture5.pdf) | [HW 5](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_5.pdf)
11 | Oct 11 | Dynamic Programming - Rod cutting, Longest common subsequence | Chapters 15.1,15.3,15.4 of CLRS | pages 7.2-7.5 of [Lecture 7](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture7.pdf) | [HW 6](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_6.pdf)
12 | Oct 16 | Dynamic Programming - LCS, Edit-Distance, Knapsack | Chapters 15.3-4 of CLRS | pages 7.5-7.7 of [Lecture 7](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture7.pdf), slides 23-28 of [KT Chapter 6](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/06DynamicProgramming.pdf) |
13 | Oct 18 | Dynamic Programming , Greedy - Activity selection | Chapters 16.1-2 of CLRS | pages 8.1-8.3 of [Lecture 8](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture8.pdf), slides 3-8 of [KT Chapter 4](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms.pdf) | [Practice MidTerm](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Practice_Midterm.pdf)
14 | Oct 23 | Review - went over practice midterm and HW | | |
15 | Oct 24 | Midterm - Good luck! | | |
16 | Oct 30 | Greedy - Huffman Code | Chapter 16.3 of CLRS | pages 8.4-8.6 of [Lecture 8](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture8.pdf), Slides 1-17 of [KT Chapter 4.8](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04Huffman.pdf) |
17 | Nov 1 | Greedy - Huffman Code | Chapter 16.3 of CLRS | pages 8.4-9.2 of [Lecture 8](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture8.pdf) and [Lecture 9](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture9.pdf), [KT Chapter 4.8](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04Huffman.pdf) | [HW 7](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_7.pdf)
18 | Nov 6 | Garphs, BFS | Chapters 22.1-22.2 of CLRS | pages 9.3-9.6 of [Lecture 9](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture9.pdf) |
19 | Nov 8 | BFS, DFS | Chapter 22.3 of CLRS | pages 9.3-9.9 of [Lecture 9](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture9.pdf) and pages 1-2 of [Lecture 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture10.pdf) | [HW 8](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_8.pdf)
20 | Nov 13 | DFS and applications | Chapter 22.3 of CLRS | pages 9.7-9.9 of [Lecture 9](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture9.pdf) and pages 1-2 of [Lecture 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture10.pdf) |
21 | Nov 15 | Topological sort, strongly connected components | Chapters 22.4-5 of CLRS |page 3 of [Lecture 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture10.pdf) | [HW 9](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_9.pdf)
22 | Nov 20 | Minimum Spanning Tree | Chapter 23.1 of CLRS | pages 4-5 of [Lecture 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture10.pdf) |
23 | Nov 27 | MST - Kruskal's and Prim's algorithms | Chapter 23.2 of CLRS | pages 5-6 of [Lecture 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture10.pdf) and 11.0-3 of [Lecture 11](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture11.pdf) | [HW 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_10.pdf)
24 | Nov 29 | Dijkstra's SSSP algorithm | Chapter 24.3 of CLRS | pages 11.4-11.6 of [Lecture 11](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture11.pdf) and 12.2-3 of [Lecture 12](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture12.pdf) | [HW 11](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_11.pdf)
25 | Dec 4 | Bellman-Ford SSSP algorithm | Chapter 24.1 of CLRS | pages 11.5-11.7 of [Lecture 11](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture11.pdf) and 12.0-1 of [Lecture 12](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture12.pdf) |
26 | Dec 6 | Floyd-Warshall APSP algorithm | Chapter 25.2 of CLRS | 12.4-5 of [Lecture 12](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture12.pdf) | [HW 12](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Homework_12.pdf)
27| Dec 11 | Computability, the halting problem, Tiling, Godel's incompleteness theorem, P, NP | Chapter 34 of CLRS | [Lecture 13](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture13.pdf) |
28| Dec 13 | P vs. NP, NP completeness, Vertex Cover, Independent set, Clique, 3SAT, reductions | Chapter 34 of CLRS | [Lecture 13](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture13.pdf) |
29 | Dec 17 | Review class, 3-6pm at room 446 in 60 5th Ave ||| [Practice Final](http://www.cs.tau.ac.il/~shpilka/courses/alg2018/Practice_Final.pdf)
30 | Dec 20 | Exam - Good Luck ! |||
## Grading
There will be one in-class midterm and a final exam, in addition to approximately weekly homework assignments. Tentative grade split is 20% homework, 30% midterm and 50% final exam.
## Late Submission Policy
Late submissions of homework solutions will be graded with a 20% penalty per day of late submission. Solutions will not be graded if they are submitted later than two days after the specified deadline.
## Academic Integrity
Please review the departmental [academic integrity policy](http://www.cs.nyu.edu/web/Academic/Graduate/academic_integrity.html).
In this course, you may discuss assignments with other students, but the work you turn in must be your own. Do not copy another student's work. You should not consult previous years' students, code, etc. You may help other students and groups on specific technical issues but you must acknowledge such interactions. Copying code or other work without giving appropriate acknowledgment is a serious offense with consequences ranging from no credit to potential expulsion.
## Fundamental algorithms lecture notes from Fall 2017
Class | Date | Topics | Notes
--- | --- | --- | ---
1 | Sep 6 | Administrata, chapters 1 , 2.1,2.2 of CLRS | [Lecture 1](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture1.pdf)
2 | Sep 13 | Chapters 2.3, 3, 4.5 of CLRS | [Lecture 2](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture2.pdf)
3 | Sep 20 | Chapters 4.2, 7 of CLRS, Binary search and Karatsuba's algorithm | [Lecture 3](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture3.pdf)
4 | Sep 27 | Chapter 6 of CLRS, Heaps, Heapsort, Priority queue | [Lecture 4](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture4.pdf)
5 | Oct 4 | Chapters 8.1,8.2,9 of CLRS, Lower bound for comparison sort, counting sort, Median and selection | [Lecture 5](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture5.pdf)
6 | Oct 11 | Chapters 12.1-12.3 of CLRS, Binary Serach Trees | [Lecture 6](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture6.pdf)
7 | Oct 18 | Chapter 15 of CLRS, Dynamic Programming | [Lecture 7](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture7.pdf)
8 | Nov 1 | Chapters 16.1-3 of CLRS, Greedy Algorithms | [Lecture 8](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture8.pdf)
9 | Nov 8 | Chapters 16.3, 22.1-22.2 of CLRS, Huffman code, graphs, BFS | [Lecture 9](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture9.pdf)
10 | Nov 15 | Chapters 22.3-22.4, 23.1 of CLRS, DFS, MST | [Lecture 10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture10.pdf)
11 | Nov 29 | Chapters 23.2, 24.1 of CLRS, MST, SSSP | [Lecture 11](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture11.pdf)
12 | Dec 6 | Chapters 24.1-24.3, 25.2 of CLRS, SSSP, APSP | [Lecture 12](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture12.pdf)
13 | Dec 13 | Chapter 34 of CLRS, P and NP | [Lecture 13](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture13.pdf)
]]>