# Question

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 + offset

5 if dest > n

6 then dest ← dest -n

7 B[dest] ← A[i]

8 return B

Show that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.

PERMUTE-BY-CYCLIC (A)

1 n ← length [A]

2 offset ← RANDOM (1, n)

3 for i ← 1 to n

4 do dest ← i + offset

5 if dest > n

6 then dest ← dest -n

7 B[dest] ← A[i]

8 return B

Show that each element A[i] has a 1/n probability of winding up in any particular position in B. Then show that Professor Armstrong is mistaken by showing that the resulting permutation is not uniformly random.

## Answer to relevant Questions

Explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. That is, your algorithm should produce a uniform random permutation, even if two or more priorities ...Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = ¬5, 13, 2, 25, 7, 17, 20, 8, 4¬.Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a ¬ b] in O (1) time. Your algorithm should use Θ ...Show how quick sort can be made to run in O (n lg n) time in the worst case.What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or ...Post your question

0