Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

course outline [pdf]
Lecture 1 (May 6): course introduction [pdf]
  • course information and overview
  • time complexity, computation model, 3-SUM
Lecture 2 (May 8): solving recurrence [pdf]
  • merge sort, master theorem, more recurrence
Lecture 3 (May 13): divide and conquer algorithms [pdf]
  • counting inversions, maximum sum subarray, median of medians
Lecture 4 (May 15): divide and conquer algorithms II [pdf]
  • closest pairs, arithmetic problems
Lecture 5 (May 20): breadth first search [pdf]
  • connectedness, BFS tree, shortest paths, bipartiteness
Lecture 6 (May 22): depth first search [pdf]
  • DFS tree, cut vertices and cut edges
Lecture 7 (May 27, 29): directed graphs [pdf]
  • BFS/DFS, strong connectivity, topological sort, strong components
Lecture 8 (June 3): greedy algorithms for scheduling problems [pdf]
  • interval scheduling, interval coloring, minimum total completion time
Lecture 9 (June 5): single source shortest paths [pdf]
  • BFS simulation, Dijkstra's algorithm
Lecture 10 (June 10): minimum spanning trees [pdf]
  • cut property, Prim's and Kruskal's algorithms
Lecture 11 (June 12, 17): dynamic programming [pdf]
  • introduction, weighted interval scheduling, subset sum and knapsack
Lecture 12 (June 17, 19): dynamic programming II [pdf]
  • longest increasing subsequence, fast algorithm
  • longest common subsequence, edit distance
Lecture 13 (June 19, 24): dynamic programming on trees [pdf]
  • independent sets, optimal binary search trees
Lecture 14 (June 24, 26): dynamic programming on graphs [pdf]
  • Bellman-Ford, negative cycles, Floyd Warshall, traveling salesman
Lecture 15 (July 3, 8): maximum flow and minimum cut [pdf]
  • flows, cuts, Ford-Fulkerson algorithm, max-flow min-cut theorem
Lecture 16 (July 10, 15): applications of max-flow min-cut [pdf]
  • disjoint paths, bipartite matching
  • baseball elimination, project selection
Lecture 17 (July 15, 17): polynomial time reductions [pdf]
  • decision problems, simple reductions, 3SAT to independent sets
Lecture 18 (July 22): NP-completeness [pdf]
  • NP, NP-completeness, Cook-Levin theorem
Lecture 19 (July 24): hard graph problems [pdf]
  • Hamiltonian cycle, graph coloring
Lecture 20 (July 29): hard partitioning problems [pdf]
  • 3-dimensional matching, subset-sum