Problem 1.  Suppose we have an array A[1 : n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plus one; so rank(A[i]) is also the correct position of A[i] in the sorted order of A.

Suppose we have an algorithm magic-pivot that given any array B[1 : m] (for any m > 0), returns an index i such that rank(B[i]) = m/2 and has worst-case runtime of O(m)1 .

Example:  if B = [1, 7, 6, 3, 13, 4, 5, 11], then magic-pivot(B) will return index 7 as rank of B[7] = 5 is 4 which is m/2 in this case.

(a)  Use magic-pivot as a black-box to obtain a deterministic quick-sort algorithm with worst-case running

time of O(nlog n).                                                                                                                    (10 points)

Solution. A complete solution has three steps, algorithm, proof of correctness, and runtime analysis.

Algorithm:  Recall that in quick sort, we pick the pivot p as any arbitrary index of the array A. In our modification, the only change is that we pick p as the output of magic-pivot; formally:

modified-quick-sort(A[1 : n]):

(a) If n = 0 or n = 1, return A.

(b)  Let p = magic-pivot(A).

(c)  Run partition(A,p) and let q be the index of the correct position of pivot.

(d)  Run modified-quick-sort(A[1 : q − 1]) and modified-quick-sort(A[q + 1 : n]).

Proof of correctness:  By the correctness of magic-pivot, we will always be able to find an index p. Since original quick-sort works with any arbitrary choice of index p as the pivot, the modified-quick- sort algorithm works correctly as well (in fact, the entire point of using magic-pivot is to speedup quick-sort with minimal connection to its proof of correctness).

Runtime  analysis:  Let T(n) be the function for the worst-case runtime of the algorithm on inputs of length n. We claim that

T(n) ≤ T(n/2) + T(n/2) + O(n).

This is because magic-pivot returns an index p such that A[p] in the sorted order will be placed in position n/2.   Hence, when running partition(A,p), the returned q will be n/2, leading to the remaining subproblems to be each of size n/2 at most.

The given recurrence is now identical to that of the MergeSort algorithm we covered in the course, which leads to T(n) = O(nlog n).

(b)  Use  magic-pivot  as  a black-box to design  an  algorithm that given the  array  A  and  any integer

1 ≤ r ≤ n, finds the element in A that has rank r in O(n) time2 .                                        (15 points)

Hint:  Suppose we run partition subroutine in quick sort with pivot p and it places it in position q . Then, if r < q, we only need to look for the answer in the subarray A[1 : q] and if r > q, we need to

look for it in the subarray A[q + 1 : n] (although, what is the new rank we should look for now?).

1 Such an algorithm indeed exists, but its description is rather complicated and not relevant to us in this problem.

2 Note that an algorithm with runtime O(n log n) follows immediately from part (a) – sort the array and return the element at position r . The goal however is to obtain an algorithm with runtime O(n).

Solution. A complete solution has three steps, algorithm, proof of correctness, and runtime analysis.

Algorithm:  The algorithm is as follows:

find-rank(A[1 : n],r):

(a) If n = 1, return A[1].

(b)  Let p = magic-pivot(A).

(c)  Run partition(A,p) and let q be the index of the correct position of pivot.

(d) If q = r, return A[q].

(e)  Else, if q > r, return find-rank(A[1 : q − 1],r); otherwise, return find-rank(A[q + 1 : n],r − q)

(note the change in the value of second argument).

Proof of Correctness:  Proof is by induction: our hypothesis is that find-rank(A,r) outputs the correct answer for any choice of n and 1 ≤ r ≤ n.

The base case is true when n = 1, since in this case r = 1 and the element of rank 1 is A[1].

For the induction step, suppose this is true for all choices of n < i + 1 and we prove it for n = i + 1. By the correctness of magic-pivot and partition, we know that q is the correct position of A[q] in the sorted array after the partitioning step; in other words, rank of A[q] is q .

So, if q = r, outputting A[q], which is A[r], is the correct answer.

If q > r, this means that the element with rank r belongs to the sub-array A[1 : q − 1] as these are the elements smaller than A[q] and since r < q , A[r] < A[q] by the definition of rank.  Thus, by the induction hypothesis, find-rank(A[1 : q −1],r) finds the element of rank r in A[1 : q − 1] which is also the element of rank r in A, making the answer correct.

Finally, if q < r, the element of rank r belongs to A[q + 1 : n]. Note however since we are removing q elements with value smaller than A[r] from consideration when looking at A[q + 1 : n], the element of rank r in A will have rank q−r in A[q+1 : n]. By the induction hypothesis, find-rank(A[q+1 : n],q−r) will find this element, finalizing the proof.

Runtime analysis:  Define T(n) as the worst-case runtime of find-rank on any array of length n (and for any choice of r). We have

T(n) ≤ T(n/2) + O(n)

because we only recurse on one subproblem and q = n/2 (unlike in part (a) which we recursed on both subproblems). This means (by replacing O(n) with C · n for some constant C > 0),

+∞

T(n) ≤ T(n/2) + C · n ≤ T(n/4) + C · (n + n/2) ≤ C · n · 工(1/2)i  = O(n),

i=0

as the sum of a geometric series with ratio less than 1 converges to O(1).  As such, the runtime of find-rank is O(n) as desired.

Problem  2.  Suppose we have an array A[1  :  n] which consists of numbers  {1, . . . ,n} written in some arbitrary order (this means that A is a permutation  of the set {1, . . . ,n}).  Our goal in this problem is to design a very fast randomized algorithm that can find an index i in this array such that A[i]  mod 5 = 0, i.e., A[i] is divisible by five. For simplicity, in the following, we assume that n itself is a multiple of 5 and is at least 5 (so a correct answer always exist).

For instance, if n = 10 and the array is A = [8, 7, 2, 5, 4, 6, 3, 1, 10, 9], we can output either of indices 4 or 9.

(a)  Suppose we sample an index i from {1, . . . ,n} uniformly at random. What is the probability that i is

a correct answer, i.e., A[i]  mod 5 = 0?                                                                                     (5 points)

Solution.  The correct answer is 1/5.

There are exactly n/5 numbers in {1, . . . ,n} such that A[i]  mod 5 = 0 (as n itself is a multiple of 5, there is no corner case).  Since we are picking i uniformly at random, the probability that A[i] is any of these numbers is exactly (n/5)/n = 1/5.

(b)  Suppose we sample m indices from {1, . . . ,n} uniformly at random and with repetition.  What is the

probability that none of these indices is a correct answer?                                                      (5 points)

Solution.  The correct answer is (4/5)m .

By part (a), the probability that each index is not  correct is 1 − 1/5 = 4/5.  Since we are sampling each index independently  (as it is with repetition), the probability that no index is correct among m trials is (4/5)m .

Now, consider the following simple algorithm for this problem:

Find-Index-1(A[1 : n]):

• Let i = 1. While A[i]  mod 5  0, sample i ∈ {1, . . . ,n} uniformly at random. Output i. The proof of correctness of this algorithm is straightforward and we skip it in this question.

(c) What is the worst-case expected running time of Find-Index-1(A[1 : n])? Remember to prove your answer formally.                                                                                                                          (7 points)

Solution.  Define a random variable X ∈ [1 : +∞] where X = j if the number of times we run the while-loop is j (it is a random variable depending on the randomness of the algorithm).  Each run of the algorithm takes O(X) time (but this is a random variable and so we need to turn it into a formula); thus the expected worst-case runtime of the algorithm is O(E[X]). So, we only need to compute E[X].

We have,

Pr(X = j) = Pr(first j − 1 trials fail and j-th trial succeeds)        (by the definition of while-loop)

= Pr(first j − 1 trials fail) · Pr(j-th trial succeeds)

(by independence of trials in different iterations)

= (4/5)j −1 · (1/5).                                               (by part (b) and part (a), respectively)

As such, by the definition of expectation,

∞                                         ∞

E[X] =工 Pr(X = j) · j ≤工(4/5)j −1 · (1/5) · j = 5,

j=1                                        j=1

as the series converges to 5. So O(E[X]) = O(1), meaning that the worst-case expected runtime of the algorithm is O(1).

The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never terminate! For this reason, let us consider a simple modification to this algorithm as follows.

Find-Index-2(A[1 : n]):

• For j = 1 to n:

–  Sample i  ∈  {1, . . . ,n} uniformly at random and if A[i]  mod 5  =  0, output i and terminate; otherwise, continue.

• If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i] mod 5 = 0 and output it as the answer.

