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, 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)
• Dynamic Programming
  • The three steps to a dynamic programming solution
  • Converting a recursive algorithm to a dynamic programming solution
  • Weighted Interval Scheduling
  • Segmented Least Squares
  • Subset Sum/Knapsack
  • Sequence Alignment/Edit Distance
  • Bellman-Ford
• Network Flow
  • Maximum Flow
  • Ford-Fulkerson Algorithm and running time analysis
  • Maxflow-Mincut Theorem
  • Capacity-Scaling Algorithm
  • Bipartite Matching
  • Project Selection/Strip Mining
• NP-completeness
  • The complexity class P
  • Polynomial-time reduction
  • 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, DecisionTSP
  • Proving that problems are NP-hard/NP-complete
• Beyond NP-completeness
  • Notion of an approximation algorithm for an optimization problem
  • Simple examples of approximation algorithms or hardness of approximation: Vertex Cover, 3-Coloring.