CSCI-UA.0310-004/005 Basic Algorithms, Spring 2015

Lecturer: Prof. Yevgeniy Dodis,, (212) 998-3084, room 413, WWH. Office hour: Monday 3:30pm-4:30pm.
Meeting Time/Place: MW 2pm-3:15pm, room 101, WWH.
Recitation Time/Place: Mon 12:30pm-1:45pm, room 109, WWH.
Recitation Instructor: Masha Pershina,, 719 Broadway, Room 713.
Tutor: Tomek Kazana,, (212) 992-7533, Rm 408, WWH. --> Office hours: Tue 10am-11am, Thu 11am-12pm, room 408, WWH.
Midterm: Mar 11, in class. Final: May 13, 2-3:50PM, Room 101, WWH.
Mailing list: To subscribe to the class list, follow instructions at
To post a message to all the list members, send email to 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:

Lecture Summaries (see also Selected Notes from MIT)

Additional Handouts:

Problem Sets: (remember to write each new problem on separate, 8.5x11 sheet(s) of paper, with your name, homework and problem number on top, and to staple your homework.)

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 - online and approximation algorithms. The emphasis will be given to arguing the correctness of algorithms and performing the analysis of their running time.


Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press.
You can get either the THIRD EDITION (recommended) or the SECOND EDITION. The exercises will refer to the THIRD edition.


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. Students on the "boundary" between two grades might increase their grade by doing accurate self-grading, as explained below.


Each problem set will consist of several problems. 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 the day of the class, and will be due the following week (unless stated otherwise). No late homework will be accepted. The solutions will be discussed during the recitation immediately following the due date of the homework. 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 week.

The maximum point value for each problem (and, sometimes, parts of the problem) will be stated on the homework. Some questions in the homework will be for the extra credit, and will be explicitly marked as such (together with their maximum extra credit) on each assignment. Solving such problems can make your overall grade for the homework above 100%, or, alternatively, effectively "erase" the credit lost for not solving some of the required problems.

Each problem in a given problem set must be written on a separate, one-sided 8.5x11 sheet of paper, with the student's name, homework number and problem number on top. If you cannot fit a solution of one page, do not use the back side, but use more sheets of paper (and put page numbers just in case). For example, if your name is John Doe, you are solving Problem 3 of Homework 5, and the solution required you to use three sheets of 8.5x11 paper, the second sheet should have "John Doe, Homework 5, Problem 3, page 2/3" on top. (If only one sheet is required, no need to put "page 1/1", it is the default.)

Do not forget to staple all the problems together. We encourage, but do not require, the students to type their solutions. This is much easier to grade and edit, and much harder to lose. In particular, while Microsoft Word or other such primitive editors can be used (and are already better than hand written solutions!), we suggest to use Latex, and will provide a latex file for each homework (where the students need to replace "stars" ***** by their solutions). Students are welcome to look at this short Latex tutorial for some useful pointers.

We also suggest that you make copies of your homework before submitting the hard copy.
In fact, you are welcome (but not required) to email a .pdf file with your solution to the Tutor in addition to (not instead of!) the hard copy. This will protect against (unlikely) loss of your homework (of course, if you type your solutions, this is automatically done!), and will be useful for grade disputes. Making copies is also useful for self-grading, as explained below.


Another way where copying homework is useful is for self-grading. In particular, after the students handed in their homework and learned the correct solutions during the following recitation, but before getting back their graded solutions, the students can hand in their self-graded homework, using the same grading system they expect from the actual graders. Unlike regular homework, self-graded homework should only be submitted by email to the Recitation Instructor. We believe self-grading their own mistakes will greatly improve the students' understanding of the material. Moreover, as explained above, students on the "boundary" between two grades might increase their grade by doing accurate self-grading.

Concluding Remarks: