Introduction to Analysis of Algorithms
Computer Science 482
Spring 2002
Problem set 10 has been graded. It can be picked up
from Esha Mollette in 4119 Upson Hall.
You may look at the your
graded final by asking Esha Mollette in 4119 Upson Hall. You may not keep the
final.
Basic Info:
- Time: Monday, Wednesday, Friday 9:05-9:55 am.
- Place: Olin 155.
Staff
- Instructors:
- Teaching Assistants:
- Siddharth Alexander, 657 Rhodes Hall, phone: 255-4195, email: alexande@cam.cornell.edu.
- Alexei Kopylov, 4139 Upson Hall, phone: 255-4934, email: kopylov@cs.cornell.edu
- Nadya Travinin, email: nt32@cornell.edu
- Misha Zatsman, email mz36@cornell.edu
- David Richardson, email dwr5@cornell.edu
- John Bicket, email jcb35@cornell.edu
- Bill McCloskey, email: btm2@cornell.edu
- Serguei Vassilvitskii, email sv39@cornell.edu
Getting in touch with us
To reach us electronically, please mail the course account
cs482@cs.cornell.edu.Office Hours for
the week of the final
Monday 3-4 |
Jon Kleinberg |
Upson 5134 |
Tuesday 3:30-4:30 |
Alexei Kopylov |
Upson 328C |
Tuesday 4:30-5:30 |
Siddharth Alexander |
Upson 328C |
Tuesday 5:30-6:30 |
Nadya Travinin |
Upson 328C |
Wednesday 11:30-12:30 |
Serguei Vassilvitskii |
Upson 328C |
Wednesday 12:30-1:30 |
Misha Zatsman |
Upson 328C |
Wednesday 1:30-2:30 |
Bill McCloskey |
Upson 328C |
Wednesday 2:30-3:30 |
Eva Tardos |
Upson 4126 |
Wednesday 3:30-4:30 |
David Richardson |
Upson 328C |
Wednesday 4:30-5:30 |
John Bicket |
Upson 328C |
Handouts
Extra copies of handouts will be kept in 303 Upson, and
on the racks outside.
Let us know if you find typographical errors in the course packet. We'll post
here the ones we know about.
Approximate Syllabus.
Please
fill out this information sheet.
Some Thoughts on 482
Homework.
Books
We will be using a
draft of a book by Jon Kleinberg and Eva Tardos, which
we developed while teaching the last few years of CS 482.
It is available at the Campus Store.
Although the book is organized around the structure of
the course, we will still cover things in lecture that
are not written down there; there are also things in the book
that we will not cover.
The content of the lectures forms the material that
you are responsible for knowing in the course.
The following useful books are on reserve in the Engineering Library:
- T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms.
McGraw-Hill, 1990.
- A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of
Computer Algorithms. Addison-Wesley, 1974.
- G. Brassard, P. Bratley. Fundamentals of Algorithmics.
Prentice-Hall, 1996.
- M. Garey and D. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.
- D. Kozen. The Design and Analysis of Algorithms.
Springer-Verlag, 1992.
Prerequisites
The official prerequisites for the course are CS 280 and 381/481.
- We will assume that everyone has seen the material in
CS 211/212 and 280,
and we will use it as necessary in 482.
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 Chapter 2 of the course packet.
- From 381/481, we mainly expect you to be familiar
with the Turing machine model.
- The lectures and homework will involve the analysis of
algorithms at a fairly mathematical level.
We expect everyone to be comfortable with reading and writing
mathematical proofs, at the level of CS 280 and 381/481.
Prelims and Final
- Prelim 1: Thursday, February 21st at 7:30 pm.
- Prelim 2: Tuesday, April 9th at 7:30 pm.
- Final: Thursday, May 9th, 12-2:30 pm.
Homework
There will be weekly homework sets, generally due on Fridays.
Homework 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 one of us and we can work
something out.)
- Most homework will consist of written questions asking
you 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.
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.
You must also list the names of everyone that you discussed
the problem set with.