CSCI-UA.0310-004/005 Basic Algorithms, Spring 2015
Lecturer: Prof. Yevgeniy
Dodis, dodiscs.nyu.edu, (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.
Masha Pershina, pershinacs.nyu.edu,
719 Broadway, Room 713.
Tomek Kazana, tomasz.kazanacs.nyu.edu,
(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
To post a message to all the list members, send email to
email@example.com. Please, post only messages
interesting to everybody taking the class. Specific class-related
questions and most of your other correspondence should be directed to
Course Homepage: http://cs.nyu.edu/courses/spring15/CSCI-UA.0310-004/index.html
- Homework 1: (due Feb. 4).
- Homework 2: (due Feb. 11).
- Homework 3: (due Feb. 18).
- Homework 4: (due Feb. 25).
- Homework 5: (due Mar. 4).
- Homework 6: (due Mar. 25).
- Homework 7: (due Apr. 1).
- Homework 8: (due Apr. 8).
- Homework 9: (due Apr. 15).
- Homework 10: (due Apr. 22).
- Homework 11: (due Apr. 29).
- Homework 12: (due May 11).
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
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
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
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
- Respect the Format. As explained above, we require
particular format from homework submissions. Please read/understand it carefully, and make sure you follow it to avoid unnecessary score penalties.
- Start early. Most problems will not be hard,
but others will be. Such more difficult problems are not
typically solved in one sitting. Start early and let the ideas
come to you over the course of a few days.
- Be rigorous. Each problem has a (sometimes
unwritten) requirement that you prove your algorithm
correct and analyze its running time. To obtain full
credit for a problem, it is necessary to fulfill these
requirements. We expect real proofs and real analyses, not
"proof by hand waving."
- Be concise. Express your algorithms at the
proper level of detail. Give enough details to clearly present your
solution, but not so many that the main ideas are
obscured. English is often a good way to express an
algorithm; pseudocode is good for communicating complex control
- Collaboration? You are encouraged to
solve all the homework questions on your own, but are
permitted to brainstorm difficult problems in small
groups, as long as each of you writes the solutions
individually and honestly acknowledges the cooperation.
Needless to say, if you work with others but never come up with
the solution on your own, you may do OK in the homework
component of your grade, but you will suffer on exams, so be
- Bibles? Help? More or less, you are only
allowed to use the textbook and your lecture notes. In
particular, the use of internet, course bibles, outsiders, and
other clearly "cheating" resources is strictly prohibited.
Please talk to me if you are having
problems keeping up with the material.