Algorithms
Computer Science 6820
Cornell University, Fall 2009
Mon-Wed-Fri 2:30-3:20
306 Hollister
This is an introductory graduate-level course on algorithms,
covering both fundamental techniques and the basics of some
current research areas.
There is no specific course pre-requisite,
though knowledge of some material at the level of CS 4820 will
be assumed at various times.
In particular, it will be useful to have experience with
elementary data structures, basic sorting and searching,
basic graph terminology,
and asymptotic analysis of time and space bounds for algorithms.
It will also be helpful to have seen basic definitions of
probability (e.g. random variables and their expectations),
as well as some very basic linear algebra.
See below for more information, including the
the list of handouts,
the outline of topics,
the description of coursework,
and the
CMS site.
Course Staff
List of Handouts
- Student Information Sheet (8/28; please fill out and return).
- Homework 1 (due 09/18).
- Homework 2 (due 10/02).
- Homework 3 (due 10/09).
- Homework 4 (due 10/30).
- Homework 5 (due 11/11).
- Homework 6 (due 11/30).
- The final exam may be picked up from Amy Finch Seely in 4120 Upson between Nov. 30 and Dec. 7. You should submit your solutions to CMS within 72 hours of the time you pick up the exam. Unlike the homework, the take-home final must be done completely on your own.
Books
We will be using the book Algorithm Design (Jon Kleinberg
and Eva Tardos, Addison-Wesley, 2005; abbreviated as "KT" below),
supplemented by additional readings and papers.
Outline of Topics
Part 1: Fundamental Graph Algorithms
Part 2: Dealing with Computational Intractability
(3) NP-completeness
- P and NP: Basic definitions (KT Sec. 8.3-8.4)
- Techniques for reducing among problems (KT Sec. 8.1-8.2, 8.7)
- NP-completeness of numerical problems (KT Sec. 8.8)
Part 3: Further Algorithmic Techniques
(6) Randomized Methods
- Basics: The Union Bound and Linearity of Expectation (KT Sec. 13.3-4, and Solved Exercise 1)
- Chernoff Bounds (KT Sec 13.9-13.10)
- Randomized routing (KT Sec. 13.11)
- Geometric nearest-neighbor problems (KT Sec. 13.7)
Homework
Homework will be assigned every 1-2 weeks; it
should be handed in in lecture, at the end of class,
on the day it is due.
- Late homeworks will not receive credit.
(If a genuine emergency situation prevents you from handing
in an assignment on time, come talk to me and we can work
something out.)
- You are expected to support the answers to the
homework with proofs.
Much of the homework will consist of questions asking
you to design algorithms for various problems.
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 do not need to implement the algorithm.
You should try to make your algorithms as efficient as possible.
- You may discuss the homework problems
with other members of the class,
but you must write up the assignment separately
and list the names of the people with whom you discussed the assignment.
- You should cite any sources that you use in working on a
homework problem.
Exams
There will be an in-class midterm exam and a take-home final exam.
- Midterm: Friday, October 16, in class.
- Final exam: The final will be done as a take-home exam.
Unlike the
homework, the take-home final must be done completely on your own.
- The final exam may be picked up from Amy Finch Seely in 4120 Upson between Nov. 30 and Dec. 7. You should submit your solutions to CMS within 72 hours of the time you pick up the exam. Unlike the homework, the take-home final must be done completely on your own.
Grading
Grades on the midterm, and
the final, and the homework will be weighted as follows:
- Midterm: 20%
- Final: 30%
- Homework: 50%
Academic Integrity
You are expected to maintain the utmost level of
academic integrity in the course.
Any violation of the code of academic integrity
will be penalized severely.
You are allowed to collaborate on the homework to the extent of
formulating ideas as a group.
However, you must write up the solutions to each problem set completely on
your own, and understand what you are writing.
You must also list the names of everyone that you discussed
the problem set with, and cite any sources you used.
Collaboration is not allowed on the midterm or the take-home final.