Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

course outline [pdf]
Lecture 1 (May 2): course introduction [pdf] [one]
  • course information and overview
  • time complexity, computation model, 3-SUM
Lecture 2 (May 4): solving recurrence [pdf] [one]
  • merge sort, master theorem, more recurrences
Lecture 3 (May 9): divide and conquer [pdf] [one]
  • counting inversion, maximum subarray, median of medians
Lecture 4 (May 11): divide and conquer II [pdf] [one]
  • closest pair, arithmetic problems
Lecture 5 (May 16, 18): breadth first search [pdf] [one]
  • connectivity, BFS tree, shortest path, bipartiteness
Lecture 6 (May 25): depth first search [pdf] [one]
  • DFS tree, cut vertices, cut edges
Lecture 7 (May 30, June 1): directed graphs [pdf] [one]
  • strong connectivity, directed acyclic graphs, strong components
Lecture 8 (June 6): greedy algorithms [pdf] [one]
  • scheduling problems
Lecture 9 (June 8): Huffman coding [pdf] [one]
  • optimal prefix tree
Lecture 10 (June 13): single source shortest paths [pdf] [one]
  • BFS, Dijkstra's algorithm
Lecture 11 (June 15): dynamic programming [pdf] [one]
  • introduction, weighted interval scheduling
  • subset-sum and knapsack
Lecture 12 (June 20): dynamic programming II [pdf] [one]
  • longest increasing subsequence, O(n log n) algorithm.
  • longest common subsequence, edit distance
Lecture 13 (June 22): dynamic programming on trees [pdf] [one]
  • maximum independent set, optimal binary search tree.
Lecture 14 (June 27, 29): dynamic programming on graphs [pdf] [one]
  • shortest paths, negative cycles, travelling salesman.
Lecture 15 (July 4): bipartite matching [pdf] [one]
  • augmenting path method.
Lecture 16 (July 6): bipartite vertex cover [pdf] [one]
  • min-max theorem, baseball elimination.
Lecture 17 (July 11): polynomial time reductions [pdf] [one]
  • decision problems, simple reductions, 3SAT to independent set.
Lecture 18 (July 13): NP-completeness [pdf] [one]
  • NP, NPc, Cook-Levin theorem.
Lecture 19 (July 18): hard graph problems [pdf] [one]
  • Hamiltonian cycle, graph coloring.
Lecture 20 (July 20): hard partitioning problems [pdf] [one]
  • 3-dimensional matching, subset sum.