Again, we skip the proof of correctness of this algorithm.

(d) What is the worst-case  running  time of  Find-Index-2(A[1  :  n])?   What about its worst-case expected running time? Remember to prove your answer formally.                                     (8 points)

Solution.  The worst-case runtime of the new algorithm happens when we finish the for-loop without success and then do a linear search over the array; both of these takes Θ(n) time so the worst-case runtime is Θ(n).

For the worst-case expected runtime, let us define two variables.  We use X  ∈ {1, . . . ,n,n + 1} to denote the number of iterations of the first for-loop where X = n + 1 means that the for-loop failed. So, when X  ≤ n, the runtime of the algorithm is O(X) and when X  = n + 1, the runtime of the algorithm is O(n) (for the first for-loop) plus another O(n) (for the second for-loop); either way, the runtime of the algorithm is O(X). We thus need to compute expected value of X to get the expected worst-case runtime of the algorithm.

n+1                                          ∞

E[X] =工 Pr(X = j) · j ≤工(4/5)j −1 · (1/5) · j = 5,

j=1                                        j=1

where the calculations is exactly as in part (a). Thus, in this case also, the worst-case expected runtime of the algorithm is still O(1).

Problem 3. You are given two strings A and B of length n, each consisting of possibly repeated characters from an alphabet of size M . A and B are said to be anagrams of one another if it is possible to reorder the characters in A to obtain string B (without removing or adding any characters).  For instance, the strings “ELEVEN PLUS TWO” and “TWELVE PLUS ONE” are anagrams of one another (think of empty-space also as a character in the alphabet).

