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 |