Computer Science 4820
Introduction to Analysis of Algorithms
Cornell University, Spring 2012
Staff and Office Hours
Staff and Office Hours
- Add cornell.edu to any incomplete email addresses below.
|CS 4820 STAFF
Costandino Dufort Moraites
Gautam “G” Kamath
Katie Lee Meusling
Mailing lists and discussion forum
- We will be using Piazza
as an online discussion forum for the class. This allows for an open
discussion of questions related to CS 4820, visible to the
instructor and the other students in the course. You will
need to register as a student in the course by visiting
- 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 (usually) on
Friday. Students will hand in homework using
- Late Homework Policy: It is expected that homework will be turned
in on time.
Assignments can be turned in late (via email to
firstname.lastname@example.org) 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 23, 2012, 7:30-9 p.m., Olin 155 and 165.
- Prelim 2:
April 10, 2012, 7:30-9 p.m., Upson B17, 109, and 111.
- Final exam: May 16, 2012, 7:00-9:30 p.m., location TBA.
- 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.