Chapter Review 327
- One variant of the Merge Sort algorithm was given in Exercise 22 of Section 2.8.
Analyze the complexity of MergeSort. Count copying an element from array A to array
B, or from array B to array A, as the key operation. Note how much faster MergeSort
is, at least asymptotically, than SelectionSort, BubbleSort, and InsertionSort.
- Challenge: This returns to an issue raised in Section 2.5.6. Show that for formulas 01
in CNF, the shortest equivalent disjunctive normal formula (DNF) 0' may be exponen-
tially longer than 0. Stated more precisely:
i. Count the length of a formula as the total number of symbols in the formula where
a proposition letter pi is counted as one symbol and, if a single symbol occurs
more than once in the formula, each occurrence is counted. So, the length of
(((P9,876,543,210 V P9,876,543,210) V P9,876,543,210) A (Pl V -P9,876,543,210))
is 18: There are five occurrences of proposition letters, four open parentheses, four
closed parentheses, one - sign, three v's, and one A.
ii. For each CNF formula 0, compute the length dnfl(k) of the shortest DNF equiv-
alent to 0. Now, for an integer n, define DNFL(n) to be the maximum value of
dnfl(o) for all formulas 0 of length less than or equal to n.
iii. Show that for some real number r, r' e O(DNFL).
- The following is a simple-minded "algorithm" to check whether a CNF formula in
variables pl ... , p, is satisfiable. The "algorithm" has n nested loops, so we just
use three dots to indicate that an obvious block of code has been omitted. (By our
rules, this really is not an algorithm, because we had no formal mechanism to cover a
variable number of nested loops in an algorithm. However, the reader should be able
to understand exactly what it does.)
The notation "for p 4 aI = F, T" below says to execute the following code twice,
once with p"' = F and once with prla = T.
