CSE 421 Midterm
Midterm
Wednesday, Feb 12, in class. This will be open book (hard copies only) and open notes.
Topics:
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
- Dynamic Programming
- Three steps to dynamic programming
- One dimensional problems: Fibonacci, Weighted Interval Scheduling, Segmented Least-Squares