CSL630: Advanced Data Structures (and Algorithms) 

Reading material 
Algorithms by Dasgupta, Papadimitriou
and Vazirani Algorithm Design by Kleinberg and Tardos, Low Priced Ed. by Pearson. Pat Morin's course on Advanced Data Structures Lecture Notes on Algorithms by Jeff Erickson, UIUC Lecture Notes on Algorithms by Sariel Har Peled, UIUC 

Course Contents  
Lecture Date 
Contents 
Reading
material 
July 25, 29 
AVL, 24 and redblack trees  AVL,
AVL,
24Trees, Redblack,
Redblack 
August 1, 5 
Amortized Analysis: Splay trees,
Fibonnaci heaps 
Jeff's fibonnaci heap lecture 
August 8, 12 
Randomized: Skip lists, Treaps 

August 19, 22  Goemetric: kd trees, range
searching, interval trees 

August 26 
Suffix arrays and trees, pattern
matching 

Sept 5,9 
checking 2edge, 2node and
strong connectivity using DFS. Strongly connected components 

Sep 12, 16 
Matroids, Greedy algorithms 
Kleinbergtardos slides 
Sept 19, 23 
Divide and Conquer: DFT and FFT,
closest pair, convex hull 
slides 
Sept 26, 30, Oct 3 
Dynamic Programming 
slides, KT Slides 
Oct 10,14,17, 28, 31 
st flows, applications of maxflow 
FordFulkerson, FF animation, shortest path, shortestpathanimation, applications 
Nov 8, 11, 16 
Intractability, NPcompleteness, Polynomial time reductions 
NPcompleteness, Polytime reductions1, Polytimereductions2 
Evaluation  3 Assignments (10 each), 2 minors (20 each), Major (30). Your marks 

Visualizations 
Animations for some datastructures/algorithms can be found here 

Assignments 
One (posted 1810, 14/08, due 0800, 19/08) Two (posted 1630, 17/09, due 0800, 23/09) Three (posted 1010, 18/10, due 0800, 28/10) 

Solutions to Major 
Q1, Q2, Q3, Q4, Q5, Q6, All 