CSE 421 Final Exam Guide

Final Exam

Review session:

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
  • Edmonds-Karp 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
  • Approximation algorithms: Vertex Cover, TSP
  • Backtracking (short answer only)
  • Heuristic approaches (short answer only)