Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

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