Computer Science 6820
Analysis of Algorithms
Cornell University, Fall 2013
Staff and Office Hours
- First day of class is Wednesday, August 28.
Office hours: Weds. 3:45-4:45, Thurs. 1-2
Office hours: TBA
- The Design and Analysis of Algorithms by Dexter Kozen. (Required)
- Algorithm Design by Jon Kleinberg and Eva Tardos. (Recommended)
- 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 .
The official prerequisites for the course are CS 4820 or graduate standing.
We will assume knowledge of:
Homework and Exams
discrete mathematical structures, including
graphs, trees, DAGs
basic data structures such as lists, trees,
heaps, sorting and searching
asymptotic complexity, O( ) and o( ) notation, solving recurrences
machine models and general computability
algebra: linear algebra (including eigenvalues and eigenvectors),
basic facts about polynomials over
the real and complex numbers
and the integers mod p.
probability: sample spaces, random variables,
expectation and variance, independence,
conditional probability and expectation.
- There will be problem sets roughly every two weeks. The problem
sets will generally be handed out on a Friday and will be
due the following Friday. Students will turn in the homework
- Students may work on homework in groups of up to 3 people. Each
group may turn in a single solution set that applies to all members of the
group. However, students are asked to understand each of their group's
solutions well enough to give an impromptu white-board presentation of
- There will a midterm and a final. Both of them will be take-home exams.
Dates of the take-home exams are TBA.
Discussion Forum (Piazza)
- Your course grade will be based on the homework and exams.
Weighting will be roughly as follows:
The weight of either the midterm or the final exam will be
reduced by ten percentage points. For each student, the
reduced weight will be applied to the exam on which that
student received the lower grade.
- 40% homework
- 30% midterm
- 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. Compared to CS 4820, the grading
in CS 6820 places greater emphasis on writing correct and complete proofs.
- 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.
- 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.
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
We will be using Piazza
as an online discussion forum for the class. This allows for an open
discussion of questions related to CS 6820, visible to the
instructor and the other students in the course. You will
need to register as a student in the course by visiting
Basic Course Data
- 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.
- Cornell's Code of Academic Integrity: http://www.cuinfo.cornell.edu/Academic/AIC.html
- Time and Place: Monday, Wednesday, and Friday, 2:30 to 3:20 in Upson B17.
Course Description (from the Catalog):
Methodology for developing and analyzing efficient algorithms.
Understanding the inherent complexity of natural problems via
polynomial-time algorithms, advanced data structures, randomized
algorithms, approximation algorithms, and NP-completeness. Additional
topics may include algebraic and number theoretic algorithms, circuit
lower bounds, online algorithms, or algorithmic game theory.