Source code online books for professionals by professionals

Finding the minimum/maximum/median. Finding the minimum and maximum of a sequence can be found in 
linear time by a simple scan. Repeatedly finding and extracting the maximum or minimum in constant time, given 
linear-time preparation, can be done using a binary heap. It is also possible to find the kth smallest element of a 
sequence (the median for k = n/2) in linear (or expected linear) time, using the select or randomized select.  
(For more information, see Chapter 6.)
Flow and cut problems. How many units of flow can be pushed through a network with flow capacities on the edges? 
That is the max-flow problem. An equivalent problem is finding the set of edge capacities that most constrain the flow; 
this is the min-cut problem. There are several versions of these problems. For example, you could add costs to the edges 
and find the cheapest of the maximum flows. You could add a lower bound on each edge and look for a feasible flow. You 
could even add separate supplies and demands in each node. These problems are dealt with in detail in Chapter 10.
Graph coloring. Try to color the nodes of a graph so that no neighbors share a color. Now try to do this with a given 
number of colors, or even to find the lowest such number (the chromatic number of the graph). This is an NP-hard 
problem in general. If, however, you’re asked to see whether a graph is two-colorable (or bipartite), the problem 
can be solved in linear time using simple traversal. The problem of finding a clique cover is equivalent to finding an 
independent set cover, which is an identical problem to graph coloring. (See Chapter 11 for more on graph coloring.)