Lectures

  1. course introduction, Course Outline   (slides)

Data Structures

  1. balanced search trees (slides)   (exercises)
    rotations, AVL trees, 2-3 trees
  2. hashing (slides)   (exercises)
    hash functions & authentication, closed hash tables: linear vs. quadratic probing
  3. heaps (slides)   (exercises)
    building a heap in O(n log n) vs. O(n), indexed heaps for changing priorities
  4. disjoint-sets and union/find (slides)   (exercises)
    equivalence relations, union by size/height, path compression

Graph algorithms

  1. directed graphs (slides)   SCCs, DAGs
    strongly connected components (SCC), directed acyclic graphs (DAG), topological orderings
  2. single source shortest paths (slides) (exercises)
    3. graphs with positive edge weights, Dijkstra's algorithm
  3. minimum spanning trees (slides) (exercises)
    cut property, Prim and Kruskal's algorithms
  4. bipartite graphs (slides)   (exercises)
    matching, stable marriages (Gale-Shapley)
  5. network flows 1 (slides)   (exercises)
    flow networks, flows, residual graphs, augmenting paths, Ford-Fulkerson
  6. network flows 2 (slides) (exercises)
    max flow = min cut, finding maximal match in bipartite graphs

Dynamic Programming

  1. interval scheduling (slides)   Interval scheduling
    greedy approaches, weighted interval scheduling, DP and memoization
  2. segmented least squares (slides)   (exercises)
  3. sum of subsets, knapsack (slides)   (exercises)
  4. shortest paths in a graph with negative weights (slides)   (exercises) (B-F code in Python)
    Bellman-Ford, Floyd-Warshall

Divide and Conquer

  1. mergesort (review), closest pair of points in 2D (slides)   (exercises)
  2. Karatsuba multiplication, Master method (slides)   (exercises)
  3. determininistic quicksort and select, median-of-median-of-5's (slides)   (exercises)

Probability and information theory

  1. what do we mean by "average case"? (slides)   (exercises)
    amortization, discrete probability: random variables, linearity of expectation
  2. randomized quicksort and select (slides)   (exercises)
    expected runtimes
  3. lower bounds for comparison sorting, sorting in linear time (slides)   (exercises)
    decision trees, counting sort, bucket sort, more probability: independence
  4. data compression (slides)   data compression
    optimal prefix codes, Huffman coding, run length coding