Key Information | ---|-------- Class Meetings | Wed 5:10-7:00pm in CIWW 517 First Lecture | Sep 6, 2017 Last Lecture | Dec 13, 2017 Mid Term | Oct 25, 2017 Final Exam | Dec 20, 2017, 5:10-7:00pm in CIWW 517 Instructor | [Amir Shpilka](http://www.cs.tau.ac.il/~shpilka/) Office | CIWW 403 Office Hours | Tue 5-6, Wed 7-8 Recitation Leader | [Siddharth Krishna](http://www.cs.nyu.edu/~siddharth/) Recitation | Fri 6:10-7:00pm in CIWW 517 Office Hours |Fri 7:00-8:00pm in CIWW 517 ## Overview Reviews a number of important algorithms, with emphasis on correctness and efficiency. The topics covered include solution of recurrence equations, sorting algorithms, fast linear algebra, 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. - [Web site at NYU classes with forum for questions](https://newclasses.nyu.edu/portal/site/78adb805-26aa-4960-b4a4-080599c34452) - We may upload lecture notes that my cover part or more of what was covered in class. - [Notes from recitation by Siddharth]( http://cs.nyu.edu/~siddharth/teach/17F-fa/) ## Syllabus Class | Date | Topics | Notes | Assignments --- | --- | --- | --- 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) | [HW1](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw1.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) | [HW2](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw2.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) | [HW3](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw3.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) | [HW4](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw4.pdf) 5 | Oct 4 | Chapters 8.1,8.2,9 of CLRS, Lower bound for compariso sort, counting sort, Median and selection | [Lecture 5](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture5.pdf) | [HW5](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw5.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) | [HW6](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw6.pdf) 7 | Oct 18 | Chapter 15 of CLRS, Dynamic Programming | [Lecture 7](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture7.pdf) | [HW7](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw7.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) | [HW8](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw8.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) | [HW9](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw9.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) | [HW10](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw10.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) | [HW11](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw11.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) | [HW12](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw12.pdf) 13 | Dec 13 | Chapter 34 of CLRS, P and NP | [Lecture 13](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/Lecture13.pdf) | [HW13](http://www.cs.tau.ac.il/~shpilka/courses/alg2017/hw13.pdf) ## Grading There will be one in-class midterm and a final exam, in addition to approximately weekly homework assignments. Tentative grade split is 30% homework, 30% midterm and 40% final exam. ## Late Submission Policy Late submissions of homework solutions will be graded with a 10% penalty per day of late submission. Solutions will not be graded if they are submitted later than one week 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 must do the projects as a group but not with other groups and without consulting previous years' students, code, etc. You should 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.