CSE 421 Midterm

Wednesday, Feb 12, in class. This will be open book (hard copies only) and open notes.

All the following are fair game:

Basics of Algorithm Analysis
- Complexity analysis, T, Big-O, Omega, Theta
Stable Matching
Basic Graph Algorithms
- Data Structures for graphs
- Graph Traversal Algorithms: BFS, DFS, including characterization of non-tree edges in both undirected and directed graphs and applications to connectivity, bipartiteness testing.
- Topological Sort
Greedy Algorithms
- Methods for proving optimality
  - Exchange Arguments
  - 'Greedy Stays Ahead'
  - Structural Properties
- Interval Scheduling
- Interval Partitioning
- Scheduling to Minimize Lateness
- Greedy Graph Algorithms
  - Min Spanning Trees, Shortest Paths and Priority Queues
Divide and Conquer
- Binary Search, Repeated Squaring
- Closest Pair
- Recurrences
- Fast Median analysis
- Polynomial and Integer Multiplication
  - Karatsuba's algorithm
Dynamic Programming
- Three steps to dynamic programming
- One dimensional problems: Fibonacci, Weighted Interval Scheduling, Segmented Least-Squares