V22.0310-001/002 Basic Algorithms (Regular and Honors), Spring 2010
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 101, WWH.
Recitation Time/Place: W 9:30-10:45, room 102, WWH.
Recitation Instructor:
Joel Alwen, jalwencs.nyu.edu,
(212)992-7533, Rm 408, WWH. Office hour: Wednesday 11-12
Midterm: Monday, March 8, in class.
Final: Monday 2-4, May 10, room 101.
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_sp10@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/spring10/V22.0310-001/index.html
Additional Handouts:
Problem Sets:
Homework 1: (due Feb. 1).
(.pdf, .tex template,
.ps sample)
Homework 2: (due Feb. 10).
(.pdf, .tex template,
.ps sample)
Homework 3: (due Feb. 22).
(.pdf, .tex template,
.ps sample)
Homework 4: (due Mar. 1).
(.pdf, .tex template,
.ps sample)
Homework 5: (due Mar. 10).
(.pdf, .tex template,
.ps sample)
Homework 6: (due Mar. 29).
(.pdf, .tex template,
.ps sample)
Homework 7: (due Apr. 5).
(.pdf, .tex template,
.ps sample)
Homework 8: (due Apr. 12).
(.pdf, .tex template,
.ps sample)
Homework 9: (due Apr. 19).
(.pdf, .tex template,
.ps sample)
Homework 10: (due Apr. 26).
(.pdf, .tex template,
.ps sample)
Homework 11: (due May 3).
(.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.
Textbook:
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.
Grading:
There will be one in-class midterm, one final exam and one programming
project, in addition to approximately weekly homework assignments.
Tentative grade split is 40% homework, 20% midterm, 30% final, 10%
project.
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. Alternatively, they can go an
"extra mile" in the final programming project.
Programming Project:
The details of the project are given below. They involve implementing
a specific algorithm, writing up the details about the implementation,
and testing your implementation on various "test cases". This will be
the only programming required for the course. Extra credit will be
given for implementing a nice GUI (e.g., a web page where one can
provide inputs and see outputs), or for implementing the extra
functionality. Also, one "winner" will be selected for the overall
"best" implementation, where "best" encompasses all the factors (speed
on test cases, elegance of code, GUI, etc.).
Homework:
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:
- 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
structure.
- 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
careful.
- 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.