# 算法代写｜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.)