算法代写｜CSCE 411 502 Design and Analysis of Algorithms Midterm 1

这是一个美国的一个算法设计与分析限时测试代写

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
integers n.

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
the following:

Permute(A)

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
is symmetric):

• 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.)