Date |
Topics |
Reading |
Tuesday, August 25 |
Administrivia, overview, motivation, potpourri |
Chapters 1-3 from text book, Jeff Erickson's notes on recurrences |
Thursday, August 27 |
Recursion, Divide and Conquer, Sorting, Multiplication, Recurrences |
Chapter 5, Jeff's notes on recurrences |
Tuesday, September 1 |
Recurrences, Closest Pair, Quick Sort and Quick Selection |
Chapter 5 |
Thursday, September 4 |
Finish quick selection. Exponentiation, binary search. Graph basics |
Chapter 5, Chapter 3 |
Tuesday, September 8 |
Depth First Search, Strong Components, DAGs |
Chapter 3 of text book and Chapter 3 of Dasgupta etal book. |
Thursday, September 10 |
BFS, Application to Bipartite Graphs, Single-Source Shortest Paths |
Chapter 3 of text book and Chapter 3 of Dasgupta etal book. |
Tuesday, September 15 |
Shortest Paths with Negative Lengths,
Bellman-Ford algorithm |
Chapter 3 of Dasgupta etal book |
Thursday, September 17 |
Continue last lecture |
|
Tuesday, September 22 |
Greedy Algorithms: Examples and Proof Techniques |
Chapter 4 |
Thursday, September 24 |
Greedy Algorithms of Minimum Spanning Trees. Implementation Issues |
Chapter 4 |
Tuesday, September 29 |
Catch up lecture |
|
Thursday, October 1 |
Midterm 1: 7-9pm Noyes Hall 217 |
|
Tuesday, October 6 |
Introduction to Dynamic Programming |
Chapter 6 |
Thursday, October 8 |
Weighted Interval Scheduling and Longest Increasing Subsequence |
Chapter 6 and lecture notes |
Tuesday, October 13 |
Dynamic Programming: Max Weight Indep Set in Trees, Edit Distance |
Chapter 6 and lecture notes |
Thursday, October 15 |
Dynamic Programming: All-Pairs Shortest Paths, Knapsack, TSP |
Chapter 6 and lecture notes |
Monday, October 19 |
Drop Deadline | |
Tuesday, October 20 |
Introduction to Network Flows |
Chapter 7 |
Thursday, October 22 |
Ford-Fulkerson for Maximum Flow and Minimum Cut |
Chapter 7 |
Tuesday, October 27 |
Network Flow Applications: Disjoint Paths and Bipartite Matching |
Chapter 7 |
Thursday, October 29 |
More Network Flow Applications |
Chapter 7 |
Tuesday, November 3 |
Introduction to Linear Programming |
Lecture notes, Dasgupta etal book |
Thursday, November 5 |
Midterm 2: 7-9pm Siebel 1105 and 1109 |
|
Tuesday, November 10 |
Polynomial-time Reductions |
Chapter 8 |
Thursday, November 12 |
The SAT problem and Definition of NP |
Chapter 8 |
Tuesday, November 17 |
NP-Completeness, Circuit Sat and Cook-Levin Theorem |
Chapter 8 |
Thursday, November 19 |
More NP-Complete Problems |
Chapter 8 |
Tue/Thu, November 24, 26 |
Thanksgiving Break | |
Tuesday, December 1 |
P, NP, co-NP, Self Reductions |
Chapter 8 |
Thursday, December 3 |
Flavor of Approximation Algorithms |
Lecture notes and Chapter 11 |
Tuesday, December 8 |
Heuristic methods, closing thoughts |
Chapter 9 in Dasgupta etal book |
Thursday, December 17 |
Final Exam: 1.30-4.30pm, 1404 Siebel |
|