Algorithms Review List:

Dynamic Programming:##

1. Segmented Least Squares;
2. Traveling Salesman Problem;
3. RNA Secondary Strucure;
4. Sequence Alignment & Linear Space Improvement;
5. Shortest Path with negative weight edges;
6. Shortest Path with negative cycles;

Network Flows##

1. Ford-Fulkerson;
2. Min Cut = Max Flow;
3. Choosing Augmenting Path: Capacity Scaling;
   (Preflow-Push Algorithm)
4. Network Flow application: Bipartite Matching;
   O(mC): If C is not large
   O(m^2logC) with scaling: is C is large.
   in bipartite C==n, O(mn) works fine.
5. Network Flow application: Disjoint Path;
   max number of edge-disjoint s-t path == max value of s-t flow == min number of edges to be removal for disconnection between s-t;
6. Project Selection;
7. Baseball Elimination;

Intractable Problems Reductions##

1. NP Completeness
2. (to be cont...)