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

Professor

Gopal Pandurangan
Office: CS 174
Office hours: Mon, Wed: 2-3pm or by appointment

Lectures

Tue, Thu: 1:30-2:45pm, room UNIV 103

Teaching Assistants

Youchan Yao (yaoy)
Office: MATH 403
Office hours: Mon, Wed 10-11:20am

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, binary trees), discrete mathematics (comfortable with basic math concepts - sets, graphs, trees, counting), and must have a knowledge of programming. The official prerequisites are CS381 (Introduction to Algorithms) and CS483 (Introduction to Theory of Computation).

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. One theme that will crop up throughout the course is the use of randomness in designing (and analyzing) algorithms. Some of the most simple and effective algorithms used today in practice employ randomness or make some assumptions on the input distribution. This is an exciting aspect of modern algorithmics and will be specially emphasized.

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.

I expect to cover the following topics:
1) Basics: Asymptotic notation, Recurrences, Probability theory
2) Sorting: Randomized Quicksort, Lower bounds, linear-time sorting
3) Selection: randomized and worst-case analysis
4) Hashing: Hash tables, Universal Hashing
5) Dynamic Programming: matrix multiplication, sequence alignment
6) Amortized analysis: techniques, Splay trees
7) Disjoint-set data structures
8) Network Algorithms: shortest paths, Max Flow
9) NP-completeness
10) Approximation algorithms
11) Probabilistic algorithms
12) Number-theoretic algorithms

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;

Other references:
Data Structures and Algorithms in C++ by M.A. Weiss.
Randomized Algorithms by Raghavan and Motwani.
Introduction to Computational Molecular Biology by Setubal and Meidanis.

You might find this theoretical computer science cheat sheet (S. Seiden, SIGACT News, 27(4):52-61, 1996) to be very useful for algorithmic analysis.PS or PDF.


Grading

There will be homework assignments every other week. (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 and can consult only me, or the TA'S. 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 "problem of the week" which will be given in class every week and whose solution will be discussed the following week (in class). This is collaborative i.e., you can discuss with your friends but the solution has to be written independently (no copying). Again violations will be taken seriously. There will also be a midterm and a final (with a qualifying exam supplement). The split up is:
problems of the week: 10%
assignments: 30%
midterm:30%
final: 30%

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. Please do not send email to me for answering such questions.