Introduction to Algorithms

Computer Science 482 (Spring 2003)

Basic Info:

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

Grades

Our record on all homeworks, prelims and the final are available to inspect from the Computer Science Course Management System. To see all your recorded scores login at <http://cms.csuglab.cornell.edu> with your cornell.edu login and password.

The final has been graded out of 60 points. The mean was 43.7 with 7.2 stdev. You can see your graded final in Bill Hogan's office in 4119 Upson.

The results of the final, and the final grades will be available through the same system early next week.

Staff

Instructors:
- Jon Kleinberg, 5134 Upson Hall, 255-3600. email: kleinber@cs.cornell.edu
- Éva Tardos 4126 Upson hall, 255-0984. email eva@cs.cornell.edu
Teaching Assistants:
- Ara Hayrapetyan, 5162 Upson, phone: 255-7421, email: ara AT cs.cornell.edu.
- Ashwin Machanavajjhala, 4162 Upson, phone: 255-2219, email: mvnak AT cs.cornell.edu.
- Steven Baker, email: sdb22 AT cornell.edu
- Bowei Du, email bd39 AT cornell.edu
- Ariful Gani, email aag24 AT cornell.edu
- Omar Khan, email: ohk2 AT cornell.edu
- Brian Kulis, email: bjk24 AT cornell.edu
- Henry Lin, email hcl5 AT cornell.edu
- Matthew Piotrowski, email mtp22 AT cornell.edu
- Justin Yang, email: jmy6 AT cornell.edu
Support Staff: Esha Molette, 4119 Upson, 254-8948, email: esha@cs.cornell.edu .

Getting in touch with us

To reach us electronically, please mail the course account cs482@cs.cornell.edu.

Office hours for study week and during finals.

Monday, May 5th 1-2	Steve Baker	Upson 328 C
Tuesday, May 6th 3-4	Justin Yang	Upson 328 C
Wednesday, May 7th 3-4	Brian Kulis	Upson 328 C
Thursday, May 8th 3-4	Bowei Du	Upson 328 C
Friday, May 9th 2-3	Matt Piotrowski	Upson 328 C
Friday, May 9th 3-4	Ariful Gani	Upson 328 C
Monday, May 12th 2-3	Henry Lin	Upson 205
Monday, May 12th 3-4	Ara Hayrapetyan	Upson 205
Tuesday, May 13th 1-2	Eva Tardos	Upson 205
Tuesday, May 13th 2-3	Ashwin Machanavajjhala	Upson 205
Tuesday, May 13th 3-4	Omar Khan	Upson 205

Handouts

We will post copies of problem sets to the course home page. Extra copies of solutions will be kept in hardcopy in 303 Upson, and on the racks outside. Leftover graded homeworks are in Upson 303 for those who filled out the information sheet.

Let us know if you find errors in the course packet.

Student Information Sheet and Waiver.

Approximate Syllabus.

Some Thoughts on 482 Homework.

Please hand in each problem on a separate sheet with your name written in each sheet.

Problem Set 1 was due in class Friday, January 31st. Solutions are available outside 303 Upson. Here are some comments from the graders. The homeworks was graded out of 30 points, with a mean of 23, and a stdev of 6.1.

Problem Set 2 was due in class Friday, February 7th. You can download it here in pdf formats also. Solutions are available outside 303 Upson. Here are some comments from the graders on problems 1 and 2, and here are some comments on problem 3. The homeworks was graded out of 30 points, with a mean of 21.5, and a stdev of 6.5.

Problem Set 3 was due in class Friday, February 14th. You can download it here in pdf formats. Solutions are available outside 303 Upson. Here are some comments from the graders for all three questions. Example fixed on 2/19/03 why dynamic programming with subproblems using first i days does not work. The homework was graded out of 30 points, with a mean of 21.5, and a stdev of 7.7.

This prelim handout contains information on Prelim 1, on the review session Monday night, and has some suggested practice questions.

Graded prelims were distributed in class on Wednesday, February 26th. Solutions, and graders comments are available outside 303 Upson. If you did not pick up your prelim in class, it can be picked up in Upson 303 for those who filled out the information sheet. The prelim was graded out of 40 points with a mean of 33 points, with 5.3 stdev

Problem Set 4 was due in class Friday, February 28th. You can also download it here if you prefer pdf format. Solutions are available outside 303 Upson. The homework was graded out of 10 points, with a mean of 7.1, and a stdev of 3.8.

Problem Set 5 was due in class Friday, March 7th. You can also download it here if you prefer pdf format. Solutions are available outside 303 Upson. Here are some comments from the graders for all three questions (or you can click here for pdf format). The homework was graded out of 30 points, with a mean of 21.9, and a stdev of 10.5.

Problem Set 6 was due in class Friday, March 14th. You can also download it here if you prefer pdf format. Here are some comments from the graders for all three questions (or you can click here for pdf format). The homework was graded out of 30 points, with a mean of 20.4, and a stdev of 10.0.

Problem Set 7 was due in class Friday, March 28th. You can also download it here if you prefer pdf format. Here are some comments from the graders for all three questions (or you can click here for pdf format). The homework was graded out of 30 points, with a mean of 21.9, and a stdev of 10.8.

Problem Set 8 was due in class Friday, April 4th. You can also download it here if you prefer pdf format. Here are the solutions (or in pdf format). Students had the basic idea of both problems, and there were no common mistakes. The homework was graded out of 20 points, with a mean of 15, and a stdev of 6.1.

The handout on the NP-completeness from the coloring problem is available on the racks in front on Upson 303.

This prelim handout contains information on Prelim 2, on the review session Sunday night, and has some suggested practice questions.

Graded prelims were distributed in class on Friday, April 11th. Solutions are available outside 303 Upson. Here are the grades' comments in ps or in pdf formats. If you did not pick up your prelim in class, it can be picked up in Upson 4119 from Bill Hogan. The prelim was graded out of 40 points with a mean of 32.5 points, with 6.9 stdev.

Problem Set 9 was due in class Friday, April 18th. You can also download it here if you prefer pdf format. The homework will be graded out of 10 points. The homework was graded out of 10 points. The mean was 7.3 points, with 3.5 stdev. Here are comments from the graders (also in pdf format).

Problem Set 10 was due in class Friday, April 25th. You can also download it here if you prefer pdf format. The homework was be graded out of 30 points. The mean was 20.3 points, with 9.6 stdev. Here are comments from the graders (also in pdf format).

Problem Set 11 was due in class Friday, May 2nd. You can also download it here if you prefer pdf format. The homework was be graded out of 30 points. The mean was 23.1 points, with 20 stdev. Here are the solutions in ps or pdf formats. Here are comments from the graders (also in pdf format).

This final handout contains information on the final, and has some suggested practice questions.

The final has been graded out of 60 points. The mean was 43.7 with 7.2 stdev.

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

The official prerequisites for the course are CS 280, 312, and 381/481.

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 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 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: Thursday, February 20th at 7:30 pm.
Prelim 2: Tuesday, April 8th at 7:30 pm.
Final: Wednesday, May 14th, 9-11:30 am.

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

Grading Policy

Student's course grade will roughly depend 30% on homeworks, 20-20% on the two prelims, and 30% on the final. However, other factor will also be taken into account. All homeworks will be counted (we do not drop any homework score).

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.