Source code online books for professionals by professionals

The halting problem. Determine whether a given algorithm will terminate with a given input. The problem is 
undecidable (that is, unsolvable) in the general case (see Chapter 11).
Hamilton cycles/paths and TSP … and Euler tours. Several path and subgraph problems can be solved efficiently. 
If, however, you want to visit every node exactly once, you’re in trouble. Any problem involving this constraint is 
NP-hard, including finding a Hamilton cycle (visit every node once and return), a Hamilton path (visit every node 
once, without returning), or a shortest tour of a complete graph (the Traveling Salesman/Salesrep problem). The 
problems are NP-hard both for the directed and undirected case (see Chapter 11). The related problem of visiting 
every edge exactly once, though—finding a so-called Euler tour—is solvable in polynomial time (see Chapter 5). The 
TSP problem is NP-hard even for special cases such as using Euclidean distances in the plane, but it can be efficiently 
approximated to within a factor of 1.5 for this case, and for any other metric distance. Approximating the TSP problem 
in general, though, is NP-hard. (See Chapter 11 for more information.)