| Date | Topics | Reading |
|---|---|---|
| Tuesday, January 18 | 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, January 20 | 2: DFS in Directed Graphs,
Strong Connected Components, DAGs
(notes and handout versions) |
Chapter 3 of book |
| Tuesday, January 25 | 3: BFS, Single-source Shortest Paths
(notes and handout versions) |
Chapter 3 of book |
| Thursday, January 27 | 4: Shortest Paths with Negative Edge
Lengths
(notes and handout versions) |
Chapter 3 of Dasgupta etal book, Jeff Erickson's notes |
| Tuesday, February 1 | 5: Reductions, Recursion, Divide and
Conquer
(notes and handout versions) |
Chapter 5, Jeff Erickson's notes on recurrences |
| Thursday, February 3 | 6: Recurrences, Closest Pair, Quick Sort and Quick Selection | Jeff Erickson's notes on recurrences |
| Tuesday, February 8 | Catch up lecture | |
| Thursday, February 10 | 7: Exponentiation, Binary Search, Intro
to Dynamic Programming
(notes and handout versions) |
|
| Tuesday, February 15 | 8: Dynamic Programming: Longest
Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions) |
|
| Thursday, February 17 | 9: Dynamic Programming: Independent
Sets in Trees, Edit Distance
(notes and handout versions) |
|
| Tuesday, February 22 |
10:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and handout versions) |
|
| Thursday, February 24 | Midterm 1: 7-9pm in LMS 141 | Topics |
| Tuesday, March 1 |
11: Greedy Algorithms: Examples and Proof
Techniques
(notes and handout versions) |
|
| Thursday, March 3 |
12: Greedy Algorithms for Minimum
Spanning Tree
(notes and handout versions) |
|
| Tuesday, March 8 | 13: Introduction to Randomized Algorithms
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
| Thursday, March 10 | 14: Randomized Quick Sort and Selection
(notes and handout versions) | Lecture Notes, Jeff Erickson's notes |
| Friday, March 11 | Drop Deadline | |
| Tuesday, March 15 | 15: Hash Tables
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
| Thursday, March 17 | 16: Introduction to Network Flows
(notes and handout versions) |
|
| Tuesday, March 19-28 | Spring break | Tuesday, March 29 |
17: Ford-Fulkerson Algorithm for Maximum Flow
and Minimum Cut
(notes and handout versions) |
| Thursday, March 31 | 18: Applications of Network Flow: Disjoint Paths
and Bipartite Matchings
(notes and handout versions) |
|
| Tuesday, April 5 | 19: More Applications of Network Flow
(notes and handout versions) Even more notes |
|
| Thursday, April 7 | 20: Polynomial time Reductions
(notes and handout versions) |
|
| Tuesday, April 12 | Midterm 2: 7-9pm in SC 1404 | Topics (Updated) |
| Thursday, April 14 |
21: SAT and Definition of NP
(notes and handout versions) |
|
| Tuesday, April 19 |
22: NP-Completeness, Circuit Sat and Cook-Levin
Theorem
(notes and handout versions) |
|
| Thursday, April 21 | 23:
More NP-Complete Problems
(notes and handout versions) |
|
| Tuesday, April 26 |
24: P, NP, co-NP, Self Reductions
(notes and handout versions) |
|
| Thursday, April 28 | Catch up lecture | |
| Tuesday, May 3 |
25: Heuristics, Closing thoughts
(notes and handout versions) |
Chapter 9 |
| Wednesday, May 11 | Final Exam: 1:30-4:30 |