1. (10 points) Some authors define W in a slightly different way than we do; let’s use
¥W (read “omega infinity”) for this alternative definition. We say that f (n) =
¥W (g(n)) if there exists a positive constant c such that f (n) ≥ cg(n) ≥ 0 for infinitely many
Show that for any two functions f (n) and g(n) that are asymptotically nonnegative,
either f (n) = O(n) or f (n) = ¥W (n) or both, whereas this is not true if we use W in
place of ¥W.
2. (10 points) Many randomized algorithms randomize the input by permuting the
given input array. We assume that we are given an array A which, without loss of
generality, contains the elements 1 through n. Our goal is to design a procedure to
produce a (uniform) random permutation of the array, that is, that the procedure is
equally likely to produce every permutation of the numbers 1 through n. Consider
1 n = A.length
2 for i = 1 to n
3 swap A[i] with A[Random(1, n)]
Does this procedure produce a uniform random permutation? Why or why not?
3. (10 points) (Errors in randomized algorithms) Recall the problem in HW2 of writing a
randomized computer program C to compute a Boolean function f : f0, 1gn ! f0, 1g,
mapping n bits to 1 bit. We saw how to transform an algorithm C that fails with a
certain probability into a zero-error algorithm that always outputs the correct answer
(at the expense of higher running time than C’s).
Now consider the case where C is a one-sided error algorithm for f , with failure
probability p. There are two kinds of such algorithms, “no-false-positives” and “no
false-negatives”. For simplicity, let’s just consider “no-false-negatives” (the other case
• on every input x, the output C(x) is either 0 or 1;
• on every input x such that f (x) = 1, the output C(x) is also 1;
• on every input x such that f (x) = 0, we have Pr[C(x) = 1] ≤ p.
Show how to convert a no-false-negatives algorithm C for f with failure probability
90% to another no-false-negatives algorithm C0 for f with failure probability at most
2−500. The “slowdown” should only be a factor of a few thousand.
4. (10 points) Let A be a heap of size n. Give the most efficient algorithm to find the
sum of the largest lg n elements.
5. (10 points) Give an O(n log k)-time algorithm to merge k sorted lists into one sorted
list, where n is the total number of elements in all the input lists. (Hint: Use a
min-heap for k-way merging.)
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx