The Gale-Shapley algorithm

Big O, Omega, and Theta

Graph algorithms
  Depth-first search
  Breadth-first search
  Bipartiteness detection
  Binary heap representation of priority queues
  UNION/FIND abstract data type
    Uptree implementation
  Topological sorting

Greedy algorithms
  Interval scheduling
  Kruskal's MST algorithm
  Using Kruskal's algorithm for finding connected components
  Huffman tree construction and Huffman codes

Dynamic Programing algorithms
  Fibonacci number calculation
  Memoization
  Recurrence equations
  Change-making with the minimum number of coins
  Weighted interval scheduling problem
  Segmented least squares problem
  Knapsack problem
  Sequence alignment 
  longest common subsequences

Divide-and-conquer algorithms
  Mergesort
  Inversion counting
  Closest-pair problem
  Polynomial evaluation
  Convolution
  Fast Fourier Transform

Network Flow
  Flow network representation with graphs
  Maximum s-t flow
  Cuts
  Augmenting path
  Ford-Fulkerson algorithm

NP-Complete Problems
  The class P
  The class EXP
  The class NP and certifiers
  Polynomial reducibility: Cook vs Karp
  CIRCUIT-SAT, the "natural" NP-complete problem
  INDEP-SET, VERTEX-COVER, SET-COVER, 3-SAT, HAM-CYCLE, DIR-HAM-CYCLE, TSP
  Reductions covered in class for the above problems.

You may be asked to give a short proof or explanation for the running time of one or more algorithms.

You will be able to write your answers on the test paper.