CSE 421 Midterm Week
Reading Assignment for this week
Read Chapter 5 of Kleinberg & Tardos
Midterm
Friday, Feb 14, in class. This will be open book and
open notes.
Here is a sample midterm from a
previous quarter with a different text.
The course covered somewhat different material that year and it was closed book,
so don't take it
literally, but it will give you some idea of the kinds of questions I might
ask.
Review session:
Will be Thursday, Feb 13, 5:00 p.m. in Loew 105.
Topics:
All the following are fair game:
- Basics of Algorithm Analysis
- Complexity analysis, T, Big-O, Omega, Theta
- Recurrences
- 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, cutpoints (rough idea).
- 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
- Divide and conquer
- Main ideas and recurrences.
- Bisection, Binary search
- Repeated Squaring
- Karatsuba's Algorithm
- Basic idea behind Strassen's algorithm and Fast Fourier Transform (but not
the details)