CPS 230: Advanced Algorithms

Instructor: Kamesh Munagala 

   Fall Semester, 2010 

This course will cover algorithm design techniques at a graduate level. Topics include graph algorithms, shortest paths, amortization and search trees, randomization, hashing, fingerprinting, divide and conquer applied to FFT and matrix multiplication, network flows, matchings, stable marriage, linear programming, simplex algorithm, zero-sum gamnes, duality, and NP-Completeness. 

CPS130 or equivalent as a hard prerequisite.  If you have never studied algorithms before, please read up on greedy algorithms and dynamic programming, or take CPS130 instead of this course. 

Assignments and grades are posted via blackboard

There are two tracks for this course - Theory Track and Project Track. The project is here. You have to let me know which track you are choosing by October 19.

Slides that explain the material from the Kleinberg-Tardos book can be found here


Lectures:           Tue/Thu 1:15-2:30   (D106 LSRC)        

Office Hours:    (Kamesh) Wed  4-5pm   (D205 LSRC)

                          (Sudhanshu)  Mon 2-4pm (D229 LSRC)


Theory Track: Homeworks (30%),  MidTerm (30%), Final (40%).  

Project Track: Homeworks (15%), MidTerm (15%), Project (30%), Final (40%).

The Project Track students will be required to submit solutions to only 2 questions per homework.  You have to let me know which track you are choosing by October 19.

Quals Requirement:  To pass the algorithm qualifier requirement, you need a grade of B+ or higher in the course.

Course Textbooks: 

[KT]      Algorithm Design  by Jon Kleinberg and Eva Tardos.    (required)

[CLRS]  Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.   (optional)

[DPV]   Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.    (optional)

Slides from the [KT] book, and a pre-print of the [DPV] book are available online.

Additional Reading:  

(Lec 2)     Buckets, heaps, lists, and monotone priority queues

(Lec 2)     Fibonacci Heaps used to implement Dijkstra's and Prim's algorithms in O(m + n log n) time

(Lec 7)     The Burrows-Wheeler Transform (aka bzip on UNIX): Clever Compression using MTF

(Lec 11)    Skip Graphs -- Peer-to-peer routing using skip lists

(Lec 14)    Survey article on network applications of Bloom filters

(Lec 14)    Consistent Hashing -- One of the key ideas behind Akamai Technologies

(Lec 14)    Distributed hash tables -- Efficient data management in P2P networks

(Lec 14)    Code-division Multiple Access (CDMA) uses "hashing" for wireless communication.

(Lec 20)    Packet switching: Great application of fast table lookups, permutation networks & matchings

(Lec 20)    Stable marriages




Reading List


Aug. 31

Graph Algorithms: 

Breadth First Search, Topological Sort, 

Strongly connected components, Testing bipartiteness

Big-oh notation

KT, Chapter 3

CLRS, Chapter 22

DPV, Chapter 3,4


Sep. 2

Greedy Algorithms: 

Shortest paths: Dijkstra's Algorithm

Implementation via priority queues

KT, Chapter 4

CLRS, Chapter 23, 24

DPV, Chapter 5


Sep. 7

Spanning trees, Cut and cycle properties

Kruskal's and Prim's Algorithms

KT, Chapter 4

DPV, Chapter 5


Sep. 9

Data Structures: Union-find implementations

Amortization, Binary counting

Notes (by Edelsbrunner)

CLRS, Chapter 21


Sep. 14

Analysis of union-find with path compression

DPV, Chapter 5


Sep. 16

Search Trees: 2-4 Trees, Amortized analysis of reorder

Lossless Data Compression: Huffman Encoding

Notes (by Edelsbrunner)

DPV, Chapter 5


Sep. 21

Kraft's inequality, Optimal code-length and Entropy

Move-to-Front Coding and Competitive analysis

Original paper

Wikipedia entry


Sep. 23

Dynamic Programming: 

Memoization, Weighted Interval Seheduling,

Integer Knapsack

KT, Chapter 6,

DPV, Chapter 6

Dynamic Prog. wiki


Sep. 28

Shortest path algorithms:

Bellman's equations, Bellman-Ford algorithm

Matrix multiplication, Floyd-Warshall algorithms

KT, Chapter 6.8, 6.9

CLRS, Chapter 24, 25

DPV, Chapter 6


Sep. 30

Space-efficient Dynamic Programming: 

Floyd-Warshall, Smith-Waterman algorithms

Hirschberg's implementation via Recursion

KT, Chapter 6.6, 6.7


Oct. 5


Linearity of Expectation

Random Search Trees, Quicksort

KT, Chapter 13

CLRS, Chapter 5,7


Oct. 7

MIDTERM (Lec. 1-10)



Oct. 14

Skip Lists

Perfect Hashing

Original Paper

CLRS, Chapter 11


Oct. 19

Universal Hashing

Bloom Filters

KT, Chapter 13.6

Lecture Notes (Milterson)

Bloom filters


Oct. 21

Rabin-Karp Fingerprinting

Divide and Conquer: Recurrence Relations, 

Counting inversions, Closest pair of points

Scribe notes (MIT)

KT, Chapter 5.5

CLRS, Chapter 28

DPV, Chapter 2


Oct. 26

Polynomial multiplication by evaluations

Introduction to the Fourier Transform

The Fast Fourier Transform Algorithm

CLRS, Chapter 30

KT, Chapter 5.6

DPV, Chapter 2


Oct. 28

FFT and Signal Processing, Permutation networks

Network Flows: The Max-Flow and Min-Cut Problems

The Ford-Fulkerson Augmentation Algorithm

CLRS, Chapter 26

KT, Chapter 7

DPV, Chapter 7


Nov. 2

The Max-flow Min-cut Theorem

Capacity scaling and Edmonds-Karp Algorithms

KT, Chapter 7


Nov. 4

Applications of Max-Flow and Min-Cut:

Bipartite Matchings and Hall's Theorem, 

Disjoint Paths and Menger's Theorem 

CLRS, Chapter 26

KT, Chapter 7


Nov. 9

Circulations with Demands,

Project Scheduling, Image Segmentation

KT, Chapter 7


Nov. 11

Linear Programming: Expressing Problems as LPs

The Dual Program

Weak and Strong LP Duality

CLRS, Chapter 29

Notes (CMU)


Nov. 16

The Simplex Algorithm

Applications of Linear Programming and Duality

Shortest paths and network flows revisited 

CLRS, Chapter 29

DPV, Chapter 7

Notes (M. X. Goemans)


Nov. 18

Flows with costs,  Zero Sum Games

NP-Completeness: Easy and hard problems 

Cook-Levin Theorem, Poly-time Reductions

CLRS, Chapter 34

KT, Chapter 8,9

DPV, Chapter 7,8


Nov. 23

NP-Completeness Proofs: TSP, Subset Sum, 

Independent Set, Vertex Cover

KT, Chapter 8,9

DPV, Chapter 8



Nov. 30

Coping with NP-Completeness:

Approximation Algorithms: Knapsack, Vertex Cover

Connection to Linear Programming

KT, Chapter 11


Dec. 2

Efficient algorithms for special graphs

Fixed parameter tractability

KT, Chapter 10

Dec. 18