414 j;\ Solutions (or Hints) to Chapter-end Exercises
11.15 qo1ll1xlby ~ llllqoXlby ~ llllqlxby. As b lies between Xl and y,
Z(4) = 0 (given by b).
11.16 In Section 11.4.5 we obtained q01xlby ~ qs1xbbly. Similarly,
qoll1xlby ~ qs1llxlb1y ~ 1qollxlbly. Proceeding further,
1qollxlb1y ~ 1qsllxlblly ~ llq o lx l blly f-"' - lllqc;Xllllly (as in
Section 11.4.5). Hence S(3) = 4.
11.18 Represent the argument x in tally notation. j(x) = S(S(x». Using the
construction given in Section 11.4.7, we can construct a TM which
gives the value S(S(x».
11.19 f(x]> X2) = S(S(U?(x]> X2»)' Use the construction in Section 11.4.7.
11.20 Represent (Xl> X2) by P 1 bl'2. By taking the input as $1' I b1'2($ is
representing the left-end) and suitably modifying the TM given in
Example 9.6, we get the value of Xl + X2 to the right of $.
Chapter 12
12.1 Denote j(n)
k
= L aini and g(n) =
1=0
I
L bini, where aj, bi' are positive
./=0 <
k
integers. Assume k :2 t. Then fen) + g(n) = L (ai + bJn
i , where b i = 0
1=0
for i > l. f(n) + g(n) is a polynomial of degree k. Hence j(n)g(n) =
O(nk+/).
12.2 As n
2 dominates n log nand n
2 10g n dominates n
2 , the growth rate of
hen) > growth rate of g(n). Note f(n) = g(n) = 0(n
2
).
Jl
II
11
12.3 As L i =n(n + 1)/2, L P =n(n + 1)(211 + 1)/6 and L P =(n(n + 1)12)2,
1=0
1=0
1=0
the answers for (i) and (ii) are 0(n
3 ) and O(n\ (iii) a(1 - r")/l - r =
n
O(l'lr) = 0(1'-1). (iv) '2 [2a + (n-1)d] = 0(n
2 ).
12.4 As log2 n, 10g3 n, loge n, differ by a constant factor, j(n) = O(r/ log n)
12.5 gcd = 3.
12.6 The principal disjunctive normal form of the boolean expression has
5 terms (refer to Example 1.13). P ;\ Q ;\ R is one such term. So
(T, T, T) satisfies the given expression. Similar assignments for the
other four terms.
12.7 No.
12.8 (T. T, F, F) makes the given expression satisfiable.
12.9 Only if: Take an NP-complete problem L. Then r is in CO-NP = NP.