Exam 2 Topics
- Module 5: Dynamic Programming (Chapter 6)
- Weighted Interval Scheduling: A Recursive Procedure
- Principles of Dynamic Programming: Memoization or Iteration over Subproblems
- Segmented Least Squares: Multi-way Choices
- Subset Sums and Knapsacks: Adding a Variable
- RNA Secondary Structure: Dynamic Programming over Intervals
- Sequence Alignment
- Sequence Alignment in Linear Space via Divide and Conquer
- Shortest Paths in a Graph
- Shortest Paths and Distance Vector Protocols
- Negative Cycles in a Graph
For each of the above, what is the recurrence relationship?
- Module 6: Network Flow (Chapter 7)
- The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
- Maximum Flows and Minimum Cuts in a Network
- Choosing Good Augmenting Paths
- The Preflow-Push Maximum-Flow Algorithm (optional)
- A First Application: The Bipartite Matching Problem
- Disjoint Paths in Directed and Undirected Graphs
- Extensions to the Maximum-Flow Problem
- Survey Design
- Airline Scheduling
- Image Segmentation
- Project Selection
- Baseball Elimination
- Module 7: NP and Computational Intractability (Chapter 8)
- Polynomial-Time Reductions
- Reductions via ‚"Gadgets": The Satisfiability Problem
- Efficient Certification and the Definition of NP
- NP-Complete Problems
- Sequencing Problems
- Partitioning Problems
- Graph Coloring
For each algorithm:
- Asymptotic Order of Growth (its Big-O)
- Key point / distinguishing attribute / clever implementation