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, Akra-Bazzi. Reading: Akra-Bazzi 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.1-5.3; Chapter 7. |
||
Friday | 13 | Recitation 2 Randomized quicksort high-probability 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.1-8.3 |
PS2 Due PS3 Out |
|
Thursday | 26 |
Lecture 7 Computational Number Theory. Reading: 31.1-31.5 |
||
Friday | 27 | Recitation 4 Bucket Sort. Polynomial Identity Testing. |
||
March | ||||
Tuesday | 2 |
Lecture 8 Computational Number Theory, RSA, Probabilistic Algorithms, Primality. Reading: 31.7-31.8. |
||
Thursday | 4 |
Lecture 9 Fast Fourier Transforms Reading: 30.1-30.2 |
||
Friday | 5 | Recitation 5 Computational Number Theory and FFT |
PS3 Due |
|
Tuesday | 9 | In-Class Quiz Review | ||
Wednesday | 10 |
Quiz 1 7:30-9:30 PM, Room 2-190 |
||
Thursday | 11 |
Lecture 10 Hashing Reading: 11.1-11.3 |
PS4 Out | |
Friday | 12 |
Recitation 6 Perfect Hashing. |
||
Tuesday | 16 |
Lecture 11 BSTs, B-Trees and 2-3 Trees Reading: 12.1-12.3, 18.1-18.2 |
||
Thursday | 18 |
Lecture 12 Skip Lists Reading: Possible Handout |
||
Friday | 19 |
Recitation 7 Augmenting Data Structures Reading: Chapter 14 |
PS4 Due PS5 Out |
|
Mon-Fri | 22-26 |
Spring Break |
||
Tuesday | 30 |
Lecture 13 Computational Geometry, Range Queries. Reading: 33.1-33.2. |
||
April | ||||
Thursday | 1 |
Lecture 14 Amortized analysis: table doubling, potential method. Reading: Chapter 17. |
||
Friday | 2 | Recitation 8 Amortized Data Structures, Union-Find 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: minimum-spanning trees, Prim's and Kruskal's algorithms. Reading: 16.1-16.3, Chapter 23. |
||
Friday | 9 | Recitation 9 Greedy vs. Dynamic Programming. |
||
Tuesday | 13 |
Lecture 17 Shortest Paths: Dijkstra's Algorithm, Breadth-First Search Reading: 22.1-22.3, pages 580-587, 24.3 |
||
Thursday | 15 |
Lecture 18 Shortest Paths: Bellman-Ford Reading: 24.1-24.2, 24.4-24.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: all-pairs shortest paths, matrix multiplication, Floyd-Warshall algorithm, difference constraints. Reading: 25.1-25.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.1-34.2. |
||
Thursday | 29 | Lecture 21 NP-Completeness, Polynomial-time reductions. Reading: 34.3-34.5. |
||
Friday | 30 | Recitation 12 NP-Completeness, Approximation Algorithms. |
||
May | ||||
Tuesday | 4 |
Lecture 22 NP-Completeness, Approximation Algorithms. Reading: 35.1. |
||
Thursday | 6 |
Lecture 23 Network Flow, Max-Flow Min-Cut Theorem, Ford-Fulkerson Reading: 26.1-26.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), 9-12am |