Date | Topics | Reading |
---|---|---|
Tuesday, August 23 |
1: Administrivia, overview, motivation, graph
basics, DFS
(notes and handout versions) |
Chapter 0, section 1.1 and 1.2 from textbook, Jeff Erickson's notes on induction/proofs |
Thursday, August 25 |
2: DFS in Directed Graphs,
Strong Connected Components, DAGs
(notes and handout versions) Slides annotated during lecture |
Chapter 3 of book |
Tuesday, August 30 |
3: BFS, Single-source Shortest Paths
(notes and handout versions) Slides annotated during lecture |
Chapter 3 of book |
Thursday, September 1 |
4: Shortest Paths with Negative Edge
Lengths
(notes and handout versions) |
Chapter 3 of Dasgupta etal book, Jeff Erickson's notes |
Tuesday, September 6 |
5: Reductions, Recursion, Divide and
Conquer
(notes and handout versions) |
Chapter 5, Jeff Erickson's notes on recurrences |
Thursday, September 8 |
6: Recurrences, Closest Pair, Quick Sort and Quick Selection | Jeff Erickson's notes on recurrences |
Tuesday, September 13 |
Catch up lecture | |
Thursday, September 15 |
7: Exponentiation, Binary Search, Intro
to Dynamic Programming
(notes and handout versions) |
|
Tuesday, September 20 |
8: Catchup lecture | |
Thursday, September 22 |
9:
Review session:
Lecture
(notes and handout versions) |
|
Monday, September 26 |
Midterm 1: 7-9pm in 1404 SC | Topics |
Tuesday, September 27 |
Dynamic Programming: Longest
Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions) Dynamic Programming: Independent Sets in Trees, Edit Distance (notes and handout versions) |
|
Thursday, September 29 |
10:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and handout versions) |
|
Tuesday, October 4 |
11: Greedy Algorithms: Examples and Proof
Techniques
(notes and handout versions) |
|
Thursday, October 6 |
12: Greedy Algorithms for Minimum
Spanning Tree
(notes and handout versions) |
|
Tuesday, October 11 |
13: Introduction to Randomized Algorithms
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
Thursday, October 13 |
14: Randomized Quick Sort and Selection
(notes and handout versions) | Lecture Notes, Jeff Erickson's notes |
Friday, Octaber 14 | Drop Deadline | |
Tuesday, October 18 |
15: Hash Tables
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
Thursday, October 20 |
16: Introduction to Network Flows
(notes and handout versions) |
Tuesday, October 25 |
17: Ford-Fulkerson Algorithm for Maximum Flow
and Minimum Cut
(notes and handout versions) |
Thursday, October 27 |
18: Applications of Network Flow: Disjoint Paths
and Bipartite Matchings
(notes and handout versions) |
|
Tuesday, November 1 |
19: More Applications of Network Flow
(notes and handout versions) Even more notes |
|
Thursday, November 3 |
20: Polynomial time Reductions
(notes and handout versions) |
|
Tuesday, November 8 |
Midterm 2: 7-9pm in SC 1404 Review session slides | Topics |
Thursday, November 10 |
21: SAT and Definition of NP
(notes and handout versions) |
|
Tuesday, November 15 |
22: NP-Completeness, Circuit Sat and Cook-Levin
Theorem
(notes and handout versions) |
|
Thursday, November 17 |
23:
More NP-Complete Problems
(notes and handout versions) |
|
November 19-November 27 | ||
Tuesday, November 29 |
24: P, NP, co-NP, Self Reductions
(notes and handout versions) |
|
Thursday, December 1 |
Catch up lecture | |
Tuesday, December 6 |
25: Heuristics, Closing thoughts
(notes and handout versions) |
Chapter 9 |
Friday, December 9 |
Final Exam: 1:30-4:30 p.m. |