Source code online books for professionals by professionals

T(n–2) + 2 + 1, which eventually turns into a 
doubling sum, 1 + 2 + … + 2
i
. To get to the base case, you need to set i = n, which gives you a sum of powers up to 2
n
, 
which is Q(2
n
).
3-9. Similar to Exercise 3-8, but here the unraveling gives you 2{2T(n–2)+(n–1)}+n = 2
2
T(n–2)+2(n–1)+n. After a while, 
you end up with a rather tricky sum, which has 2
i
T(n–i) as its dominating summand. Setting i = n gives you 2
i
. (I hope 
this sketchy reasoning didn’t completely convince you; you should check it with induction.)
3-10. This is a neat one: take the logarithm on both sides, yielding log x
log y
 = log y
log x
. Now, simply note that both of 
these are equal to log x · log y. (See why?)
3-11. What’s happening outside the recursive calls is basically that the two halves of the sequence are merged together 
to a single sequence. First, let’s just assume that the sequences returned by the recursive calls have the same length 
as the arguments (that is, lft and rgt don’t change length). The while loop iterates over these, popping off elements 
until one of them is empty; this is at most linear. The reverse is also at most linear. The res list now consists of 
elements popped off from lft and rgt, and finally, the rest of the elements (in lft or rgt) are combined (linear time). 
The only thing remaining is to show that the length of the sequence returned from mergesort has the same length as 
its argument. You could do this using induction in the length of seq. (If that still seems a bit challenging, perhaps you 
could pick up some tricks in Chapter 4?)
3-12. This would give us the handshake sum inside f(n), meaning that the recurrence is now T(n) = 2T(n/2) + Q(n
2
). 
Even a basic familiarity with the master theorem should tell you that the quadratic part dominates, meaning that T(n) 
is now Q(n
2
)—drastically worse than the original!

---

Appendix d 
■
 Hints for exercises
276
Chapter 4
4-1. Try induction on E, and do the induction step “backward,” as in the internal node count example. The base 
case (E = 0 or E = 1) is trivial. Assume the formula is true for E – 1, and consider an arbitrary connected planar graph 
with E edges. Try to remove an edge, and assume (for now) that the smaller graph is still connected. Then the edge 
removal has reduced the edge count by one, and it must have merged two regions, reducing the region count by one. 
The formula holds for this, meaning that V – (E – 1) + (F – 1) = 2, which is equivalent to the formula we want to prove. 
Now see if you can tackle the case when removing an edge disconnects the graph. (Hint: You can apply the induction 
hypothesis to each of the connected components, but this counts the infinite region twice, so you must compensate 
for that.) Also try to use induction on V and F. Which version suits your tastes?
4-2. This is actually sort of a trick question, because any sequence of breaks will give you the same “running time” of 
n–1. You can show this by induction, as follows (with n=1 giving a trivial base case): the first break will give you one 
rectangle with k squares and one with n–k (where k depends on where you break). Both of these are smaller than n, 
so by strong induction, we assume that the number of breaks for each of them is k–1 and n–k–1, respectively. Adding 
these, along with the initial break, we get n–1 for the entire chocolate.
4-3. You can represent this as a graph problem, where an edge uv means that u and v know each other. You’re trying 
to find the largest subgraph (that is, with the greatest number of nodes) where each node v has a degree d(v) ³ k. Once 
again, induction comes to the rescue. The base case is n = k + 1, where you can solve the problem only if the graph 
is complete. The reduction (inductive hypothesis) is, as you might have guessed, that you can solve the problem for