The Design and Analysis of Algorithms

Computer Science 681
Fall 2006

Instructor: Éva Tardos

4130 Upson

255-0984

eva at cs.cornell.edu

Regular Office Hours: Mondays 1:15-2:15 in 4130 Upson, or send email for an appointment

TAs: Ymir Vigfusson                                and                        Ara Hayrapetyan

4143 Upson                                                                                      4106 Upson Hall

255-3009                                                                                          255-8758

email: ymir at cs.cornell.edu                                                                email: ara at cs.cornell.edu

                                                            

Class Time: MWF 2:30-3:20 pm.

Place: UPSON 111   

The final can be picked up in 4130 Upson any time starting Wednesday, November 29.

Modified the office hour schedule for the end of the semester:

 

Thursday, Nov 30 10-11 in Upson 328C, Ara

Friday, Dec 1 11:15-12:15 in Upson 328B: Ymir

Monday, December 4th, 1-2 in Upson 4130: Eva

Tuesday, December the 5th, 10-11 in Upson 328C, Ara

Wednesday, Dec 6th 11:15-12:15 in Upson 328C: Ymir

Thursday, Dec 7th 10-11 in Upson 328C, Ara

Friday, Dec 8th, 1-2 1-2 in Upson 4130: Eva

 

Overview

CS 681 is an introductory graduate-level course on algorithms. Although we will be covering a number of current research topics in the design and analysis of algorithms, the primary focus will be on principles in algorithm design that are conceptually clean and broadly applicable. Our goal is to make the course both accessible and useful for graduate students in any area that makes use of algorithms.

Some of the broad areas we will be considering are: basic graph algorithms and data structures from a current perspective; the use of randomization; intractable problems and the design of approximation algorithms; and fundamental techniques from combinatorial optimization. We will be looking at algorithms as they appear in a variety of settings; some of these may include communication networks, on-line algorithms, computational geometry, computational biology, and the design of error-correcting codes.

Handouts and Announcements

All handouts other than homework and exams will be available on the web in pdf or html format.  It is your responsibility to check often for new postings.  Homeworks and exams will be posted on CMS. For viewing pdf files, we recommend Adobe Reader, available free of charge.

  • Approximate Syllabus updated on September 8
  • First homework was due on Wednesday, September 13th, solutions available on CMS.
  • You can pick up a copy of Lectures 2-3 of Kozen in class.
  • We will also have handouts for Lectures 8-9 and 12 of Kozen.
  • Second homework was due Tuesday morning, October 26, and is now graded. Solutions are available on CMS.
  • The third homework was due Friday, October 6, and is now graded. Solutions available on CMS.
  • The 4th homework was due in class Friday, October 20, and is now graded. Solutions available on CMS.
  • The midterm was due Monday, October 30th, it is available on CMS. The midterm requires individual work!
  • The 5th homework was due Friday, November 10th, and is now graded. Solutions available on CMS.
  • The 6th homework was due Wednesday, November 22nd. Solutions available on CMS.
  • The final will require individual work, and you have exactly one week to do it! You can start Wednesday, November 29th (and have your final due December 6th at the same time), or start later. The very latest to hand in your final is 4pm on Monday, December 11th. The final can be picked up in 4130 Upson any time starting Wednesday, November 29.

Pre-requisites

There is no specific course pre-requisite, though knowledge of some material at the level of an undergraduate algorithms course, such as CS 482 will be assumed at various times. In particular: elementary data structures and elementary algorithms, such as basic sorting and searching, basic graph terminology, and basic graph algorithms, such as graph search, asymptotic order of growth notation, and basic recurrence relations for analyzing 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.

The course will follow the same basic outline, with a similar set of topics as CS482. However, the actual overlap with 482 will be rather minimal, as all topics will be covered at a more advanced level.

CMS

We are using the course management system CMS.  We will enter everyone who preregistered, but if you did not preregister, you are probably missing.  Please login to http://cms.csuglab.cornell.edu/ and check whether you exist.  There will be a list of courses you are registered for, and Com S 681 should be one of them.  If not, please send your full name and Cornell netid to Cindy so she can register you.  You can check your grades and submit homework in CMS.  There is a help page with instructions.

Homework and Exams

There will be biweekly homework sets consisting of 3-5 problems.  You may collaborate on the homework in small groups, but you need to write down your solution alone.   Acknowledge all sources, including others in the class from whom you obtained ideas.  Please type or write legibly and staple.  There will be a significant point deduction for late homework without a good excuse.  Assignments and solutions will be posted in CMS.  Submit hardcopy in class or to Cindy by date and time indicated on the problem set, or a .pdf, .ps, .doc, or .txt file in CMS.  Do not submit Latex source.

There will be two exams, either take home or in class, open book and notes.  No collaboration is allowed on the exams. 

Graded homework and exams will be passed back in class, otherwise old homework and exams will be available from Cindy.

Approximate weights: Homework 50%, mid-term 20%, final 30%..

Books

We will use two books throughout the course. The main textbook will be

  • J. Kleinberg and E. Tardos.  Algorithm Design.  Addison-Wesley, 2005.

In the first few weeks we will follow the book:

  • D. Kozen. The Design and Analysis of Algorithms. Springer, 1992.

Some other useful books are

  • T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. McGraw-Hill, 1990.
  • A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
  • M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  • R. Tarjan. Data Structures and Network Algorithms. SIAM Regional Conference Series in Applied Mathematics 44, 1983.
  • R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  • S. Even. Graph Algorithms. Computer Science Press, 1979.
  • C. Papadimitriou, K. Steiglitz. Combinatorial Optimization -- Algorithms and Complexity. Prentice-Hall, 1982.