Site menu:

Lecture notes

Notes will usually be posted the day before lecture.

course outline [pdf]
Lecture 1 (May 11): course introduction [pdf] [one] [pptx] [pdf]
  • course information and overview
  • time complexity, computation model, 3-SUM
Lecture 2 (May 14): solving recurrence [pdf] [one] [pptx] [pdf]
  • merge sort, master theorem, more recurrences
Lecture 3 (May 19): divide and conquer [pdf] [one] [pptx] [pdf]
  • counting inversion pairs, maximum sum subarray, median of medians
Lecture 4 (May 21): divide and conquer II [pdf] [one] [pptx] [pdf]
  • closest pair, arithmetic problems
Lecture 5 (May 26): breadth first search [pdf] [one] [pptx] [pdf]
  • graph connectivity, BFS tree, shortest path, bipartite graph
Lecture 6 (May 28): depth first search [pdf] [one] [pptx] [pdf]
  • DFS tree, cut vertices and cut edges
Lecture 7 (June 2, June 4, June 9): directed graphs [pdf] [one] [pptx] [pdf]
  • BFS/DFS, strongly connected, directed acyclic, strong components
Lecture 8 (June 11): greedy algorithms [pdf] [one] [pptx] [pdf]
  • scheduling problems
Lecture 9 (June 16): Huffman coding [pdf] [one] [pptx] [pdf]
  • optimal prefix code, Huffman's algorithm
Lecture 10 (June 18): single source shortest paths [pdf] [one] [pptx] [pdf]
  • BFS simulation, Dijkstra's algorithm
Lecture 11 (June 23): dynamic programming I [pdf] [one] [pptx] [pdf]
  • framework, weighted interval scheduling, subset-sum and knapsack
Lecture 12 (June 25,30): dynamic programming II [pdf] [one] [pptx] [pdf]
  • longest increasing subsequence, fast algorithm
  • longest common subsequence, edit distance
Lecture 13 (July 7): dynamic programming on trees [pdf] [one] [pptx] [pdf]
  • maximum independent set, optimal binary search tree
Lecture 14 (July 9): dynamic programming on graphs [pdf] [one] [pptx] [pdf]
  • Bellman-Ford, negative cycles
  • Floyd-Warshall, traveling salesman problem
Lecture 15 (July 14): bipartite matching [pdf] [one] [pptx] [pdf]
  • augmenting path algorithm
Lecture 16 (July 16): bipartite vertex cover [pdf] [one] [pptx] [pdf]
  • min-max theorem, applications and generalizations
Lecture 17 (July 21): polynomial time reductions [pdf] [one] [pptx] [pdf]
  • decision problems, simple reductions, 3SAT to independent set
Lecture 18 (July 23): polynomial time reductions [pdf] [one] [pptx] [pdf]
  • Cook-Levin theorem
Lecture 19 (July 28): hard graph problems [pdf] [one] [pptx] [pdf]
  • Hamiltonian cycle, graph coloring
Lecture 20 (July 30): hard partitioning problems [pdf] [one] [pptx] [pdf]
  • 3-dimensional matching, subset-sum