| Wednesday, January 16 |
Administrivia, overview |
Homework FAQ |
| Friday, January 18 |
Graph Search |
Sections 3.1, 3.2, 3.3 |
| Wednesday, January 23 |
DAGs and Strongly connected components |
Sections 3.5, 3.6; Chapter 3 of textbook by Dasgupta et. al. |
| Friday, January 25 |
Divide and Conquer: Sorting and Recurrences |
Sections 5.1, 5.2 |
| Wednesday, January 30 |
Continuation of previous lecture |
|
| Friday, February 1 |
Closest Pair and Multiplication |
Sections 5.4, 5.5 |
| Wednesday, February 6 |
Fast Fourier Transforms |
Section 5.6 |
| Friday, February 8 |
Introduction to Greedy Algorithms |
Sections 4.1, 4.2 |
| Wednesday, February 13 |
Minimum Spanning Trees and Data
Structures: Priority Queues and Union-Find |
Sections 4.5, 2.5, and 4.6 |
| Friday, February 15 |
Huffman Codes |
Section 4.8 |
| Wednesday, February 20 |
Dynamic Programming: Weighted Interval
Scheduling and Segmented Least Squares |
Sections 6.1, 6.2, 6.3 |
| Friday, February 22 |
Midterm I |
Chapters 1 through 5 |
| Wednesday, February 27 |
RNA secondary structure and Sequence
Alignment |
Sections 6.5, 6.6 and 6.7 |
| Friday, February 29 |
All pairs shortest path and Knapsack |
Sections 6.4, 6.8, 6.9 6.10 |
| Wednesday, March 5 |
Basic Network Flow Algorithms |
Sections 7.1, 7.2, 7.3 |
| Friday, March 7 |
Network Flows Algorithms continued (same lectures slides
as the previous lecture) |
Sections 7.1, 7.2, 7.3 |
| Wednesday, March 12 |
Applications of Network Flows |
Sections 7.5, 7.6 |
| Friday, March 14 |
Applications of Network Flows continued (previous lecture
slides) |
Sections 7.5,7.6,7.7 |
| Wednesday, March 19 |
Spring Break |
Spring Break |
| Friday, March 21 |
Spring Break |
Spring Break |
| Wednesday, March 26 |
Solving Problems with Network Flows |
Chapter Seven |
| Friday, March 28 |
Midterm |
Chapters 6 and 7 |
| Wednesday, April 2 |
Polynomial Time Reductions |
Sections 8.1,8.2 |
| Friday, April 4 |
NP Completness and Cook-Levin Theorem |
Sections 8.3,8.4 |
| Wednesday, April 9 |
More NP Complete Problems |
Sections 8.5, 8.7 |
| Friday, April 11 |
co-NP, P and NP. Introduction to
Approximation Algorithms |
Sections 8.9, 11.1 |
| Wednesday, April 16 |
Set Cover |
Section 11.3 |
| Friday, April 18 |
Pricing Method |
Section 11.4 |
| Wednesday, April 23 |
Introduction to Linear Programming |
Section 11.6 |
| Friday, April 25 |
Primal-Dual Method and LP Rounding |
Section 11.6 |
| Wednesday, April 30 |
Last Day of Class |
Last Day of Class |