1   Quicksort with 3-way partitioning

The analysis of the expected running time of Randomized-Quicksort given in lecture (see also CLRS section 7.4.2) assumed that all element values are distinct. In this problem, we examine what happens when they are not.

•   (1 point) Suppose that the input array A consists of n identical real numbers. What is Randomized-Quicksort’s running time for this input? Explain.

The Partition procedure (CLRS, p. 171) returns an index q such that each element of A[p..q - 1] is less than or equal to A[q] and each element of A[q + 1..r] is greater than A[q].

Modify the Partition procedure to produce a procedure New-Partition(A, p, r), which permutes the elements of A[p..r] and returns two indices q and t, where p ≤ q ≤ t ≤ r, such that

– all elements of A[q..t] are equal;

– each element of A[p..q q 1] is less than A[q];

– each element of A[t + 1..r] is greater than A[q].

Like Partition, your procedure New-Partition should take Θ(r - p) time.

•   (3 points) Describe your algorithm in pseudocode. Comment your code.

•   (2 points) What is the main modifification to Partition? Argue that your algorithm works.

Modify the Randomized-Partition procedure to call New-Partition, and name the new procedure Randomized-New-Partition. Then modify the Quicksort algorithm to produce an algorithm New-Quicksort(A, p, r) that calls Randomized-New-Partition and recurses only on partitions of elements not known to be equal to each other.

•   (1 point) Describe Randomized-New-Partition in pseudocode. Comment your code.

•   (1 point) Describe New-Quicksort in pseudocode.

•   (3 points) Suppose an input array A of length n contains k distinct elements where k|n, and each element occurs exactly n/k times. Show that the expected running time of New-Quicksort on A is O(n lg k). Suppose k = 3; what is the asymptotic running time?

2   Frequency Sorting

Given an array A[1..n] let 0 ≤ f(A, a) ≤ n denote the frequency at which the value a occurs in A. An array A[1..n] is said to be “frequency sorted” if f(A, A[i]) ≤ f(A, A[i + 1]) for all 1 ≤ i ≤ n - 1.

Examples

[1, 2, 3, 1, 2, 1] → [1, 1, 1, 2, 2, 3]

[1, 2, 3, 1, 2, 5] → [2, 2, 1, 1, 3, 5]

[1, 2, 3, 4, 5, 6] → [3, 1, 5, 4, 2, 6]

Note that there may be multiple possible frequency-sorted outputs for a given input array: [1, 1, 2, 2, 3, 5] would also work for the second input, and any permutation would work for the third.

•   (6 points) Given an array A[1..n] of integers, give pseudocode for an algorithm that produces a frequency sorting of A. The algorithm should run in O(n + k log k) expected time, where k denotes the number of unique elements in A.

•   (2 points) Analyze the running time of your algorithm.

3   Randomization Problem

Suppose you are given an array B[1..n] that contains t 1’s and n - t 0’s. It is guaranteed that t is either 0 or (n/2). The problem is to identify which is the case, i.e., to compute what t is. For each question that uses randomness, assume that you have access to a function randint(1, m) that generates a number from 1 to m uniformly at random.

This is the only way you may use randomness.

(a) (1 point) Give a deterministic algorithm that solves this problem. What is the minimum number of comparisons that your algorithm makes in the worst case? Explain your answer.

(b) We would like to do better than the deterministic algorithm by using randomness.

(i) (2 points) First, let’s implement a helper function. Assume that there is an array I[1..n] such that I[j] = j. Using this array, write pseudocode for an algorithm that generates random numbers from 1 to n without replacement in O(1) time. In other words, when calling the function for the kth time, the probability of receiving a number r is 0 if it has been output earlier and otherwise. Note that the state of the array is maintained from one call to the next.

(ii) (3 points) Using the helper function you wrote above, design a randomized algorithm that takes B as input and outputs t. Analyze its expected running time and prove your answer.

(c) (3 points) Now let’s say we always want our algorithm to run in constant time but are willing to tolerate wrong answers. Give a randomized O(1) time algorithm that takes the array B, and a constant probability threshold p ∈ (0, 1) and outputs the value of t correctly with probability at least p. More precisely, the running time of your algorithm should be a function of p. Prove your answer.

(d) (2 points) We slightly generalize the above problem. Let’s say that t can be either · n or 0 for some fixed  in the range (0.01, 1). Now redo the problem, i.e., given (B, p) write a constant time algorithm to output the correct value of t with probability at least p. More precisely, the running time of your algorithm should be a function of p and . Prove your answer. Note that part (c) is the special case when = 1/2.

4 Programming: Arena Security

•   (12 points) Please complete the HW2 programming assignment on GitHub Classroom. Follow the link to accept the assignment and read the README for instructions.