Introduction to Analysis of Algorithms

Computer Science 482
Spring 1999

Basic Info

• Time: Monday, Wednesday, Friday 9:05-9:55 am.
• Place: Kimball B11.

Final Info

• Final on Thursday May 20th, 12:00-2:30.
• Those whose last name starts with a letter between A-R should go to room OH 155,
• Those with last names S-Z, should go to OH 165

Staff

• Instructors:
  • Jon Kleinberg, 5134 Upson Hall, 255-3600, email: kleinber@cs.cornell.edu .
  • Eva Tardos, 4105B Upson Hall, 255-0984, email: eva@cs.cornell.edu .
• Teaching Assistants:
  • Rie Ando, 4132 Upson, 255-1179, email: kubotar@cs.cornell.edu .
  • Alexandre Evfimeivski, 4132 Upson, 255-1179, email: aevf@cs.cornell.edu .
  • Chris Jeuell, email: chj2@cornell.edu .
  • Yeongwee Lee, email: yl79@cornell.edu .
  • Brian Sabino, email: bjs19@cornell.edu .
• Support Staff: Rosemary Adessa, 4105 Upson, 255-9555, email: rosemary@cs.cornell.edu .

Getting in touch with us

• To reach us electronically, please mail the course account cs482@cs.cornell.edu.
• Graded prelims and finals, and course grades are available from Rosemary Adessa in 4105 Upson.

Office Hours

Course grade

The course grade will be determined roughly as follows:

• 30% problem sets,
• 20-20% each of the two prelims
• 30% final

Homework return policy

Graded problem sets are returned in class on Fridays, or can be picked up in Upson 303 after Fridays class. If you do not want to have your problem set returned this way, please write PRiVATE RETURN ONLY on each problem, and you will have to pick up your graded problem sets in the instructors office hours (Professors Kleinberg and Tardos only, and not the TAs).

Prerequisites

The official prerequisites for the course are CS 410 and 381/481.

• We will assume that everyone has seen the material in CS 211/212, 280, and 410, and we will use it as necessary in 482. This includes elementary data structures, sorting, depth-first search, breadth-first search, and shortest paths. A good review of all these topics is given in the course textbook.
• 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 25th at 7:30 pm.
• Prelim 2: Thursday, April 15th at 7:30 pm.
• Final: Thursday, May 20th, 12-2:30 pm.

Homework

There will be weekly homework sets 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.

Books

The course textbook is

• T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

Other useful books, on reserve in the Engineering Library, are

• 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.

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.