Introduction to Algorithms

Computer Science 482 (Spring 2004)

Basic Info:

• Monday, Wednesday, Friday 9:05-9:55 am. Olin 155.

Staff

• Instructor:
  • Jon Kleinberg, 5134 Upson Hall, 255-3600.
• Teaching Assistants:
  • Elliot Anshelevich,  5139 Upson, phone: 255-5578, email: eia2.
  • Xin Qi,  5162 Upson, phone: 255-7421, email: xq24.
  • Lars Backstrom, email: lb87.
  • Michael Connor, email: mjc52.
  • Shaddin Doghmi, email: sfd22.
  • Jonathan Peress, email: jmp62.
  • Perry Tam, emaill: mt235.
  • Matthew Wachs, email: mw223.
  • Justin Yang, email: jmy6.
• Support Staff: Bill Hogan, 4119 Upson, 254-8948, email: whh at cs.cornell.edu.

Getting in touch with us

Office hours

• Monday 1:00-2:00, Michael Connor
• Tuesday 2:00-3:00, Justin Yang
• Tuesday 3:00-4:00, Xin Qi
• Wednesday 10:10-11:10, Jon Kleinberg (5134 Upson)
• Wednesday 1:30-2:30, Perry Tam
• Wednesday 2:30-3:30 (May 19 only), Elliot Anshelevich
• Wednesday 8:00-9:00, Matthew Wachs
• Thursday 12:15-1:15, Jonathan Peress
• Thursday 3:30-4:30, Shaddin Doghmi
• Thursday 4:30-5:30, Lars Backstrom

Handouts

Handouts other than problem set solutions will be handed out in class and also available on the course home page. Problem set solutions will be available only as hardcopy; they will be handed out in lecture and extra copies 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 the ones we know about to the course home page.

• Approximate syllabus.
• Student information sheet. (Please fill out and return.)
• Some thoughts on homework in CS482.
• Problem Set 1 (due 2/6).
• Problem Set 2 (due 2/13).
• Problem Set 3 (due 2/20).
• Information and Review Questions for Prelim 1 (2/26, 7:30 PM).
• Problem Set 4 (due 3/5).
• Problem Set 5 (due 3/12).
• Problem Set 6 (due 3/19).
• Problem Set 7 (due 4/2).
• Problem Set 8 (due 4/9).
• Information and Review Questions for Prelim 2 (4/13, 7:30 PM).
• Problem Set 9 (due 4/30).
• Problem Set 10 (due 5/7).
• Information and Review Questions for Final Exam (5/20, 12 noon).

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 are also useful references.

• T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. 
• A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Computer Algorithms. 
• G. Brassard, P. Bratley. Fundamentals of Algorithmics. 
• M. Garey and D. Johnson. Computers and Intractability . 
• D. Kozen. The Design and Analysis of Algorithms. 

Prerequisites

• We will assume that everyone has seen the material in CS 211, 312, 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 the course packet.
• 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 280 and 381/481.

Prelims and Final

• Prelim 1: February 26th at 7:30 pm.
• Prelim 2: April 13th at 7:30 pm.
• Final: May 20th, 12 noon.

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.