CSE 421 Midterm

Finish reading Chapter 6 of Kleinberg & Tardos

Wednesday, Nov 7, in class. This will be open book and open notes.

Will be one on Tuesday, Nov 6, at 4:35 p.m. in TBA.

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
- Belady's Algorithm for Optimal Caching
- Greedy Graph Algorithms
  - Min Spanning Trees, Shortest Paths and Priority Queues
Divide and Conquer
- Binary Search, Repeated Squaring
- Closest Pair
- Recurrences
- Fast Median and Quicksort analyses
- Polynomial and Integer Multiplication
  - Karatsuba's algorithm
Dynamic Programming
- Three steps to dynamic programming
- One dimensional problems: Fibonacci, Weighted Interval Scheduling, Segmented Least-Squares
- Two dimensional problems: Knapsack/Subset Sum
- Ideas for solution reconstruction and saving space