Computer Science 4820
Introduction to Analysis of Algorithms
Cornell University, Spring 2010
Staff and Office Hours
A review sheet for the
final exam has been posted on the class website.
Professor Kleinberg's Wednesday morning office hours are moving
to 11:00am this week. In subsequent weeks, he'll shift back
to the normal time slot of 10:10-11:10.
Problem Set 6 will be available in Upson 360 starting at 11:15 on Monday,
Prelim 2 is taking place on Tuesday, April 13, at 7:30pm in Upson B17.
There is no homework due on Friday, April 16. The next homework will
be due April 23.
The lecture notes on Turing
machines have been updated to include pseudocode for
multi-tape and universal Turing machine simulations.
Staff and Office Hours
- Add cornell.edu to any incomplete email addresses below.
|CS 4820 STAFF
Hooyeon “Haden” Lee
Jong Hwi Lee
- Broadcast messages from the course staff to students
will be sent using firstname.lastname@example.org. All students
- There will be an additional mailing list,
email@example.com, for the
staff only. Students should use this for addressing
questions to the course staff about homework clarifications
and procedural questions (e.g. scheduling a make-up prelim).
Do not use this list as a substitute for office hours.
Questions about the lectures, homeworks, etc., should be
asked in office hours.
- There will be weekly problem sets, due in class (usually) on
- Late Homework Policy: It is expected that homework will be turned
in in class and on time. If you cannot come to class yourself,
you are responsible for finding someone else to turn in your assignment
for you, or else presenting it
(in hardcopy to Professor Kleinberg, or in email to cs4820-staff-l)
before the beginning of class on the date the homework
is due. Assignments turned in late will be accepted until 12 noon
on the due date, with a penalty of 8 points out of 30 for the
assignment. Beyond 12 noon on the due date,
late homework will not be be accepted
except in emergency situations. If a genuine emergency situation
exists you must inform the course staff as soon as possible.
- Deadline Extensions: Each student is entitled to one
of the homework deadline during the semester, if the student has a
valid excuse and asks for the deadline extension more than twelve
hours before the assignment is due. In the event of such a request,
the deadline will typically be extended from a Friday morning to the
following Monday morning. The definition of valid excuse
will be interpreted to include excessive workload
in other classes, travel for academic reasons or for a job interview,
personal illness, or other reasons at the professor's discretion.
- Submitting Homework: To simplify the process of distributing papers
for grading, each homework will consist of 3 problems. Each
problem must be turned in separately. In other words, each of problems 1, 2, 3 will be placed in separate piles when homework is handed in on Friday.
The student's name and netID should appear on each page they turn in.
- Returning Homework: Homework will be returned at the end of class
(usually) on Monday. Any homework not picked up in class can be picked up
from Upson 360, 10:00-12:00 and 2:00-4:00 Monday through Friday. You
will need your Cornell ID and you will not be able to pick up an assignment
for another student.
- Homework Privacy: Normally, graded homework is handed back in a
self-service stack. In other words, your homework grade is not
private. If you prefer more privacy, clearly mark HOLD at the top of
the first page of each piece of your homework;
these papers will be held for pick-up in Upson 360.
- Warning: It is unlikely that you will learn the material in the
course unless you do the homework. Those who skip a significant number of
them are likely to earn poor grades on the exams (as well as receiving a low
Prelims and Final
There will be two evening prelims and a final exam. The dates
and times are as follows.
- Prelim 1: February 25, 2010, 7:30-9 p.m., Upson B17.
- Prelim 2: April 13, 2010, 7:30-9 p.m., Upson B17.
- Final exam: May 19, 2009, 7-9:30 p.m.
- Your course grade will be based on homework, two prelims, and a
final exam. Each of these three portions of your grade will be
given a maximum weight as follows:
For each student, we will determine which of these three components
of their grade has the lowest score relative to the class average.
The weight of that component will be reduced by 10%, for that
student, so that the weights of all three components add up to 100%.
- 30% homework
- 40% prelims (20% each)
- 40% final exam.
- Grading Criteria: For the most part, you will be asked to design
algorithms for various problems. (There will not be any programming
assignments.) A complete answer consists of a clear description of an
algorithm (an English description is fine), followed by an analysis of its
running time and a proof that it works correctly. You should try to make
your algorithms as efficient as possible.
- CMS: We are using the CS course management system at http://cms.csuglab.cornell.edu/
to manage course grades. Please check your grades regularly to make sure
we are recording things properly. The system also provides some grading
- Regrade Policy: Regrade requests must be made within one week of
the time that homework or exams are returned to the class. It's not
fair to the graders to ask them to explain details of their grading scheme
for an assignment from several weeks ago. Also, this rule prevents a pileup
of such requests at the end of the semester.
- Regrade Process: If you believe your solution to a question was
correct and it was marked incorrect then you should write up an explanation
of the grading error, attach it to your homework, and bring it to the TA who
graded the question. Alternately, you can leave the homework and written
explanation with the instructor. Note that we're talking here about correct
algorithms that were treated as incorrect; in general, we will not look at
regrade requests that are simply arguing about the amount of partial credit
assigned. Regrade requests will be handled periodically in batch mode rather
- Any violation of academic integrity will be severely penalized. You are
allowed to collaborate on the homework to the extent of formulating ideas as
a group. However, you are expected to write up (and understand) the homework
on your own, and you should acknowledge the names of the students with whom
- Cornell's Code of Academic Integrity: http://www.cuinfo.cornell.edu/Academic/AIC.html
Basic Course Data
- Time and Place: Monday, Wednesday, and Friday, 9:05 to 9:55 in
Course Description (from the Catalog): Techniques used in the creation
and analysis of algorithms. Combinatorial algorithms, computational complexity,
NP-completeness, and intractable problems.
The official prerequisites for the course are CS 280/2800 and 312/3110.
- We will assume that everyone has seen the material in CS 2110, 3110, and
2800, and we will use it as necessary in 4820. This includes elementary data
structures, sorting, and basic terminology involving graphs (including the
concepts of depth-first search and breadth-first search). Some of these are
reviewed in the text.
- The lectures and homework involve the analysis of algorithms at a fairly
mathematical level. We expect everyone to be comfortable reading and writing
proofs at the level of CS 2800.
- Algorithm Design by Jon Kleinberg and Eva Tardos. This text
is available at the Campus Store.
- Note that, although this book was designed for this course, there will be
topics covered in lecture that are not in the text and there will be topics
in the text that are not covered in lecture. You are responsible for
topics covered in lecture and for any assigned reading in the text.
- The following are also useful references.
- T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms.
- A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of
- M. Garey and D. Johnson. Computers and Intractability .
- D. Kozen. The Design and Analysis of Algorithms.
- The Schedule lists topics covered in lecture
and the corresponding chapters in the text. It includes some prediction of
future lectures. This will be updated periodically during the semester.