<; office hours: Tue 11:00am-12:00pm (Section 1) and Thu 11:00am-12:00pm (Section 3), over Zoom.
- Section 1
- Recitation 1 (section 002): Min Jae Song (mjs1168), Mondays 12:30-1:45pm, 12WP G08; office hour Tue 9:30-10:30am, online
- Recitation 2 (section 021): Harish Karthikeyan (hk2617), Mondays 12:30-1:45pm, online; office hour Mon 2:00-3:00pm, online
- Section 3
- Recitation 1 (section 004): Peter Fenteany (pf2184), Wednesdays 8:00-9:15am, GCASL 461; office hour Wed 3:00-4:00pm, online
- Recitation 2 (section 041): Ishan Agarwal (ia1020), Wednesdays 8:00-9:15am, online; office hour Sunday 2:00-3:00pm, online
- Tutors:
- Aditya Kashilkar: Monday 10:00-11:45am, Thursday 2:15pm-4:00pm, Friday 10:30am-12:00pm
- Tianbo Jiang: Tuesday 3:00-5:00pm, Wednesday 2:00-3:00pm, Friday 4:00-6:00pm
- Aditya Pandey: Tuesday 5:00-7:00pm, Wednesday 11:00am-1:00pm, Thursday 7:30-8:30pm
- Vishal Kumar: Tuesday 2:00-3:00pm and 7:00-8:00pm, Wednesday 1:00-2:00pm, Friday 2:00-4:00pm
- As this is a large class, we ask that you first try to post all questions on [Campuswire](https://campuswire.com/c/GDAFBAB46/feed), and/or attend the tutoring sessions. Please email your recitation leader only as a last resort. The instructor will not be able to respond to emails.
## 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.
We will try to cover most of chapters 1-4, 6-8, 12, 15, 16, 22-25, 30, 31, 34 of [CLRS].
## Prerequisites
Data Structures (CSCI-UA 102); Discrete Mathematics (MATH-UA 120); and either Calculus I (MATH-UA 121) or Mathematics for Economics I (MATH-UA 211). Also at least one year of experience with a high-level language such as Python, 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, 3rd Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein**, published by MIT Press. Our main textbook.
- Algorithm Design by Jon Kleinberg and Eva Tardos, Published by Pearson.
- [Lecture Slides](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/) for Algorithm Design by Kevin Wayne, distributed by Pearson.
## Summary of lectures
Class | Date | Topics | Read and watch before class | Notes | Assignments
--- | --- | --- | --- | --- | ---
1 | Jan 25 | Intro, logists, insertion sort, run time analysis | CLRS §1, §2.1, §2.2; Insertion sort [video1](https://www.youtube.com/watch?v=K4CuPzdiAIo), [video2](https://www.youtube.com/watch?v=EdIKIf9mHk0) and [demo1](https://www.lemmaplay.com/sort/insertion-sort.html) and [demo2 (click INS)](https://visualgo.net/en/sorting)| pp. 1.2-1.5 of [Lecture 1](lecture_1.pdf) | [HW1](hw1.pdf)
2 | Jan 27 | Big-O notation, merge sort | CLRS §2.3,3; Merge Sort [video](https://www.youtube.com/watch?v=Pr2Jf83_kG0) and [demo (click MER)](https://visualgo.net/en/sorting); [Big-O video](https://www.youtube.com/watch?v=v4cd1O4zkGw) | [Lectures 2-6](lectures_2_6.pdf), slides 2-11 of [KT Chapter 5a](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf) |
3 | Feb 1 | Analysis of merge sort, Quick Sort | CLRS §2.3, 4.3-4.6, 7; Quick Sort [video](https://www.youtube.com/watch?v=SLauY6PpjW4) and [demo (click QUI)](https://visualgo.net/en/sorting) | [Lectures 2-6](lectures_2_6.pdf), slides 2-11 of [KT Chapter 5a](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf) | [HW2](hw2.pdf)
4 | Feb 3 | Finishing Quick Sort; Karatsuba's algorithm | CLRS §7 | [Lectures 2-6](lectures_2_6.pdf), slides 4-12 of [KT Chapter 5b](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05Multiplication.pdf) |
5 | Feb 8 | Finishing Karatsuba, Closest pair in the plane | KT §5 | [Lectures 2-6](lectures_2_6.pdf), slides 21-34 of [KT Chapter 5a](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/05DivideAndConquer.pdf) | [HW3](hw3.pdf)
6 | Feb 10 | Finishing Closest Pair | CLRS §33.4 | [Lectures 2-6](lectures_2_6.pdf) |
7 | Feb 15 | Median and order statistics in linear time | CLRS §9 | [Lectures 7-13](lectures_7_13.pdf) | [HW4](hw4.pdf)
8 | Feb 17 | Lower bound for comparison sort | CLRS §8.1 | [Lectures 7-13](lectures_7_13.pdf) |
9 | Feb 22 | Counting sort, Radix sort; Dynamic Programming: Fibonacci Numbers | CLRS §8.2, §8.3 | [Lectures 7-13](lectures_7_13.pdf) | [HW5](hw5.pdf)
10 | Feb 24 | Dynamic Programming: Rod Cutting Problem | CLRS §15.1 | [Lectures 7-13](lectures_7_13.pdf) |
11 | Mar 1 | Dynamic Programming: Longest Common Subsequence| CLRS §15.4, [visualization](http://lcs-demo.sourceforge.net/) | [Lectures 7-13](lectures_7_13.pdf) | [HW6](hw6.pdf)
12 | Mar 3 | Dynamic Programming: LCS, Knapsack | CLRS §15.3-4; Demaine's [video lecture](https://youtu.be/ocZMDMZwhCY?t=2592)| [Lectures 7-13](lectures_7_13.pdf), slides 23-28 of [KT Chapter 6](http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/06DynamicProgramming.pdf) |
13 | Mar 8 | Greedy: Interval scheduling (aka activity selection) | CLRS §16.1-2 | [Lectures 7-13](lectures_7_13.pdf), [Slides 1-10](http://athena.nitc.ac.in/~kmurali/Courses/Algos15A/interval.pdf) | [HW7](hw7.pdf)
14 | Mar 10 | Greedy - Huffman Code | 6 first minutes of video on [priority queues](https://youtu.be/B7hVxCmfPtM); CLRS §16.3 | [Lectures 16-22](lectures_16_22.pdf); Slides 1-17 of [KT Chapter 4.8](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04Huffman.pdf) | [Practice Midterm](practice_midterm.pdf)
15 | Mar 22 | Review of practice midterm and HW | | |
16 | **Mar 24** | Midterm - Good luck! | | |
17 | Mar 29 | Greedy - Huffman Code | CLRS §16.3 | [Lectures 16-22](lectures_16_22.pdf); [KT Chapter 4.8](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04Huffman.pdf), and [advanced notes for further reading](https://cs.nyu.edu/~roweis/csc310-2005/notes/lec2x.pdf) | [HW8](hw8.pdf)
18 | Mar 31 | Graphs, BFS | CLRS §22.1-22.2, [adj list and adj matrix visualization](https://visualgo.net/en/graphds), [visualization](https://visualgo.net/en/dfsbfs) | [Lectures 16-22](lectures_16_22.pdf) |
19 | Apr 5 | DFS | CLRS §22.3; [video](https://youtu.be/AfSk24UTFS8) |[Lectures 16-22](lectures_16_22.pdf) | [HW9](hw9.pdf)
20 | Apr 7 | DFS, edge classification, detecting acyclic graphs | CLRS §22.3 | [Lectures 16-22](lectures_16_22.pdf) |
21 | Apr 12 | Topological sort, strongly connected components | CLRS §22.4,22.5 | [Lectures 16-22](lectures_16_22.pdf) | [HW10](hw10.pdf)
22 | Apr 14 | Finishing SCC; Minimum Spanning Tree | CLRS §23.1; [demo](https://visualgo.net/en/mst?slide=1) | [Lectures 16-22](lectures_16_22.pdf) |
23 | Apr 19 | MST safe edge theorem, Kruskal's algorithm | CLRS §23.2 | [Lectures 23-28](lectures_23_28.pdf) | [HW11](hw11.pdf)
24 | Apr 21 | Prim's algorithm | CLRS §23.2 | [Lectures 23-28](lectures_23_28.pdf) |
25 | Apr 26 | Dijkstra's SSSP algorithm | CLRS §24.3 and [video](https://www.youtube.com/watch?v=_qX5mIrAjtU) | [Lectures 23-28](lectures_23_28.pdf); [Prof. Shoup's demo](dijkstra_demo.pdf) | [HW12](hw12.pdf)
26 | Apr 28 | Floyd-Warshall APSP algorithm | CLRS §25.2 | [Lectures 23-28](lectures_23_28.pdf) | [Practice final](practice_final.pdf)
27| May 3 | Computability, Wang tiling, the halting problem is uncomputable | CLRS §34 | [Lectures 23-28](lectures_23_28.pdf) |
28| May 5 | P vs. NP, NP completeness, Vertex Cover, Independent set, 3SAT, reductions, approximating Vertex Cover | CLRS §34, 35 | [Lectures 23-28](lectures_23_28.pdf) |
| May 12 | 8:00-9:50am, Final for Section 3 (morning section), 60FA Room 150 - Good Luck ! |||
| May 16 | 12:00-1:50pm, Final for Section 1 (afternoon section), Room TBD - Good Luck ! |||
<!-- Bellman-Ford SSSP algorithm ; Chapter 24.1 of CLRS-->
## Course Policies
### Homework
There will be weekly homework assignments.
We prefer homework submissions typeset in LaTeX (you might want to use the [Overleaf templates](https://www.overleaf.com/read/fvcscrvctmjg)) or Word. You are encouraged to insert scanned figures or illustrations. Scanned handwritten submissions will only be graded if *neatly written and perfectly legible*. Honors questions will be graded, but will not affect your grade in any way.
Submission is through Gradescope.
### Grading
Tentative grade split is 5% participation, 20% homework, 25% midterm, and 50% final exam. Participation includes both in class, and on BrightSpace.
### 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).
### Collaboration
We strongly encourage you to discuss assignments with your peers. However, all work that you submit must be your own. You must list all discussions you had.
You **should not** consult previous years' students, code, assignments, etc. You may help other students and groups on specific technical issues but you must acknowledge such interactions.
Interactions must be limited to groups of at most 3.
### Plagiarism
**Anything** you use from other sources (other students, web, etc.) must be clearly acknowledged.
Failure to do so will result in a zero grade for the submitted work and, except in cases of obvious mistakes, a University investigation.
### Laptops
We discourage the use of laptops. Pen and paper are more efficient for taking notes, and less distracting to students around you.
If you do decide to bring a laptop, we ask that you use it for taking notes only, and not browsing the web (even if it is
related to the course). If you cannot follow this rule, we ask that you sit in the back row, so there are no students behind you to get distracted by the monitor.
### Participation
Students are expected to attend every meeting of the class.
Students are also expected to participate actively in course discussion, either in person or on Piazza. Participation will be taken into account in the final grade.
## Applicable University Policies
### Academic Integrity
Work you submit should be your own. Please consult the [CAS academic integrity policy](https://cas.nyu.edu/content/nyu-as/cas/academic-integrity.html) for more information. Penalties for violations of academic integrity may include failure of the course, suspension from the University, or even expulsion.
### Religious Observance
As a nonsectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the [University Calendar Policy on Religious Holidays](http://www.nyu.edu/about/policies-guidelines-compliance/policies-and-guidelines/university-calendar-policy-on-religious-holidays.html)
### Disability Disclosure Statement
Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, or who is deaf or hard of hearing. Students should please register with the Moses Center for Students with Disabilities at 212-998-4980.
> NYU's Henry and Lucy Moses Center for Students with Disabilities
> 726 Broadway, 2nd Floor
> New York, NY 10003-6675
> Telephone: 212-998-4980
> Voice/TTY Fax: 212-995-4114
> Web site: http://www.nyu.edu/csd
]]>