|
Date |
Topics |
Additional reading |
|
Tuesday,
January 20 |
1: Administrivia, overview, motivation, graph
basics, DFS
(notes and
handout versions)
|
Jeff Erickson's notes on
induction/proofs |
|
Thursday,
January 22 |
2: DFS in Directed Graphs and DAGs
(notes and
handout versions)
|
|
Discussion 1 |
|
|
Tuesday,
January 27 |
3:
Strong connected components
(notes and
handout versions)
|
|
|
Thursday,
January 29 |
4:
BFS, Single-source Shortest Paths
(notes and
handout versions)
|
Jeff Erickson's notes
|
Discussion 2 |
|
|
Tuesday,
February 3 |
5:
Shortest Paths with Negative Edge
Lengths
(notes and
handout versions)
|
Jeff Erickson's notes
on recurrences |
|
Thursday,
February 5 |
6: Reductions, Recursion, Divide and
Conquer
(notes and
handout versions) |
Jeff Erickson's notes
on recurrences |
Discussion 3 |
|
|
Tuesday,
February 10 |
7: Recurrences, Closest Pair, Quick Sort and Quick
Selection
(notes and
handout versions) |
|
|
Thursday,
February 12 |
8: Exponentiation, Binary Search, Intro
to Dynamic Programming
(notes and
handout versions) |
|
Discussion 4 |
|
|
Tuesday,
February 17 |
9:
Dynamic Programming: Longest
Increasing Subsequence, Weighted Interval Scheduling
(notes and
handout versions)
|
|
|
Thursday,
February 19 |
10:
Dynamic Programming: Independent
Sets in Trees, Edit Distance
(notes and
handout versions)
|
|
Discussion 5 |
|
|
Tuesday,
February 24
|
Review session:
Lecture
(notes and
handout versions)
|
|
---- |
Midterm 1:
7:00 PM to 9:00 PM ARMRY 101
|
Topics |
|
Thursday,
February 26 |
11:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and
handout versions)
|
|
Discussion 6 |
|
|
Tuesday,
March 3 |
12: Greedy Algorithms: Examples and Proof
Techniques
(notes and
handout versions)
|
|
|
Thursday,
March 5 |
13: Greedy Algorithms for Minimum
Spanning Tree
(notes and
handout versions)
|
|
Discussion 7 |
|
|
Tuesday,
March 10 |
14: Introduction to Randomized Algorithms
(notes and
handout versions)
|
Lecture Notes, Jeff Erickson's notes |
|
Thursday,
March 12
|
15: Randomized Quick Sort and Selection
(notes and
handout versions)
|
Lecture Notes,
Jeff Erickson's notes
|
|
Friday, March 13 |
Drop Deadline |
|
Discussion 8 |
|
|
Tuesday,
March 17
|
16: Hash Tables
(notes and
handout versions)
|
Lecture Notes, Jeff Erickson's
notes
|
|
Thursday,
March 19 |
17: Introduction to Network Flows
(notes and handout versions)
|
|
Discussion 9 |
|
|
March 21 - 29 |
Spring break
UnThanksgiving Vacation
|
|
|
|
Tuesday, March 31 |
18:
Ford-Fulkerson Algorithm for Maximum Flow and
Minimum Cut
(notes and
handout versions).
|
|
|
Thursday,
April 2 |
19: Applications of Network Flow: Disjoint
Paths and Bipartite Matchings
(notes and
handout versions)
|
|
Discussion 10 |
|
|
Tuesday,
April 7
|
Midterm 2:
7:00 PM to 9:00 PM Armory 101
|
Review session slides
Topics
|
|
Thursday,
April 9
|
20: More Applications of Network Flow
(notes and
handout versions)
Even more notes
|
|
Discussion 11 |
|
|
Tuesday,
April 14 |
21: Polynomial time Reductions
(notes and
handout versions)
|
|
|
Thursday,
April 16
|
22: SAT and Definition of NP
(notes and
handout versions)
|
|
Discussion 12 |
|
|
Tuesday,
April 21 |
23: NP-Completeness, Circuit Sat and Cook-Levin
Theorem
(notes and
handout versions)
|
|
|
Thursday,
April 23
|
24:
More NP-Complete Problems
(notes and
handout versions)
|
|
Discussion 13 |
|
|
Tuesday,
April 28 |
25: Introduction to Linear Programming
(notes and
handout versions)
|
|
|
Thursday,
April 30 |
26:
Approximation algorithms using
Linear Programming
(notes and
handout versions)
|
|
Discussion 14 |
|
|
Tuesday,
May 5 |
27: Review for the final
(notes and
handout versions)
|
|
Discussion 15 |
|
|
|
Final exam |
Topics: final topics |
|
|
Thursday, May 14th. |
May 14, 7pm-10pm |
Roger Adams Laboratory, 116
Proof.
directions.
|
|
|
|
Conflict to final exam - you need
permission from instructors to take it! |
|
May ???, 7pm-10pm |
TBD
|
|