Midterm Examination
CSE 417: Algorithms
The University of Washington, Seattle, Winter 2013
Date: Friday, February 15
Format: Closed-book, closed-notes. No computers, calculators, or communication devices. Written answers. There will be five problems worth 20 points each. Each problem may have several parts.
Topics: 
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
On this test you may be asked to give algorithms. You will be instructed to use either pseudocode or an English description. (You will not need to give Python code.)

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.