number of moves made by any algorithm that doesn’t disconnect already
connected pieces is equal to −1
20
Exercises 11.3
1. A game of chess can be posed as the following decision problem: given
a legal positioning of chess pieces and information about which side is
to move, determine whether that side can win. Is this decision problem
decidable?
2. A certain problem can be solved by an algorithm whose running time is
in (log2)Which of the following assertions is true?
3. Give examples of the following graphs or explain why such examples can-
not exist.
4. For each of the following graphs, find its chromatic number.
a
a
e
af
d
5. Design a polynomial-time algorithm for the graph 2-colorability problem:
determine whether vertices of a given graph can be colored in two colors
so that no two adjacent vertices are colored the same color.
21
6. Consider the following brute-force algorithm for solving the composite
7. State the decision version for each of the following problems and outline
a polynomial-time algorithm that verifies whether or not a proposed so-
lution solves the problem. (You may assume that a proposed solution
8. BShow that the partition problem is polynomially reducible to the deci-
sion version of the knapsack problem.
9. BShow that the following three problems are polynomially reducible to
each other.
(i) Determine, for a given graph =hiand a positive integer ≤||,
whether contains a clique of size or more. (A clique of size in a
10. Determine whether the following problem is NP-complete. Given several
sequences of uppercase and lowercase letters, is it possible to select a
letter from each sequence without selecting both the upper- and lowercase
versions of any letter? For example, if the sequences are Abc, BC, aB, and
11. BWhich of the following diagrams do not contradict the current state
of our knowledge about the complexity classes P,NP,andNPC (NP-
22
complete problems)?
P=NP
NP
12. King Arthur expects 150 knights for an annual dinner at Camelot. Unfor-
tunately, some of the knights quarrel with each other, and Arthur knows
who quarrels with whom. Arthur wants to seat his guests around a table
so that no two quarreling knights sit next to each other.
23
Hints to Exercises 11.3
1. Check the definition of a decidable decision problem.
3. All four combinations are possible and none of the examples needs to be
large.
5. Use a depth-first search forest (or a breadth-first search forest) of a given
graph.
9. If you are not familiar with the notions of a clique, vertex cover, and
independent set, it would be a good idea to start by finding a maximum-
10. The same problem in a different wording can be found in the section.
Solutions to Exercises 11.3
1. Yes, it’s decidable. Theoretically, we can simply generate all the games
2. First, log2grows to infinity faster than any polynomial function .
This follows immediately from the fact that while the exponent of is
fixed, the exponent log2of log2grows to infinity. (More formally:
3. Here are examples of graphs required:
d
a b
ce
a c
d
b
a b
cd
c
a
e
f
b
(a) (b) (c) (d)
a. Graph (a) has a Hamiltonian circuit (−−−−) but no Eulerian
circuit because it has vertices of odd degrees (and ).
25
4. The chromatic numbers for the graphs below are 2, 3, and 4, respectively.
a
a
e
af
d
a. The chromatic number of graph (a) is 2 because we can assign color
1 to vertices and and color 2 to vertices and .(Note:
b. The chromatic number of graph (b) is 3. It needs at least 3 col-
ors because it has an odd-length cycle: −−−−−and 3 colors
will suffice if we assign, for example, color 1 to vertices and , color 2 to
vertices and , and color 3 to vertex .
c. The chromatic number of graph (c) is 4. It needs at least 3 colors
5. Consider a depth-first search forest obtained by a DFS traversal of a given
graph. If the DFS forest has no back edges, the graph’s vertices can be
colored in two colors by alternating the colors on odd and even levels of
26
6. The brute-force algorithm is in ()However, a proper measure of size
7. a. Determine whether there is a subset of a given set of items that
fits into the knapsack and has a total value not less than a given posi-
tive integer To verify a proposed solution to this problem, sum up the
8. The partition problem for given integers =1 can be expressed
as a selection of 0—1 variables =1 such that
X
=1
=1
2
X
=1
27
9. The reductions follow from the following result (see, e.g., [Gar79]), which
immediately follows from the definitions of the clique, independent set,
10. Since the problem is a different wording of the CNF-satisfiability problem,
it is NP-complete.
11. The given diagrams are:
P=NP=NPC
P=NP
NPC P NPC
NP
(a) is impossible because the trivial decision problem whose solution is
“yes” for all inputs is clearly not NP-complete.
(b) is possible (depicts the case of =NP)
12. a. Create a graph in which vertices represent the knights and an edge
connects two vertices if and only if the knights represented by the vertices
28
b. According to Dirac’s theorem, a graph with ≥3vertices has a
Hamiltonian circuit if the degree of each of its vertices is greater than or
29
Exercises 11.4
1. Some textbooks define the number of significant digits in the approxima-
tion of number ∗by number as the largest nonnegative integer for
2. If =15is known to approximate some number ∗with the absolute
error not exceeding 10−2find
a. the range of possible values of ∗
b. the range of the relative errors of these approximations.
3. Find the approximate value of √=1648721 obtained by the fifth-
6. BIf R1
0sin is to be computed by the composite trapezoidal rule, how
large should the number of subintervals be to guarantee a truncation error
smaller than 10−4?What about 10−6?
8. Write a computer program for solving equation 2+ +=0
30
10. Apply four iterations of Newton’s method to compute √3and estimate
the absolute and relative errors of this approximation.
31
Hints to Exercises 11.4
1. As the given definition of the number of significant digits requires, compute
the relative errors of the approximations. One of the answers does not
agree with our intuitive idea of this notion.
5. Apply formulas (11.7) and (11.9).
6. Find an upper bound for the second derivative of sin and use formula
(11.9) to find a value of guaranteeing the truncation error smaller than
a given error limit
Solutions to Exercises 11.4
1. a. For =31415the relative error of the approximation is
|−∗|
|∗|=|31415 −|
≈29·10−5
2. Since |−∗|≤10−2is equivalent to −10−2≤∗≤+10
−2
149 ≤∗≤151
These bounds imply the following for the possible values of the relative
strips:
2[()+(+1)]
Theentireareais approximated by the sum of these areas:
5. a. Applying formula (11.7) to function ()=2on the interval 0≤≤1
divided into four equal subintervals of length =(1−0)4=025 yields
which is exactly equal to the actual magnitude of the truncation error.
b. Applying formula (11.7) to function ()=1 on the interval 1≤
≤3divided into four equal subintervals of length =(3−1)4=05
Hence, the (magnitude of) truncation error of this approximation is 111¯
6−
109861 =001805
Before we use formula (11.9), let us find
6. Since ()=sin
0()=sin cos and
00()=[sin cos ]0=[sin ]0cos +sin [cos ]0=sin cos2−sin sin
=sin (cos2−sin )=sin (1 −sin2−sin )
35
7. The solution to the first system is =1=1;the solution to the second
one is =85,=−2Both systems are ill-conditioned.
9. a. Let us prove by induction that √for =01 if 0√
Indeed, 0√by assumption. Further, assuming that √ we
can prove that this implies that +1 √as follows:
as goes to infinity yields
=1
2(+
)
whose nonnegative solution is =√
b. We will take advantage of the equality
Applying the last inequality times yields
|−√|≤(−1−√)2≤(−2−√)4≤ ≤(0−√)2
For 025 ≤105≤√1, and hence
10. We will roundoffthe numbers to 6 decimal places.
Thus, 4
=1732051 and, had we continued, all other approximations
would’ve been the same. The exact value of √3is 173205080. Hence,
we can bound the absolute error by
37