Lecture notes
Notes will usually be posted the day before lecture.
course outline
[pdf] |
Lecture 1 (May 6): course introduction [pdf]
|
Lecture 2 (May 8): solving recurrence [pdf]
|
Lecture 3 (May 13): divide and conquer algorithms [pdf]
|
Lecture 4 (May 15): divide and conquer algorithms II [pdf]
|
Lecture 5 (May 20): breadth first search [pdf]
|
Lecture 6 (May 22): depth first search [pdf]
|
Lecture 7 (May 27, 29): directed graphs [pdf]
|
Lecture 8 (June 3): greedy algorithms for scheduling problems [pdf]
|
Lecture 9 (June 5): single source shortest paths [pdf]
|
Lecture 10 (June 10): minimum spanning trees [pdf]
|
Lecture 11 (June 12, 17): dynamic programming [pdf]
|
Lecture 12 (June 17, 19): dynamic programming II [pdf]
|
Lecture 13 (June 19, 24): dynamic programming on trees [pdf]
|
Lecture 14 (June 24, 26): dynamic programming on graphs [pdf]
|
Lecture 15 (July 3, 8): maximum flow and minimum cut [pdf]
|
Lecture 16 (July 10, 15): applications of max-flow min-cut [pdf]
|
Lecture 17 (July 15, 17): polynomial time reductions [pdf]
|
Lecture 18 (July 22): NP-completeness [pdf]
|
Lecture 19 (July 24): hard graph problems [pdf]
|
Lecture 20 (July 29): hard partitioning problems [pdf]
|