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