February  
Tuesday  3 
Lecture 1 Introduction, Analysis of algorithms, insertion sort. Reading: Chapter 1, 2.1, 2.2. 
Register Online PS1 Out 

Thursday  5 
Lecture 2 Asymptotic notation. Recurrences: substitution, iteration, recursion trees, master method, integer multiplication. Reading: Chapters 3 and 4, excluding Section 4.4. 

Friday  6  Recitation 1 Recurrences, sloppiness, AkraBazzi. Reading: AkraBazzi Handout. 

Tuesday  10 
Lecture 3 Divide and conquer: merge sort, binary search, powering a number, computing Fibonacci numbers, Strassen's algorithm. Reading: 2.3. 28.2, and 30.1 

Thursday  12 
Lecture 4 Quicksort, randomized algorithms. Reading: 5.15.3; Chapter 7. 

Friday  13  Recitation 2 Randomized quicksort highprobability analysis, Divide and Conquer examples. 
PS1 Due PS2 Out 

Tuesday  17 
No Lecture 

Thursday  19 
Lecture 5 Median and order statistics. Reading: Chapter 9 

Friday  20  Recitation 3 Sorting, heapsort, priority queues, applications of median. Reading: Chapter 6 

Tuesday  24 
Lecture 6 Sorting Lower Bounds, Linear time sorting, counting sort, radix sort. Reading: 8.18.3 
PS2 Due PS3 Out 

Thursday  26 
Lecture 7 Computational Number Theory. Reading: 31.131.5 

Friday  27  Recitation 4 Bucket Sort. Polynomial Identity Testing. 

March  
Tuesday  2 
Lecture 8 Computational Number Theory, RSA, Probabilistic Algorithms, Primality. Reading: 31.731.8. 

Thursday  4 
Lecture 9 Fast Fourier Transforms Reading: 30.130.2 

Friday  5  Recitation 5 Computational Number Theory and FFT 
PS3 Due 

Tuesday  9  InClass Quiz Review  
Wednesday  10 
Quiz 1 7:309:30 PM, Room 2190 

Thursday  11 
Lecture 10 Hashing Reading: 11.111.3 
PS4 Out  
Friday  12 
Recitation 6 Perfect Hashing. 

Tuesday  16 
Lecture 11 BSTs, BTrees and 23 Trees Reading: 12.112.3, 18.118.2 

Thursday  18 
Lecture 12 Skip Lists Reading: Possible Handout 

Friday  19 
Recitation 7 Augmenting Data Structures Reading: Chapter 14 
PS4 Due PS5 Out 

MonFri  2226 
Spring Break 

Tuesday  30 
Lecture 13 Computational Geometry, Range Queries. Reading: 33.133.2. 

April  
Thursday  1 
Lecture 14 Amortized analysis: table doubling, potential method. Reading: Chapter 17. 

Friday  2  Recitation 8 Amortized Data Structures, UnionFind Reading: Chapter 17. 
PS5 Due PS6 Out 

Tuesday  6 
Lecture 15 Dynamic programming: optimal binary search trees, longest common subsequence. Reading: Chapter 15. 

Thursday  8 
Lecture 16 Graphs and Greedy algorithms: minimumspanning trees, Prim's and Kruskal's algorithms. Reading: 16.116.3, Chapter 23. 

Friday  9  Recitation 9 Greedy vs. Dynamic Programming. 

Tuesday  13 
Lecture 17 Shortest Paths: Dijkstra's Algorithm, BreadthFirst Search Reading: 22.122.3, pages 580587, 24.3 

Thursday  15 
Lecture 18 Shortest Paths: BellmanFord Reading: 24.124.2, 24.424.5 

Friday  16  Recitation 10 Quiz 2 Review 
PS6 Due  
Tuesday  20 
No Lecture: Patriot's Day 

Wednesday  21  Evening Quiz 2  
Thursday  22 
Lecture 19 Graph algorithms: allpairs shortest paths, matrix multiplication, FloydWarshall algorithm, difference constraints. Reading: 25.125.2. 
Drop Day  
Friday  23  Recitation 11 Graph Algorithm Review Reading: 26.3 
PS7 Out  
Tuesday  27 
Lecture 20 Complexity: P vs. NP, efficient verification. Reading: 34.134.2. 

Thursday  29  Lecture 21 NPCompleteness, Polynomialtime reductions. Reading: 34.334.5. 

Friday  30  Recitation 12 NPCompleteness, Approximation Algorithms. 

May  
Tuesday  4 
Lecture 22 NPCompleteness, Approximation Algorithms. Reading: 35.1. 

Thursday  6 
Lecture 23 Network Flow, MaxFlow MinCut Theorem, FordFulkerson Reading: 26.126.1 

Friday  7  Recitation 13 Matching algorithms. Hard Problems. Reading: 26.3 
PS7 Due Practice PS8 Out 

Tuesday  11 
Lecture 24 Floating Point Arithmetic Guest Lecturer: Alan Edelman 

Thursday  13 
Lecture 25 Folding and Unfolding in Computational Geometry 

Monday  17  Final Exam Johnson (Ice Rink), 912am 