CS 381: Introduction to the Analysis of Algorithms, Fall 2006

Professor

Gopal Pandurangan (gopal@cs.purdue.edu)
Office: LWSN 1209
Office hours: Tu, Thu 4.45-6pm.

Teaching Assistants

Topkara, Mercan (mkarahan@cs.purdue.edu)
Office: LWSN B1116H
Office hours: M 1-3 pm, W 2-4 pm

Li, Tiancheng (li83@cs.purdue.edu)
Office: LWSN B132

I do not hold office hours and will be mostly involved in grading. If you have questions, please write to me to make an appointment.

Lectures

TTh 3:00-4:15pm, HAAS G066.

About this course

Welcome to the world of algorithms!! This is an undergraduate-level course and is a must for a thorough understanding of algorithms which is of central importance in computer science. In this course we will systematically study the design and analysis of algorithms. We will first emphasize on techniques for designing and analyzing algorithms. These techniques will be illustrated with many key problems. The importance of understanding the techniques is very essential: they invariably prove useful when faced with the challenge of designing algorithms for new problems. Next we will study key data structures and some of their implementations. Algorithmic techniques + data structures will give us efficient algorithms. This will be illustrated next in the context of graph algorithms where they come together nicely. For the most part we will be interested in designing efficient algorithms. 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 --- Asymptotic Notation, Recurrences, Induction, Probability.

·  Algorithm Design Techniques:
Divide and Conquer --- MergeSort, QuickSort, selection (worst-case linear time), finding the closest pair of points.
Randomization --- Quicksort, Selection (expected linear time)
Dynamic Programming --- Matrix chain multiplication, longest common subsequence, knapsack.
Greedy --- fractional knapsack, caching.

·  Data Structures:
Binary Search Trees, Red Black Trees, Splay Trees (Concept of Amortization).
Disjoint set union-find --- union by rank and path compression techniques.
Heaps (Priority Queues) -- binary heaps, leftist heaps, applications.
Hashing --- hash functions, universal hashing, applications.

·  Graph Algorithms:
Fundamental algorithms --- Breadth-first search, Depth-first search, topological sorting, connectivity.
Minimum Spanning Trees --- Kruskal, Prim.
Shortest Paths --- Bellman-Ford, Dijkstra, Floyd Warshall.
Network Flow --- Ford Fulkerson, Edmonds Karp, applications.

·  NP-completeness --- Introduction to P and NP, Reductions.

·  Approximation Algorithms --- Vertex Cover, Set Cover, Traveling Salesman, Fully polynomial time approximation scheme.

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

Recommended

Algorithm Design by Kleinberg and Tardos (contains many applications illustrating the different algorithmic techniques).

Data Structures and Algorithm Analysis in Java by Mark Weiss (contains many different data structures and their implementations).

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.

---

Newsgroup

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