CS580: Algorithm Design, Analysis, and Implementation - Fall 2004

Professor

Gopal Pandurangan (gopal@cs.purdue.edu)
Office: CS 128
Office hours: by appointment

Lectures

Tue, Thu: 1:30-2:45pm, room CS G66

Teaching Assistant

Maleq Khan (mmkhan@cs.purdue.edu)
Office: CS 143
Office hours: Tue 4.30-5.30pm, Fri 2-3pm

About this course

Welcome to the world of algorithms!! This is a graduate-level course on algorithms. The students are expected to have some knowledge of algorithms (such as O-notation, sorting, searching, trees, basic graph algorithms), data structures (such as arrays, lists, trees), discrete mathematics (comfortable with basic math concepts - sets, graphs, trees, counting), and must have a knowledge of programming. The official (undergraduate) prerequisites are CS381 (Introduction to Algorithms) and CS483 (Introduction to Theory of Computation). (Note: If you have not taken these two prerequisites or their equivalent, you cannot take this course.)

Algorithms usually don't exist in a void. They are driven by applications. Thus we will motivate topics by applications. This will highlight both the the centrality of algorithms to computer science and the diversity of application areas. We will also emphasize on techniques for designing and analyzing algorithms. The importance of understanding the techniques is very essential: they invariably prove useful when faced with the challenge of designing algorithms for new problems.

For the most part we will be interested in designing efficient algorithms (read polynomial time in a "reasonable" model of computation - a uniprocessor RAM). However, it turns out that many important problems that arise in practice may not have efficient algorithms. This will lead us to the theory of NP-completeness and to ways of getting around the inherent hardness of these problems.

Topics

  • Introduction: Mathematical concepts for Algorithm Analysis, Probability Theory.
  • Algorithm Design Techniques: Divide and Conquer, Randomization, Dynamic Programming, Greedy Algorithms, Amortized Analysis.
  • Data Structures: Balanced Search Trees, disjoint set union-find, Heaps, Hashing.
  • Graph Algorithms: Basic Algorithms, Minimum Spanning Trees, Shortest Paths, Network Flow, Matchings.
  • Lower Bounds.
  • NP-completeness.
  • Approximation Algorithms.
  • Probabilistic Algorithms.

    Lecture Notes

    Lecture 1: 1.pdf
    Lecture 2: 2.pdf
    Lecture 3: 3.pdf
    Lecture 4: 4.pdf
    Lecture 5: 5.pdf
    Lecture 6: 6.pdf
    Lecture 7: 7.pdf
    Lecture 8: 8.pdf
    Lecture 9: 9.pdf
    Lecture 10: 10.pdf
    Lecture 11: 11.pdf
    Lecture 12: 12.pdf
    Lecture 13: 13.pdf
    Lecture 14: 14.pdf
    Lecture 15: 15.pdf
    Lecture 16: 16.pdf
    Lecture 17: 17.pdf
    Lecture 18: 18.pdf
    Lecture 19: 19.pdf
    Lecture 20: 20.pdf
    Lecture 21: 21.pdf
    Lecture 22: 22.pdf
    Lecture 23: 23.pdf
    Lecture 24: 24.pdf
    Lecture 25: 25.pdf
    Lecture 26: 26.pdf
    Lecture 27: 27.pdf
    Lecture 28: 28.pdf
    Lecture 29: 29.pdf

    Textbook

    Introduction to Algorithms, second edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2001, ISBN 0-262-03293-7.
    Please note that this is the new second edition!
    Book home page; errata list.
    You might find this theoretical computer science cheat sheet (S. Seiden, SIGACT News, 27(4):52-61, 1996) to be useful for algorithmic analysis.PS or PDF.

    Grading

    There will be 5 or 6 homework assignments. (The assignments have to be done in Latex. If you are not familiar with Latex please learn as soon as possible. This is quite easy: there are tutorials on the Web and we will also provide you with a template file to get started.) Assignments will be non-collaborative i.e., you should work independently. You should refer only to the textbook, class notes, and any handouts given in class. Cheating on the non-collaborative policy of the assignments or on the exams will be taken seriously.
    There will also be a midterm and a final (with a Ph.D. qualifying exam supplement). The (tentative) split up is:
    assignments: 20%
    midterm:40%
    final: 40%

    WebCT

    We will use WebCT to turn in assignments.

    Newsgroup

    We plan to use the purdue.class.cs580 newsgroup ( on the server news.purdue.edu) for announcements and other postings. You should subscribe to this newsgroup and check it regularly. Send all general questions (such as clarifications regarding assignments etc.) to this newsgroup.