Source code online books for professionals by professionals

Are there extra assumptions you can exploit? Integers in a fixed value range can be sorted more 
efficiently than arbitrary values. Finding the shortest path in a DAG is easier than in an arbitrary 
graph, and using only non-negative edge weights is often easier than arbitrary edge weights.
At the moment, you should be able to start using the first two pieces of advice in constructing your algorithms. 
The first (understanding and representing the problem) may seem obvious, but a deep understanding of the structure 
of the problem can make it much easier to find a solution. Consider special cases or simplifications to see whether 
they give you ideas. Wishful thinking can be useful here, dropping parts of the problem specification, so you can think 
of one or a few aspects at a time. (“What if we ignored the edge weights? What if all the numbers were 0 or 1? What if 
all the strings were of equal length? What if every node had exactly k neighbors?”)
The second item (looking for a reduction) has been discussed a lot in this chapter, especially reducing to (or 
decomposing into) subproblems. This is crucial when designing your own spanking new algorithms, but ordinarily, 
it is much more likely that you’ll find an algorithm that almost fits. Look for patterns in or aspects of the problem 
that you recognize, and scan your mental archives for algorithms that might be relevant. Instead of constructing 
an algorithm that will solve the problem, can you construct an algorithm that will transform the instances so an 
existing algorithm can solve them? Working systematically with the problems and algorithms you know can be more 
productive than waiting for inspiration.
The third item is more of a general observation. Algorithms that are tailored to a specific problem are usually 
more efficient than more general algorithms. Even if you know a general solution, perhaps you can tweak it to use the 
extra constraints of this particular problem? If you’ve constructed a brute-force solution in an effort to understand the 
problem, perhaps you can develop that into a more efficient solution by using these quirks of the problem? Think of 
modifying insertion sort so it becomes bucket sort,
19
 for example, because you know something about the distribution 
of the values.
19
Discussed in the sidebar “Counting Sort & Fam,” earlier in this chapter.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
90
Summary
This chapter is about designing algorithms by somehow reducing a problem to something you know how to solve. If 
you reduce to a different problem entirely, you can perhaps solve it with an existing algorithm. If you reduce it to one 
or more subproblems (smaller instances of the same problem), you can solve it inductively, and the inductive design 
gives you a new algorithm. Most examples in this chapter have been based on weak induction or extending solutions 
to subproblems of size n–1. In later chapters, especially Chapter 6, you will see more use of strong induction, where 
the subproblems can be of any size k < n.
This sort of size reduction and induction is closely related to recursion. Induction is what you use to show that 
recursion is correct, and recursion is a very direct way of implementing most inductive algorithm ideas. However, 
rewriting the algorithm to be iterative can avoid the overhead and limitations of recursive functions in most 
nonfunctional programming languages. If an algorithm is iterative to begin with, you can still think of it recursively, 
by viewing the subproblem solved so far as if it were calculated by a recursive call. Another approach would be to 
define a loop invariant, which is true after every iteration and which you prove using induction. If you show that the 
algorithm terminates, you can use the invariant to show correctness.
Of the examples in this chapter, the most important one is probably topological sorting: ordering the nodes of 
a DAG so that all edges point forward (that is, so that all dependencies are respected). This is important for finding 
a valid order of performing tasks that depend on each other, for example, or for ordering subproblems in more 
complex algorithms. The algorithm presented here repeatedly removes nodes without in-edges, appending them 
to the ordering and maintaining in-degrees for all nodes to keep the solution efficient. Chapter 5 describes another 
algorithm for this problem.
In some algorithms, the inductive idea isn’t linked only to subproblem sizes. They are based on gradual 
improvement of some estimate, using an approach called relaxation. This is used in many algorithms for finding 
shortest paths in weighted graphs, for example. To prove that these are correct, you may need to uncover patterns in 
how the estimates improve or how correct estimates spread across elements of your problem instances.
While reductions have been used in this chapter to show that a problem is easy, that is, to find a solution for 
it, you can also use reductions to show that one problem is at least as hard as another. If you reduce problem A to 
problem B, and the reduction itself is easy, then B must be at least as hard as A (or we get a contradiction). This idea is 
explored in more detail in Chapter 11.
If You’re Curious ...
As I said in the introduction, this chapter is to a large extent inspired by Udi Manber’s paper “Using induction to 
design algorithms.” Information on both that paper and his later book on the same subject can be found in the 
“References” section. I highly recommend that you at least take a look at the paper, which you can probably find 
online. You will also encounter several examples and applications of these principles throughout the rest of the book.
If you really want to understand how recursion can be used for virtually anything, you might want to play around 
with a functional language, such as Haskell (see 
http://haskell.org
) or Clojure (see 
http://clojure.org
). Just 
going through some basic tutorials on functional programming could deepen your understanding of recursion, and, 
thereby, induction, greatly, especially if you’re a bit new to this way of thinking. You could even check out the books by 
Rabhi and Lapalme on algorithms in Haskell and by Okasaki on data structures in functional languages in general.
Although I’ve focused exclusively on the inductive properties of recursion here, there are other ways of showing 
how recursion works. For example, there exists a so-called fixpoint theory of recursion that can be used to determine 
what a recursive function really does. It’s rather heavy stuff, and I wouldn’t recommend it as a place to start, but if 
you want to know more about it, you could check out the book by Zohar Manna or (for a slightly easier but also less 
thorough description) the one by Michael Soltys.
If you’d like more problem-solving advice, Pólya’s How to Solve It is a classic, which keeps being reprinted. Worth 
a look. You might also want to get The Algorithm Design Manual by Steven Skiena. It’s a reasonably comprehensive 
reference of basic algorithms, along with a discussion of design principles. He even has a quite useful checklist for 
solving algorithmic problems.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
91
Exercises
4-1. A graph that you can draw in the plane without any edges crossing each other is called planar. 
Such a drawing will have a number of regions, areas bounded by the edges of the graph, as well as 
the (infinitely large) area around the graph. If the graph has V, E, and F nodes, edges, and regions, 
respectively, Euler’s formula for connected planar graphs says that V – E + F = 2. Prove that this is 
correct using induction.
4-2. Consider a plate of chocolate, consisting of n squares in a rectangular arrangement. You want 
to break it into individual squares, and the only operation you’ll use is breaking one of the current 
rectangles (there will be more, once you start breaking) into two pieces. What is the most efficient way 
of doing this?
4-3. Let’s say you’re going to invite some people to a party. You’re considering n friends, but you know 
that they will have a good time only if  each of them knows at least k others at the party. (Assume that if 
A knows B, then B automatically knows A.) Solve your problem by designing an algorithm for finding 
the largest possible subset of your friends where everyone knows at least k of the others, if such a 
subset exists.
Bonus question: If your friends know d others in the group on average and at least one person knows at 
least one other, show that you can always find a (nonempty) solution for k £ d/2.
4-4. A node is called central if the greatest (unweighted) distance from that node to any other in the 
same graph is minimum. That is, if you sort the nodes by their greatest distance to any other node, 
the central nodes will be at the beginning. Explain why an unrooted tree has either one or two central 
nodes, and describe an algorithm for finding them.
4-5. Remember the knights in Chapter 3? After their first tournament, which was a round-robin 
tournament, where each knight jousted one of the other, the staff want to create a ranking. They  
realize it might not be possible to create a unique ranking or even a proper topological sorting  
(because there may be cycles of knights defeating each other), but they have decided on the following 
solution: order the knights in a sequence K
1
, K
2
, ... , Kn, where K
1
 defeated K
2
, K
2
 defeated K
3
, and so 
forth (K