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, 2-4 and red-black trees AVL, AVL, 2-4TreesRed-black,   Red-black
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: k-d trees, range searching, interval trees

August 26
Suffix arrays and trees, pattern matching

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

Sep 12, 16
Matroids, Greedy algorithms
Kleinberg-tardos 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
s-t flows, applications of maxflow
Ford-Fulkerson, FF animation, shortest path,
shortestpathanimation, applications
Nov 8, 11, 16
Intractability, NP-completeness, Polynomial time reductions
NP-completeness, 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