CSE 421 Midterm

Midterm

Review session:

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
• Greedy Algorithms
  • Methods for proving optimality
    • Exchange Arguments
    • 'Greedy Stays Ahead'
    • Structural Properties
  • Interval Scheduling
  • Interval Partitioning
  • Scheduling to Minimize Lateness
  • Belady's Algorithm for Optimal Caching
  • Greedy Graph Algorithms
    • Min Spanning Trees, Shortest Paths and Priority Queues
• Divide and Conquer
  • Binary Search, Repeated Squaring
  • Closest Pair
  • Recurrences
  • Fast Median and Quicksort analyses
  • Polynomial and Integer Multiplication
    • Karatsuba's algorithm
• Dynamic Programming
  • Three steps to dynamic programming
  • One dimensional recursions: Fibonacci, Weighted Interval Scheduling, Segmented Least-Squares
  • Two dimensional recursions: Knapsack/Subset Sum, RNA folding, Edit Distance
  • Ideas for solution reconstruction and saving space
  • Shortest paths with negative weights (Bellman-Ford)