11. n/a
12. a. After the bunch of spaghetti rods is put in a vertical position on a
tabletop, repeatedly take the tallest rod among the remaining ones out
until no more rods are left. This will sort the rods in decreasing order of
Exercises 6.5
1. Consider the following brute-force algorithm for evaluating a polynomial.
Algorithm BruteForcePolynomialEvaluation([0])
//Computes the value of polynomial at a given point
//by the “highest to lowest term” brute-force algorithm
2. Write pseudocode for the brute-force polynomial evaluation that stems
from substituting a given value of the variable into the polynomial’s for-
3. a. Estimate how much faster Horner’s rule is compared to the “lowest-
to-highest term” brute-force algorithm of Problem 2 if (i) the time of one
multiplication is significantly larger than the time of one addition; (ii) the
time of one multiplication is about the same as the time of one addition.
5. Apply Horner’s rule to convert 110100101 from binary to decimal.
6. Compare the number of multiplications and additions/subtractions needed
by the “long division” of a polynomial ()=+−1−1+···+0
7. a. Apply the left-to-right binary exponentiation algorithm to compute 17
10. Is it a good idea to use a general-purpose polynomial evaluation algorithm
such as Horner’s rule to evaluate the polynomial ()=+−1+···+
+1?
11. According to the corollary of the Fundamental Theorem of Algebra, every
polynomial
()=+−1−1+···+0
12. IPolynomial interpolation Given a set of data points (
)where
42
Hints to Exercises 6.5
1. Set up a sum and simplify it by using the standard formulas and rules for
2. Take advantage of the fact that the value of can be easily computed
from the previously computed −1
3. a. Use the formulas for the number of multiplications (and additions) for
both algorithms.
answer might surprise you.
7. a. Trace the left-to-right binary exponentiation algorithm on the instance
given the same way it is done for another instance in the section.
b. The answer is “yes”: the algorithm can be extended to work for the
zero exponent as well. How?
8. Trace the right-to-left binary exponentiation algorithm on the instance
given the same way it is done for another instance in the section.
43
Solutions to Exercises 6.5
1. The total number of multiplications made by the algorithm can be com-
puted as follows:
2. Algorithm BetterBruteForcePolynomialEvaluation([0])
//Computes the value of polynomial at a given point
//by the “lowest-to-highest term” algorithm
//Input: Array [0]of the coefficients of a polynomial of degree ,
The number of multiplications made by this algorithm is
()=
X
=1
2=2
3. a. If only multiplications need to be taken into account, Horner’s rule
will be about twice as fast because it makes just multiplications vs. 2
44
4. a. Evaluate ()=34−3+2+5at =−2
5. Applying Horner’s rule to compute (2) where ()=8+7+5+2+1
yields
6. The long division by −is done as illustrated below
7. a. Compute 17 by the left-to-right binary exponentiation algorithm.
Here, = 17 = 100012So, we have the following table filled left-to-right:
binary digits of 10 0 0 1
45
8. Compute 17 by the right-to-left binary exponentiation algorithm.
Here, = 17 = 100012So, we have the following table filled right-to-left:
9. Algorithm ImplicitBinaryExponentiation(,)
//Computes by the implicit right-to-left binary exponentiation
//Input: A number and a nonnegative integer
10. Since the polynomial’s terms form a geometric series,
11. a. With Horner’s rule, we can evaluate a polynomial in its coefficient form
with multiplications and additions. The direct substitution of the
value in the factorized form requires the same number of operations,
although these may be operations on complex numbers even for a polyno-
mial with real coefficients.
12. For the general case of points, Lagrange’s interpolation formula looks
as follows:
47
Exercises 6.6
1. a. Prove the equality
2. You are given a list of numbers for which you need to construct a min-heap.
(A min-heap is a complete binary tree in which every key is less than or
equal to the keys in its children.) How would you use an algorithm for
constructingamax–heap(aheapasdefined in Section 6.4) to construct a
min-heap?
3. Prove that the number of different paths of length 0from the th
vertex to the th vertex in a graph (undirected or directed) equals the
( )th element of where is the adjacency matrix of the graph.
5. Given 3points 1=(1
1) =(
)in the coordinate
plane, design an algorithm to check whether all the points lie within a
triangle with its vertices at three of the points given. (You can either
design an algorithm from scratch or reduce the problem to another one
with a known algorithm.)
6. Consider the problem of finding, for a given positive integer the pair of
48
8. Solve the instance of the linear programming problem given in Section 6.6:
maximize 010+007+003
9. The graph-coloring problem is usually stated as the vertex-coloring prob-
lem: Assign the smallest number of colors to vertices of a given graph so
that no two adjacent vertices are the same color. Consider the edge–
coloring problem: Assign the smallest number of colors possible to edges
of a given graph so that no two edges with the same endpoint are the
same color. Explain how the edge-coloring problem can be reduced to a
vertex-coloring problem.
10. Consider the two-dimensional post office location problem:given
11. Jealous husbands There are ≥2married couples who need to cross
a river. They have a boat that can hold no more than two people at a
time. To complicate matters, all the husbands are jealous and will not
a. Solve the problem for =2
b. Solve the problem for =3, which is the classical version of this
problem.
49
12. BDouble-n dominoes Dominoes are small rectangular tiles with dots
called spots or pips embossed at both halves of the tiles. A standard
“double-six” domino set has 28 tiles: one for each unordered pair of in-
Hints to Exercises 6.6
1. a. Use the rules for computing lcm( )and gcd( )from the prime
2. Use a relationship between minimization and maximization problems.
3. Prove the assertion by induction on
4. a. Base your algorithm on the following observation: a graph contains a
5. An easier solution is to reduce the problem to another one with a known
6. Express this problem as a maximization problem of a function in one
variable.
7. Introduce double-indexed variables to indicate an assignment of the
th person to the th job.
11. a., b. Create a state-space graph for the problem as it is done for the
river-crossing puzzle in the section.
51
Solutions to Exercises 6.6
1. a. Since
lcm( )=the product of the common prime factors of and
·the product of the prime factors of that are not in
·the product of the prime factors of that are not in
and
Since the product of the first two terms is equal to and the product of the
last two terms is equal to we showed that lcm( )·gcd( )=·
and, hence,
2. Replace every key of a given list by −and apply a max-heap con-
struction algorithm to the new list. Then change the signs of all the keys
again.
3. The induction basis: For =1
1[ ]is equal to 1 or 0 depending on
whether there is an edge from vertex to vertex . In either case, it is
52
4. a. For the adjacency matrix of a given graph, compute 2with an al-
gorithm whose time efficiency is better than cubic (e.g., Strassen’s matrix
b. The algorithm is incorrect because the condition is sufficient but not
necessary for a graph to contain a cycle of length 3. Consider, as a
5. The problem can be reduced to the question about the convex hull of a
given set of points: if the convex hull is a triangle, the answer is yes,
6. Let be one of the numbers in question; hence, the other number is −
The problem can be posed as the problem of maximizing ()=(−)
on the set of all integer values of Since the graph of ()=(−)
7. Let be a 0-1 variable indicating an assignment of the th person to
the th job (or, in terms of the cost matrix a selection of the matrix
element from the th row and the th column). The assignment problem
8. We can exploit the specific features of the instance in question to solve it
by the following reasoning. Since the expected return from cash is the
smallest, the value of cash investment needs to be minimized. Hence,
=025(+)in an optimal solution. Substituting =025(+)into
9. Create a new graph whose vertices represent the edges of the given graph
and connect two vertices in the new graph by an edge if and only if these
10. The problem is obviously equivalent to minimizing independently 1
P
=1 |−
|and 1
=1 |−|Thus we have two instances of the same problem,
11. a. Here is a state-space graph for the two jealous husbands puzzle: H,W
54
graph doesn’t include crossings that differ by obvious index substitutions
such as starting with the first couple H1W1crossing the river instead of
thesecondoneH
2W2) The vertices corresponding to the initial and final
states are shown in bold.
H H
W W
12
12
H H
W W
12
12
H H
W W
12
12
H
W
2
1
H H
W
12
2
H1
W2W1
W W
12 H W
22 W2
H H
12
There are four simple paths from the initial-state vertex to the final-state
vertex, each five edges long, in this graph. If specified by their edges,
they are:
W1W2W1H1H2H1H1W1
W1W2W1H1H2W2W1W2
b. Here is a state-space graph for the three jealous husbands puzzle:
H,W
denote the husband and wife of couple (=123)respectively;
the two bars ||denote the river; the arrow indicates the possible direction
55
of the next trip, which is defined by the boat’s location. (For the sake of
simplicity, the graph doesn’t include crossings that differ by obvious index
substitutions such as starting with the first or second couple crossing the
H H H
12 3
H H H
12 3
W1W3
W W W
12 3 W W W
12 3
W W
23
W W
12
H H H
123
H H H
123
Hence, there are four (to within obvious symmetric substitutions) optimal
solutions to this problem, each requiring eleven river crossings.
c. The problem doesn’t have a solution for the number of couples ≥
56
12. One can reduce the problem to the question about existence of an Eulerian
circuit in a complete graph with +1 vertices. Vertex ,0≤≤,inthis
graph represents a possible number of spots on one of the two halves of
an -domino, and an edge between vertices and represents the domino
57