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
Do'stlaringiz bilan baham: