Lecture Schedule, Notes and Readings

Subject to Change - check page frequently
Date Day Topic (Link to Lecture Notes) Book Chapter
Jan 18  Course Intro, Karatsuba multiplication Notes: Chapters 1-5, 11, 13 and 23 of the textbook are regarded as prerequisite material for the course.
Jan 20  Th  Math Foundations: asymptotics, recurrences 1,2,3,4,5 
  Probability, Sorting and Order Statistics  
Jan 25  Probability Intro. Worst/Avg/Expected case. Quicksort 6,8 
Jan 27  Th  Avg case vs. Expected case (cont). Linearity of expectation. Randomized selection 6,10 
Feb 1  Deterministic selection. Lower bounds for comparison sorts. Counting and Bucket sort 9,10 
Feb 3  Th  Radix sort. Tail inequalities. Hashing 6,9,12 
  Data Structures  
Feb 8  Universal hashing    Quiz 1 (1/2 lecture).  12 
Feb 10  Th  Binary search trees. Red-Black trees 13,14,15 
Feb 15  Red-Black trees (cont). Skip-lists. Tries. Splay trees Lecture Notes 
  Fundamental Algorithm/Analysis Techniques  
Feb 17  Th  Amortized analysis 18 
Feb 22  Amortized analysis (cont). Dynamic Programming 18,16 
  Graph Algorithms  
Feb 24  Th  DFS, BFS, Shortest Paths 23,25 
Feb 29  Shortest Paths (cont), MST, Designing Algorithms 25,24,Lecture Notes 
Mar 2  Th  Midterm
Mar 7  Union-Find 22 
Mar 9  Th  Union-Find (cont). Flow Networks: Max Flow, Min Cut 27 
Mar 14  Max Flow (cont), Bipartite Matching 27 
Mar 16  Th  Linear Programming 25 
  Computational Complexity  
Mar 21  P, NP, and NP-Completeness 36 
Mar 23  Th  NP-Completeness (cont) 36 
Mar 28  Spring break; no classes. 
Mar 30  Th  Spring break; no classes. 
Apr 4  Approximation Algorithms 37 
Apr 6  Th  Hardness of Approximation Lecture Notes 
Apr 11  Hardness of Approx (cont)  Quiz 2 (1/2 lecture).  Lecture Notes 
  Context-Based Algorithmics  
Apr 13  Th  Context-based algorithmics. External Memory Algorithms. B-trees 19, Lecture Notes 
Apr 18  External Sorting. Synopsis Data Structures Lecture Notes 
Apr 20  Th  Synopsis Data Structures (cont). Online Algorithms Lecture Notes 
Apr 25  Parallel Algorithms 30 
Apr 27  Th  Distributed Algorithms Lecture Notes 
May 2  Cryptography and Number-theoretic algorithms 33 
May 4  Th  Summary and Overview
May 8  Final exam