Date | Topics | Reading |
---|---|---|
Tuesday, January 15 |
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 17 |
2: DFS in Directed Graphs,
Strong Connected Components, DAGs
(notes and handout versions) Slides annotated during lecture |
Chapter 3 of book |
Discussion 1 | ||
Tuesday, January 22 |
3: BFS, Single-source Shortest Paths
(notes and handout versions) Slides annotated during lecture |
Chapter 3 of book |
Thursday, January 24 |
4: Shortest Paths with Negative Edge
Lengths
(notes and handout versions) |
Chapter 3 of Dasgupta etal book, Jeff Erickson's notes |
Discussion 2 | ||
Tuesday, January 29 |
5: Reductions, Recursion, Divide and
Conquer
(notes and handout versions) |
Chapter 5, Jeff Erickson's notes on recurrences |
Thursday, January 31 |
6: Recurrences, Closest Pair, Quick Sort and Quick
Selection (notes and handout versions) |
Jeff Erickson's notes on recurrences |
Discussion 3 | ||
Tuesday, February 5 |
Catch up lecture | |
Thursday, February 7 |
7: Exponentiation, Binary Search, Intro
to Dynamic Programming
(notes and handout versions) |
|
Discussion 4 | ||
Tuesday, February 12 |
8:
Dynamic Programming: Longest
Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions) |
|
Thursday, February 14 |
9:
Dynamic Programming: Independent
Sets in Trees, Edit Distance
(notes and handout versions) |
|
Discussion 5 | ||
Tuesday, February 19 |
Review session:
Lecture
(notes and handout versions) |
|
---- |
Midterm 1: 7:00 PM to 9:00 PM 1EVRT 151 7:00 PM to 9:00 PM 1LMS 151 |
Topics |
Thursday, February 21 |
10:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and handout versions) |
|
Discussion 6 | ||
Tuesday, February 26 |
11: Greedy Algorithms: Examples and Proof
Techniques
(notes and handout versions) |
|
Thursday, February 28 |
12: Greedy Algorithms for Minimum
Spanning Tree
(notes and handout versions) |
|
Discussion 7 | ||
Tuesday, March 5 |
13: Introduction to Randomized Algorithms
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
Thursday, March 7 |
14: Randomized Quick Sort and Selection
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
Friday, March 8 | Drop Deadline | |
Discussion 8 | ||
Tuesday, March 12 |
15: Hash Tables
(notes and handout versions) |
Lecture Notes, Jeff Erickson's notes |
Thursday, March 14 |
16: Introduction to Network Flows (notes and handout versions) |
|
Discussion 9 | ||
March 16 - March 24 |
Spring break |
|
Tuesday, March 26 |
17:
Ford-Fulkerson Algorithm for Maximum Flow and
Minimum Cut (notes and handout versions). |
|
Thursday, March 28 |
18: Applications of Network Flow: Disjoint
Paths and Bipartite Matchings
(notes and handout versions) |
|
Discussion 10 | ||
Tuesday, April 2 |
Midterm 2: 7:00 PM to 9:00 PM 1NOYES 217 7:00 PM to 9:00 PM 1MH 103 |
Review session slides Topics |
Thursday, April 4 |
19: More Applications of Network Flow
(notes and handout versions) Even more notes |
|
Discussion 11 | ||
Tuesday, April 9 |
20: Polynomial time Reductions
(notes and handout versions) |
|
Thursday, April 11 |
21: SAT and Definition of NP
(notes and handout versions) |
|
Discussion 12 | ||
Tuesday, April 16 |
22: NP-Completeness, Circuit Sat and Cook-Levin
Theorem
(notes and handout versions) |
|
Thursday, April 18 |
23:
More NP-Complete Problems
(notes and handout versions) |
|
Discussion 13 | ||
Tuesday, April 23 |
24: P, NP, co-NP, Self Reductions
(notes and handout versions) |
|
Thursday, April 25 |
Catch up lecture | |
Discussion 14 | ||
25: Linear programming
(notes and handout versions) |
Chapter 9 | |
Discussion 15 | ||
Final exam | Topics: final topics | |
May 3, 7pm-10pm |
1DKH 114 David Kinley Hall, Room 114. |
Proof |
Conflict to final exam - you need permission from instructors to take it! | ||
May 6, 7pm-10pm |
1EB 160 English Building, Room 160. |
Proof |
Date | Topics | Reading |
---|---|---|
26: Heuristics, Closing thoughts
(notes and handout versions) |