Page 557 - Discrete Mathematics and Its Applications

536 8 / Advanced Counting Techniques

the answer, but the situation is more complicated when asking the first person whether x is in each set. The
some terms are negative. For example, the maximum sum first person answers either “yes” or “no.” When the first
of consecutive terms of the sequence −2, 3, −1, 6, −7, 4 person answers each query truthfully, we can find x
is 3 + (−1) + 6 = 8. (This exercise is based on [Be86].) using log n queries by successively splitting the sets
Recall that in Exercise 56 in Section 8.1 we developed a used in each query in half. Ulam’s problem, proposed by
dynamic programming algorithm for solving this prob- Stanislaw Ulam in 1976, asks for the number of queries
lem. Here, we first look at the brute-force algorithm required to find x, supposing that the first person is al-
for solving this problem; then we develop a divide-and- lowed to lie exactly once.
conquer algorithm for solving it. a) Show that by asking each question twice, given a num-
a) Use pseudocode to describe an algorithm that solves ber x and a set with n elements, and asking one more
this problem by finding the sums of consecutive terms question when we find the lie, Ulam’s problem can be
starting with the first term, the sums of consecutive solved using 2 log n + 1 queries.
terms starting with the second term, and so on, keep- b) Show that by dividing the initial set of n elements into
ing track of the maximum sum found so far as the four parts, each with n/4 elements, 1/4 of the elements
algorithm proceeds. can be eliminated using two queries. [Hint: Use two
b) Determine the computational complexity of the al- queries, where each of the queries asks whether the
gorithm in part (a) in terms of the number of sums element is in the union of two of the subsets with n/4
computed and the number of comparisons made. elements and where one of the subsets of n/4 elements
c) Devise a divide-and-conquer algorithm to solve this is used in both queries.]
problem. [Hint:Assume that there are an even number c) Show from part (b) that if f (n) equals the number
of terms in the sequence and split the sequence into of queries used to solve Ulam’s problem using the
two halves. Explain how to handle the case when the method from part (b) and n is divisible by 4, then
maximum sum of consecutive terms includes terms in f (n) = f(3n/4) + 2.
both halves.] d) Solve the recurrence relation in part (c) for f (n).
d) Use the algorithm from part (c) to find the maximum
sum of consecutive terms of each of the sequences: e) Is the naive way to solve Ulam’s problem by ask-
−2, 4,−1, 3, 5,−6, 1, 2; 4, 1,−3, 7,−1,−5, 3, −2; ing each question twice or the divide-and-conquer
and −1, 6, 3, −4, −5, 8, −1, 7. method based on part (b) more efficient? The most
e) Find a recurrence relation for the number of sums efficient way to solve Ulam’s problem has been
determined by A. Pelc [Pe87].
and comparisons used by the divide-and-conquer al-
gorithm from part (c). In Exercises 29–33, assume that f is an increasing function
d
f) Use the master theorem to estimate the computa- satisfying the recurrence relation f (n) = af (n/b) + cn ,
tional complexity of the divide-and-conquer algo- where a ≥ 1, b is an integer greater than 1, and c and d
rithm. How does it compare in terms of computational are positive real numbers. These exercises supply a proof of
complexity with the algorithm from part (a)? Theorem 2.
24. Apply the algorithm described in Example 12 for find- ∗ 29. Show that if a = b and n is a power of b, then f (n) =
d
d
ing the closest pair of points, using the Euclidean dis- f(1)n + cn log n.
d
b
tance between points, to find the closest pair of the 30. Use Exercise 29 to show that if a = b , then f (n) is
d
points (1, 3), (1, 7), (2, 4), (2, 9), (3, 1), (3, 5), (4, 3), O(n log n).
d
and (4, 7).
d
∗ 31. Show that if a = b and n is a power of b, then f (n) =
25. Apply the algorithm described in Example 12 for finding d log b a d d
the closest pair of points, using the Euclidean distance be- C 1 n + C 2 n , where C 1 = b c/(b − a) and C 2 =
d
d
tween points, to find the closest pair of the points (1, 2), f(1) + b c/(a − b ).
d
(1, 6), (2, 4), (2, 8), (3, 1), (3, 6), (3, 10), (4, 3), (5, 1), 32. Use Exercise 31 to show that if a< b , then f (n) is
d
(5, 5), (5, 9), (6, 7), (7, 1), (7, 4), (7, 9), and (8, 6). O(n ).
d
∗ 26. Use pseudocode to describe the recursive algorithm for 33. Use Exercise 31 to show that if a> b , then f (n) is
solving the closest-pair problem as described in Exam- O(n log b a ).
ple 12. k
34. Find f (n) when n = 4 , where f satisfies the recurrence
27. Construct a variation of the algorithm described in Ex- relation f (n) = 5f (n/4) + 6n, with f(1) = 1.
ample 12 along with justifications of the steps used by
35. Give a big-O estimate for the function f in Exercise 34
the algorithm to find the smallest distance between two
points if the distance between two points is defined to be if f is an increasing function.
k
d((x i ,y i ), (x j ,y j )) = max(|x i − x j |, |y i − y j |). 36. Find f (n) when n = 2 , where f satisfies the recurrence
2
∗ 28. Suppose someone picks a number x from a set of n relation f (n) = 8f (n/2) + n with f(1) = 1.
numbers. A second person tries to guess the number 37. Give a big-O estimate for the function f in Exercise 36
by successively selecting subsets of the n numbers and if f is an increasing function.