Source code online books for professionals by professionals

i–1
 defeated K
i
, for i=2...n). Prove that it is always possible to construct such a sequence by 
designing an algorithm that builds it.
4-6.  George Pólya (the author of How to Solve It; see the “References” section) came up with the following 
entertaining (and intentionally fallacious) “proof” that all horses have the same color. If you have only a 
single horse, then there’s clearly only one color (the base case). Now we want to prove that n horses have 
the same color, under the inductive hypothesis that all sets of n–1 horses do. Consider the sets {1, 2, ... , 
n–1} and {2, 3, ... , n}. These are both of size n–1, so in each set, there is only one color. However, because 
the sets overlap, the same must be true for {1, 2, ... n}. Where’s the error in this argument?
4-7.  In the example early in the section “One, Two, Many,” where we wanted to show how many 
internal nodes a binary tree with n leaves had, instead of “building up” from n–1 to n, we started with n 
nodes and deleted one leaf and one internal node. Why was that OK?
4-8. Use the standard rules from Chapter 2 and the recurrences from Chapter 3 and show that the 
running times of the four sorting algorithms in Listings 4-1 through 4-4 are all quadratic.
4-9. In finding a maximum permutation recursively (such as in Listing 4-5), how can we be sure that 
the permutation we end up with contains at least one person? Shouldn’t it be possible, in theory, to 
remove everyone?
4-10. Show that the naïve algorithm for finding the maximum permutation (Listing 4-5) is quadratic.
4-11. Implement radix sort.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
92
4-12. Implement bucket sort.
4-13. For numbers (or strings or sequences) with a fixed number of digits (or characters or elements), 
d, radix sort has a running time of Q(dn). Let’s say you are sorting number whose digit counts vary 
greatly. A standard radix sort would require you to set d to the maximum of these, padding the rest with 
initial zeros. If, for example, a single number had a lot more digits than all the others, this wouldn’t be 
very efficient. How could you modify the algorithm to have a running time of Q(∑d
i
), where d
i
 is the 
digit count of the ith number?
4-14. How could you sort n numbers in the value range 1...n
2
 in Q(n) time?
4-15. When finding in-degrees in the maximum permutation problem, why could the count array 
simply be set to [M.count(i) for i in range(n)]?
4-16. The section “Designing with Induction (and Recursion)” describes solutions to three problems. 
Compare the naïve and final versions of the algorithms experimentally.
4-17. Explain why naive_topsort is correct; why is it correct to insert the last node directly after its 
dependencies?
4-18. Write a function for generating random DAGs. Write an automatic test that checks that topsort 
gives a valid orderings, using your DAG generator.
4-19. Redesign topsort so it selects the last node in each iteration, rather than the first.
4-20. Implement the algorithm for finding balance factors in a binary tree.
4-21. An interval can be represented, for example, as a pair of numbers, such as (3.2, 4.9). Let’s say you 
have a list of such intervals (where no intervals are identical), and you want know which intervals that 
fall inside other intervals. An interval (u,v) falls inside (x,y) when x £ u and v £ y. How would you do 
this efficiently?
4-22. How would you improve the relaxation-based algorithm for the airplane + train problem in the 
section “Relaxation and Gradual Improvement” so that you are guaranteed an answer in polynomial time?
4-23. Consider three problems, foo, bar, and baz. You know that bar is hard and that baz is easy. How 
would you go about showing that foo was hard? How would you show that it was easy?
References
Manber, U. (1988). Using induction to design algorithms. Communications of the ACM, 31(11):1300–1313.
Manber, U. (1989). Introduction to Algorithms: A Creative Approach. Addison-Wesley.
Manna, Z. (1974). Mathematical Theory of Computation. McGraw-Hill Book Company.
Okasaki, C. (1999). Purely Functional Data Structures. Cambridge University Press.
Pólya, G. (2009). How To Solve It: A New Aspect of Mathematical Method. Ishi Press.
Rabhi, F. A. and Lapalme, G. (1999). Algorithms: A Functional Approach. Addison-Wesley.
Simionato, M. (2006). The Python 2.3 method resolution order. 
http://python.org/download/releases/2.3/mro
.
Skiena, S. S. (2008). The Algorithm Design Manual, second edition. Springer.
Soltys, M. (2010). An Introduction to the Analysis of Algorithms.  World Scientific.

---

93