V22.0310-001 Basic Algorithms (Honors), Fall 2003

Lecturer: Prof. Yevgeniy Dodis, dodis(at)cs.nyu.edu, (212) 998-3084, room 508, WWH. Office hour: Thursday 12:15-1:15
Meeting Time/Place: TR 11-12:15, room 513, WWH.
Midterm: October 14, in class. Final: December 16, 10:00-11:50, room 513, WWH
Mailing list: To subscribe to the class list, follow instructions at
To post a message to all the list members, send email to v22_0310_001_fa03@cs.nyu.edu. Please, post only messages interesting to everybody taking the class. Specific class-related questions and most of your other correspondence should be directed to the instructor.
Course Homepage: http://cs.nyu.edu/courses/fall03/V22.0310-001/index.htm

Lecture Summaries

Additional Handouts:

Problem Sets:

Brief Course Description:

This is an introductory course in algorithms. We will cover standard topics such as sorting, divide-and-conquer, various data structures, graph algorithms, dynamic programming, greedy algorithms, and - time permitting - NP-completeness and basic approximation algorithms. The emphasis will be given to formal mathematical proofs of algorithms correctness and the rigorous analysis of their running time.


Introduction to Algorithms (Second Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press and McGraw-Hill.


There will be one in-class midterm and a final exam, in addition to approximately weekly homework assignments. Tentative grade split is 40% homework, 25% midterm and 35% final exam. I will also entertain the possibility of an optional honors project for those who are interested. The project will involve reading and implementing one of the algorithms not covered in the course.


Some of the homework exercises will be routine, but others will be more challenging. I do not expect you to solve all of the homework problems, but I hope that you will benefit from working on the more difficult ones. A few hints on the homework assignments: