# Question

Suppose that instead of swapping element A[i] with a random element from the subarray A[i ..n], we swapped it with a random element from anywhere in the array:

PERMUTE-WITH-ALL (A)

1 n ← length [A]

2 for i ← 1 to n

3 do swap A[i] ↔ A [RANDOM (1, n)]

Does this code produce a uniform random permutation? Why or why not?

PERMUTE-WITH-ALL (A)

1 n ← length [A]

2 for i ← 1 to n

3 do swap A[i] ↔ A [RANDOM (1, n)]

Does this code produce a uniform random permutation? Why or why not?

## Answer to relevant Questions

Professor Armstrong suggests the following procedure for generating a uniform random permutation: PERMUTE-BY-CYCLIC (A) 1 n ← length [A] 2 offset ← RANDOM (1, n) 3 for i ← 1 to n 4 do dest ← i + ...Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω (lg n). (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the ...Show that there is no comparison sort whose running time is linear for at least half of the n! input of length n. What about a fraction of 1/n of the inputs of length n? What about a fraction 1/2n?In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used. Define a family ℋ of hash functions from a finite set U to a finite set B to be ¬-universal if for all pairs of distinct elements k and l in U, Pr {h(k) = h(l)} ≤ ¬, where the probability is taken over the ...Post your question

0