CSE 421 Final Exam Guide
Final Exam
Monday, December 10, 2:30-4:20 in class.
This will be open book and
open notes.
Here is a sample final from a
previous quarter.
Review session:
Will be Sunday, December 9, 4:00 p.m. in EE1 045.
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.
- Topological Sort
- Min Spanning Trees, Shortest Paths and Priority Queues
- Greedy Algorithms
- Methods for proving optimality
- Exchange Arguments
- 'Greedy Stays Ahead'
- Structural properties
- Interval Scheduling
- Scheduling to Minimize Lateness
- Belady's Algorithm
- Greedy Graph Algorithms
- Divide and conquer
- Main ideas and recurrences.
- Sorting
- Closest Pair
- Bisection, Binary search, Repeated Squaring
- Karatsuba's Algorithm and efficient algorithms for polynomial/integer multiplication
- Linear-time Median Finding
- 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 Dista
nce
- One dimensional splitting problems: RNA Secondary Structure
- Bellman-Ford
- Ideas for solution reconstruction and saving space
- Network Flow
- Maximum Flow
- Ford-Fulkerson Algorithm and running time analysis
- Maxflow-Mincut Theorem
- Capacity-Scaling Algorithm
- Bipartite Matching
- NP-completeness
- The complexity class P
- Polynomial-time reductions, both their definition and creating them.
- Definition of NP
- Proving that problems are in NP
- Definition of NP-hard
- Definition of NP-complete
- NP-completeness of SAT, 3-SAT, Independent Set, Clique, Vertex Cover,
Set Cover, 3-Coloring, Subset Sum, Hamiltonian Path/Cycle, TSP
- Proving that problems are NP-hard/NP-complete
- Dealing with NP-completeness (short answer only)
- Approximation algorithms: Vertex Cover, TSP
- Backtracking
- Heuristic approaches