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 (tentative date) 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 5:00-6: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) ## 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.