Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

Course outline [pdf]
Lecture 1 (Jan 10): course introduction [pdf] [one]
  • course information and overview
  • time complexity, computation model, 3-SUM
Lecture 2 (Jan 12): solving recurrence [pdf] [one]
  • merge sort, master theorem, more recurrence
Lecture 3 (Jan 17): divide and conquer [pdf] [one]
  • inversion pairs, maximum sum subarray, median of medians
Lecture 4 (Jan 19): divide and conquer II [pdf] [one]
  • closest pair, arithmetic problems
Lecture 5 (Jan 24): breadth first search [pdf] [one]
  • graph connectivity, BFS tree, shortest path, bipartite graphs
Lecture 6 (Jan 26): depth first search [pdf] [one]
  • DFS tree, cut vertices and cut edges
Lecture 7 (Jan 31, Feb 2): directed graphs [pdf] [one]
  • strong connectivity, topological sort, strongly connected components
Lecture 8 (Feb 7): greedy algorithms [pdf] [one]
  • scheduling problems
Lecture 9 (Feb 9): single-source shortest paths [pdf] [one]
  • BFS simulation, Dijkstra's algorithm
Lecture 10 (Feb 14): minimum spanning trees [pdf] [one]
  • cut property, Prim's and Kruskal's algorithms
Lecture 11 (Feb 16,28): dynamic programming I [pdf] [one]
  • weighted interval scheduling, subset-sum and knapsack
Lecture 12 (Mar 2): dynamic programming II [pdf] [one]
  • increasing subsequence, common subsequence, edit distance
Lecture 13 (Mar 7): dynamic programming on trees [pdf] [one]
  • independent sets, optimal binary search tree
Lecture 14 (Mar 7,14): dynamic programming on graphs [pdf] [one]
  • single-source shortest paths, all-pairs shortest paths, traveling salesman problem
Lecture 15 (Mar 16,21): maximum flows and minimum cuts [pdf] [one]
  • flows, cuts, Ford-Fulkerson algorithm, max-flow min-cut theorem
Lecture 16 (Mar 23): applications of max-flows min-cuts [pdf] [one]
  • disjoint paths, bipartite matching
  • baseball elimination, project selection
Lecture 17 (Mar 28): polynomial time reductions [pdf] [one]
  • decision problems, simple reductions, 3SAT to independent set
Lecture 18 (Mar 30): NP-completeness [pdf] [one]
  • NP, NP-completeness, Cook-Levin theorem
Lecture 19 (Apr 4): hard graph problems [pdf] [one]
  • Hamiltonian cycle, graph coloring
Lecture 20 (Apr 6): hard partitioning problems [pdf] [one]
  • 3-dimensional matching, subset-sum