Source code online books for professionals by professionals

n–1, and the way to solve it for n is to either (1) see that all nodes have degrees greater than or equal to k (we’re done!) 
or (2) find a single node to remove and solve the rest (by the induction hypothesis). It turns out that you can remove 
any node you like that has a degree smaller than k, because it could never be part of a solution. (This is a bit like the 
permutation problem—if it’s necessary to remove a node, just go ahead and remove it.)
Hint for bonus question: Note that d/2 is the ratio of edges to nodes (in the full graph), and as long as you delete nodes 
with a degree of less than or equal to d/2, that ratio (for remaining subgraph) will not decrease. Just keep deleting 
until you hit this limit. The remaining graph has a nonzero edge-to-node ratio (because it’s at least as great as for the 
original), so it must be non-empty. Also, because we couldn’t remove any more nodes, each node has a degree greater 
than d/2 (that is, we’ve removed all nodes with smaller degrees).
4-4. Although there are many ways of showing that there can be only two central nodes, the easiest way is, perhaps, 
to construct the algorithm first (using induction) and then use that to complete the proof. The base cases for  
V = 0, 1, or 2 are quite easy—the available nodes are all central. Beyond that, we want to reduce the problem from V 
to V – 1. It turns out that we can do that by removing a leaf node. For V > 2, no leaf node can be central (its neighbor 
will always be “more central” because its longest distance will be lower), so we can just remove it and forget about 
it. The algorithm follows directly: keep removing leaves (possibly once again implemented by maintaining  
degrees/counts) until all remaining nodes are equally central. It should now be quite obvious that this occurs when 
V is at most 2.
4-5. This is a bit like topological sorting, except that we may have cycles, so there’s no guarantee we’ll have nodes 
with an in-degree of zero. This is, in fact, equivalent to finding a directed Hamiltonian path, which may not even 
exist in a general graph (and finding out is really hard; see Chapter 11), but for a complete graph with oriented 
edges (what is actually called a tournament in graph theory), such a path (that is, one that visits each node 
once, following the directions of the edges) will always exist. We can do a single-element reduction directly—we 
remove a node and order the rest (which is OK by inductive hypothesis; the base case is trivial). The question now 
becomes whether (and how) we can insert this last node, or knight. The easiest way to see that this is possible is 
to simply insert the knight before the first opponent he (or she) defeated (if there is such an opponent; otherwise, 
place him last). Because we’re choosing the first one, the knight before must have defeated him, so we’re 
preserving the desired type of ordering.

---

Appendix d 
■
 Hints for exercises
277
4-6. This shows how important it is to pay attention to detail when doing induction. The argument breaks down for 
n=2. Even though the inductive hypothesis is true for n–1 (the base case, n=1), in this case there is no overlap between 
the two sets, so the inductive step breaks down! Note that if you could somehow show that any two horses had the 
same color (that is, set the base case to n=2), then the induction would (obviously) be valid.
4-7. The point isn’t that it should work for any tree with n–1 leaves, because we had already assumed that to be the 
case. The important thing is that the argument hold for any tree with n leaves, and it does. No matter which tree 
with n leaves you choose, you can delete a leaf and its parent and construct a valid binary tree with n–1 leaves and 
n–2 internal nodes.
4-8. This is just a matter of applying the rules directly.
4-9. Once we get down to a single person (if we ever do), we know that this person couldn’t have been pointing to 
anyone else, or that other person would not have been removed. Therefore, he (or she) must be pointing to himself 
(or, rather, his own chair).
4-10. A quick glance at the code should tell you that this is the handshake recurrence (with the construction of B 
taking up linear time in each call).
4-11. Try sorting sequences (of “digits”). Use counting sort as a subroutine, with a parameter telling you which digit to 
sort by. Then just loop over the digits from the last to the first, and sort your numbers (sequences) once for each digit. 
(Note: You could use induction over the digits to prove radix sort correct.)
4-12. Figure out how big each interval (value range) must be. You can then divide each value by this number, rounding 
down, to find out which bucket to place it in.
4-13. We assume (as discussed in Chapter 2) that we can use constant-time operations on numbers that are large 
enough to address the entire data set, and that includes d
i
. So, first, find these counts for all strings, adding them as a 
separate “digit.” You can then use counting sort to sort the numbers by this new digit, for a total running time so far of  
Q(∑d