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
Additional Handouts:
Problem Sets:
- Homework 1: (due Sep. 9).
(.pdf, .tex template,
.ps sample)
- Homework 2: (due Sep. 16).
(.pdf, .tex template,
.ps sample)
- Homework 3: (due Sep. 23).
(.pdf, .tex template,
.ps sample)
- Homework 4: (due Sep. 30).
(.pdf, .tex template,
.ps sample)
- Homework 5: (due Oct. 7).
(.pdf, .tex template,
.ps sample)
- Homework 6: (due Oct. 16).
(.pdf, .tex template,
.ps sample)
- Homework 7: (due Oct. 28).
(.pdf, .tex template,
.ps sample)
- Homework 8: (due Nov. 4).
(.pdf, .tex template,
.ps sample)
- Homework 9: (due Nov. 13).
(.pdf, .tex template,
.ps sample)
- Homework 10: (due Nov. 20).
(.pdf, .tex template,
.ps sample)
- Homework 11: (due Dec. 2).
(.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 formal mathematical proofs of algorithms
correctness and the rigorous analysis of their running time.
Textbook:
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.
Grading:
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.
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. A few hints on the homework assignments:
- Start early. 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.
Remember, this is an honors section, and I expect you to do
well without any cheating. Please talk to me if you are having
problems keeping up with the material.