The Design and Analysis of Algorithms

Computer Science 681
Fall 1999

  • Instructor: Jon Kleinberg

  • TA: Alexei Kopylov

  • MWF 2:30-3:20 pm.

  • Upson 111A.

    Handouts

  • Approximate Syllabus.

  • Information Sheet. (Please fill out and return to course staff.)

  • Problem Set 4 (due in class 11/12).

    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 computational geometry, computational biology, on-line algorithm, communication networks, and the design of error-correcting codes.

    Pre-requisites

    There is no specific course pre-requisite, though knowledge of some material at the level of CS 410 will be assumed at various times. In particular: elementary data structures, basic sorting and searching, basic graph terminology, asymptotic order of growth notation, and basic recurrence relations for analyzing algorithms. These are nicely summarized near the beginnings of books such as Cormen-Leiserson-Rivest and Aho-Hopcroft-Ullman (see below). 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.

    Homework

    Homework will be assigned every 1-2 weeks; it 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 me and we can work something out.)

  • You are expected to support the answers to the homework with proofs. Much of the homework will consist of questions asking you to design algorithms for various problems. 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 do not need to implement the algorithm. You should try to make your algorithms as efficient as possible.

  • You may discuss the homework problems with other members of the class, but you must write up the assignment separately and list the names of the people with whom you discussed the assignment.

    Exams

    There will be a take-home midterm in the middle of the semester, and a take-home final at the end of the semester. Unlike the homework assignments, these must be done completely on your own.

    Grading

    The homework will count for 50% of the grade, the mid-term for 20%, and the final for 30%.

    Books

    The textbook is

    Some other useful books are