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-4Trees, Red-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 |