V22.0310-001/002 Basic Algorithms (Regular and Honors), Spring 2009

Lecturer: Prof. Yevgeniy Dodis, dodiscs.nyu.edu, (212) 998-3084, room 413, WWH. Office hour: Monday 4-5
Meeting Time/Place: MW 2-3:15, room 202, WWH.
Recitation Time/Place: W 9:30-10:45, room 201, WWH.
Recitation Instructor: Antonina Mitrofanova, antoninacs.nyu.edu, (212)998-3375, Rm 1010, 715 Broadway. Office hour: Monday 11:30-12:30
Midterm: Wednesday, March 11, in class. Final: Monday 2-4, May 11, room 202
Mailing list: To subscribe to the class list, whether regular section or honors section, follow instructions at
Notice, the above mailing list will be used both for regular (002) and honors (001) sections. So do not sign-up for the "001" list.
To post a message to all the list members, send email to v22_0310_002_sp09@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/spring09/V22.0310-001/index.html

Lecture Summaries

Additional Handouts:

Problem Sets:

  • Homework 1: (due Feb. 2). (.pdf, .tex template, .ps sample)
  • Homework 2: (due Feb. 9). (.pdf, .tex template, .ps sample)
  • Homework 3: (due Feb. 23). (.pdf, .tex template, .ps sample)
  • Homework 4: (due Mar. 2). (.pdf, .tex template, .ps sample)
  • Homework 5: (due Mar. 9). (.pdf, .tex template, .ps sample)
  • Homework 6: (due Mar. 30). (.pdf, .tex template, .ps sample)
  • Homework 7: (due Apr. 6). (.pdf, .tex template, .ps sample)
  • Homework 8: (due Apr. 13). (.pdf, .tex template, .ps sample)
  • Homework 9: (due Apr. 20). (.pdf, .tex template, .ps sample)
  • Homework 10: (due Apr. 27). (.pdf, .tex template, .ps sample)
  • Homework 11: (due May 4). (.pdf, .tex template, .ps sample)

  • 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 arguing the correctness of algorithms and performing the 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.

    Each homework grade will consist of two parts: correctness and effort. The correctness grade is a numeric grade equaling the sum of the correctness grades for each homework problem, and roughly measures the fraction of the homework correctly solved. In contrast, the effort grade is a single number from 0% to 100%, and roughly measure the effort level the student has put into solving the homework. This grade will play an important role in the "overall" homework evaluation, so students are encouraged to try as many problems as possible. (Of course, simply restating the problem or intentionally writing "nonsense" as a proposed "solution" might actually lower your effort grade, so only put genuine thoughts and attempts into your solutions.) Generally, I expect the effort grade to be "higher" than the correctness grade.

    Additionally, students can increase their total grade by up to 10% (for a total maximum of 110%) by doing well in self-grading their homework, as explained in class. Please make sure you make a copy of your homework before handing it in.

    Students in the honors section will have to do an honors project studying/implementing some advanced algorithmic topic not covered in class.


    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. Homework will be assigned on Mondays, and will be due the following Monday. No late homework will be accepted. The solutions will be handed out during the recitation on the wednesday of the week the homework is due. We encourage the students to come to the recitation - not only for the homework solutions, - but primarily to see examples of the problems similar to those assigned for the following Monday. Self-graded homework will be due one week from the assignment due date (and should naturally utilize the solutions handed in during the recitation). It will not be returned to the students.

    A few hints on the homework assignments: