Week 1 | Graphs |
| Monday 7/14 |
Discuss Syllabus and Course Goals, Mathematics Review, and Graph
Basics |
|
| Tuesday 7/15 |
Graph Basics (cont), BFS, DFS (intro) |
Homework 1 out |
| Wednesday 7/16 |
DFS, and Implementations. |
|
| Thursday 7/17 |
DFS Numbering and Connected/Strongly Connected Components |
|
| Friday 7/18 |
Topological Ordering and DAGs |
|
Week 2 | Greedy Algorithms |
| Monday 7/21 |
What Makes a Greedy Algorithm and Interval Scheduling |
Homework 2 out |
| Tuesday 7/22 |
Review Homework 1 and Dijkstra's Shortest Paths |
Homework 1 due, solution out |
| Wednesday 7/23 |
More on Dijkstra and Minimum Spanning Trees |
|
| Thursday 7/24 |
Minimum Spanning Trees |
|
| Friday 7/25 |
Huffman Codes |
|
Week 3 | Divide and Conquer and Dynamic Programming |
| Monday 7/28 |
Divide and Conquer Basics and Mergesort |
Homework 3 out |
| Tuesday 7/29 |
Review Homework 2 and Counting Inversions |
Homework 2 due, solutions are available |
| Wednesday 7/30 |
Dynamic Programming Basics and Weighted Interval Scheduling |
|
| Thursday 7/31 |
All Pairs Shortest Paths |
|
| Friday 8/1 |
Knapsack and Sequence Alignment |
|
Week 4 | Network Flows |
| Monday 8/4 |
Review Homework 3 and all material for the midterm |
Homework 3 due, solutions are available |
| Tuesday 8/5 |
Midterm |
Solutions available |
| Wednesday 8/6 |
Flows, Max Flows, Ford-Fulkerson and its Variants |
|
| Thursday 8/7 |
Cuts, Min Cuts, and Bipartite Matching |
Homework 4 out |
| Friday 8/8 |
Applications of Max Flows and Min Cuts |
|
Week 5 | NP and NP-Completeness |
| Monday 8/11 |
P, NP, and NP-Completeness |
|
| Tuesday 8/12 |
3-SAT and Reductions (Vertex Cover, Independent Set) |
|
| Wednesday 8/13 |
Examples of Reductions (3-Color, Subset sum) |
Homework 5 out |
| Thursday 8/14 |
Review Homework 4 and Examples of Reductions (Ham-Cycle, TSP) |
Homework 4 due, solutions are available |
| Friday 8/15 |
Greedy Approximations to NP-Complete Problems (Vertex Cover,Set Cover) |
|
Week 6 | Approximation to NP-Complete Problems and Randomness in Algorithms |
| Monday 8/18 |
Randomization Definitions |
| Tuesday 8/19 |
Randomized Algorithms |
|
| Wednesday 8/20 |
Randomized Algorithms |
|
| Thursday 8/21 |
Review Homework 5 and all material for the final |
Homework 5 due |
| Friday 8/22 |
Final Exam |
|