CSE 421 Midterm
Reading Assignment for this week
Read Chapter 6 of Kleinberg & Tardos
Midterm
Friday, Feb 11, in class. This will be open book and
open notes.
Review session:
Will be Thursday, Feb 10, 4:35 p.m. in Loew 102.
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
- Min Spanning Trees, Shortest Paths and Priority Queues
- Greedy Algorithms
- Two methods for proving optimality
- Exchange Arguments
- 'Greedy Stays Ahead'
- Interval Scheduling
- Scheduling to Minimize Lateness
- Belady's Algorithm
- Greedy Graph Algorithms
- Dynamic Programming
- Three steps to dynamic programming
- One dimensional problems: Fibonacci, Weighted Interval Scheduling, Segmented Least-Squares
- Two dimensional problems: Knapsack/Subset Sum, Sequence Alignment/Edit Distance
- One dimensional splitting problems: RNA Secondary Structure
- Bellman-Ford
- Ideas for solution reconstruction and saving space