Source code online books for professionals by professionals

Longest increasing subsequence. Find the longest subsequence of a given sequence whose elements are in 
increasing order. This can be solved in loglinear time using dynamic programming (see Chapter 8).
Matching. There are many matching problems, all of which involve linking some object to others. The problems 
discussed in this book are bipartite matching and min-cost bipartite matching (Chapter 10) and the stable marriage 
problem (Chapter 7). Bipartite matching (or maximum bipartite matching) involves finding the greatest subset of 
edges in a bipartite graph so that no two edges in the subset share a node. The min-cost version does the same but 
minimizes the sum of edge costs over this subset. The stable marriage problem is a bit different; there, all men and 
women have preference rankings of the members of the opposite sex. A stable set of marriages is characterized by the 
fact that you can’t find a pair that would rather have each other than their current mates.

---

Appendix B 
■
 List of proBLems And ALgorithms
261
Minimum spanning trees. A spanning tree is a subgraph whose edges form a tree over all the nodes of the original 
graph. A minimum spanning tree is one that minimizes the sum of edge costs. Minimum spanning trees can be found 
using Kruskal’s algorithm (Listing 7-4) or Prim’s algorithm (Listing 7-5), for example. Because the number of edges is 
fixed, a maximum spanning tree can be found by simply negating the edge weights.