Source code online books for professionals by professionals

Compression and optimal decision trees. A Huffman tree is a tree whose leaves have weights (frequencies), and the 
sum of their weights multiplied by their depth is as small as possible. This makes such trees useful for constructing 
compression codes and as decision trees when a probability distribution is known for the outcomes. Huffman trees 
can be built using Huffman’s algorithm, described in Chapter 7 (Listing 7-1).
Connected and strongly connected components. An undirected graph is connected if there is a path from every 
node to every other. A directed graph is connected if its underlying undirected graph is connected. A connected 
component is a maximal subgraph that is connected. Connected components can be found using traversal algorithms 
such as DFS (Listing 5-5) or BFS (Listing 5-9), for example. If there is a (directed) path from every node to every other 
in a directed graph, it is called strongly connected. A strongly connected component (SCC) is a maximal subgraph that 
is strongly connected. SCCs can be found using Kosaraju’s algorithm (Listing 5-10).
Convex hulls. A convex hull is the minimum convex region containing a set of points in the Euclidean plane. Convex 
hulls can be found in loglinear time using the divide-and-conquer strategy (see Chapter 6).
1
Facetiously attributed to Lt. Cdr. Geordi La Forge of Star Trek: The Next Generation.

---

Appendix B 
■
 List of proBLems And ALgorithms
260