Your goal is to design an algorithm that decides if a given pair of strings are anagrams of one another. You may assume that all characters in the alphabet can represented by distinct integers in the set {1, 2, . . . ,M}, and that you can convert any character to its integer representation in O(1) time (note that M can be much larger than n).

(a)  Design an algorithm for this problem with worst-case runtime of O(n + M).                     (15 points)

Solution. A complete solution has three steps, algorithm, proof of correctness, and runtime analysis. Algorithm:  The algorithm is as follows:

(a)  Sort the arrays A and B separately, using counting sort.

(b)  For i = 1 to n:

i. If A[i]  B[i], then return No.

(c) If the algorithm has not terminated yet, return  Yes.

Problem 4. You are given an array of characters S[1 : n] such that each S[i] is a small case letter from the English alphabet.  You are also provided with a black-box algorithm dict that given two indices i,j ∈ [n], dict(i,j) returns whether the sub-array S[i : j] in array S forms a valid word in English or not in O(1) time. (Note that this algorithm is provided to you and you do not need to implement it in any way).

Design and analyze a dynamic programming algorithm to find whether the given array S can be partitioned

into a sequence of valid words in English. The runtime of your algorithm should be O(n2 ). Example: Input Array: S = [maytheforcebewithyou].

Assuming the algorithm dict returns that may,the,force,be,with and you are valid words (this means that for instance, for may we have dict(1, 3) = True), this array can be partitioned into a sequence of valid words.

Solution.

Specification:  For an integer i, 1 ≤ i ≤ n, define:

• dp(i) to be 1 if the string s[1 : i] can be partitioned into a sequence of valid words, and 0 otherwise. The final answer to the problem will be dp(n).

Solution:  We can calculate dp(i) recursively as follows:

'1   if dict(1,i) is True

dp(i) =〈 1   if dp(j) = 1 and dict(j + 1,i) is True for some j < i

'(0   otherwise

We will now prove the correctness of this solution.

Direction 1: if s[1 : i] is a valid sequence of words, then dp(i) = 1. Since we assume s[1 : i] is a valid sequence, it is either the case that s[1 : i] is a single word, or a collection of words. If it is a single word, then dist(1,i) is True and dp(i) returns 1 by its first line.  Otherwise, let j + 1 be the index of the beginning of last word in the valid sequence of s[1 : i]. For that particular choice of j, we have that s[1 : j] is a collection of words, and thus dp(j) = 1, and dict(j + 1,i) is True, so dp(i) returns 1 also.

Direction 2:  if s[1  : i] is not a valid sequence of words, then dp(i)  = 0.   By the contrapositive, this is equivalent to proving that if dp(i) = 1, then s[1 : i] is a valid sequence.  Since we assume dp(i) = 1, then it can either be because dict(1,i) is True or there is some j < i such that dp(j) = 1 and dict(j + 1,i) is True. In the first case, we know that s[1 : i] is a valid word itself so it is also a valid sequence. In the second case,

we have s[1 : j] is a valid sequence and s[j + 1,i] is a word, so all of s[1 : i] is also a valid sequence of words. This proves the correctness of the recursive function dp(i) for every 1 ≤ i ≤ n.

Dynamic programming algorithm:  We will do a bottom-up dynamic programming for this problem.

1.  Create array D[1 : n] with 0 as its entries.

2.  Let D[1] = 1 if dict(1, 1) returns True, D[1] = 0 otherwise.