wk  Date  Topics  HW/Quizzes 
WEEK 1  
M  May 16  Course Overview Complexity of Algorithms [Review  Slides] 
HW1: Amortized Dictionary
Due: May 22 Rec. 1 Slides 
Tu  May 17  Amortized Analysis
[Complexity  Amortized] 

W  May 18  Solving divideandconquer recurrences
[Notes ] 

Th  May 19  Lower Bound Mergesort and Quicksort [Notes  Slides] 
Rec. 2 Slides Quiz 1 Solution 
F  May 20  Making Change, 01 Knapsack [Notes  Slides] 
HW1: Theory Solution 
WEEK 2  
M  May 23  Matrix Chain Multiplication [Slides] 
HW2: Edit Distance
Due: May 29 Rec. 3 Slides 
Tu  May 24  BST, AVL trees [Notes  Slides] 

W  May 25  AVL and Splay Trees [Slides]  
Th  May 26  Heaps, Treaps and Binomial Heaps [Notes ] 
Rec. 4 Slides Quiz 2 Solution 
F  May 27  Tries [ Notes  Slides ] 
HW2: Theory Solution 
WEEK 3  
M  May 30  Memorial Day No Classes 
HW3: Boggle
Due: June 05 
Tu  May 31  BTrees, Redblack trees
[ Slides ] 

W  June 01  Game trees [ Slides ]  
Th  June 02  Huffman coding LZW algorithm
[Notes  Slides] 
Rec. 5 Slides
Quiz 3 Solution 
F  June 03  BurrowsWheeler compression [ Slides ] 
HW3: Theory Solution 
WEEK 4  
M  June 06  Midterm Examsolution 
HW4: Compression Due: June 12 Rec. 6 Slides 
Tu  June 07  Finite Automaton The KMP algorithm [ Notes  Slides ] 

W  June 08  The AhoCorasick algorithm The RabinKarp algorithm [ Slides ] 

Th  June 09  Traversals Minimum Spanning Trees JarnikPrim's algorithm [ Slides  Notes ] 
Rec. 7 Slides
Quiz 4 Solution 
F  June 10  Kruskal's algorithm Disjoint Sets UnionFind [ Slides ] 
HW4: Theory Solution 
WEEK 5  
M  June 13  Dijsktra's algorithm [ Slides ] 
HW5: Graphs
Due: June 19 Rec. 8 Slides 
Tu  June 14  The BellmanFord algorithm The FloydWarshall algorithm [ Slides ] 

W  June 15  Biconnected Components [ Slides ] 

Th  June 16  Karatsuba's Algorithm [ Notes ] 
Rec. 9 Slides
Quiz 5 Solution 
F  June 17  FFT Algorithm [ Notes ] 
HW6: TBA
Due: June 24 
WEEK 6  
M  June 20  Parallel Algorithms  Rec. 10 Slides 
Tu  June 21  Parallel Algorithms  
W  June 22  Parallel Algorithms  
Th  June 23  Final Exam 