University of Waterloo

CS240 Winter 2020

Assignment 2

Due Date: Wednesday, February 12 at 5:00pm

Please read http://www.student.cs.uwaterloo.ca/~cs240/w20/guidelines.pdf for

guidelines on submission. This assignment contains both written problems and a pro-

gramming problem. Submit your written solutions electronically as a PDF with file name

a2Submit.pdf using MarkUs. We will also accept individual question files named a2q1.pdf,

a2q2.pdf, ... , a2q6.pdf if you wish to submit questions as you complete them.

Note: you may assume all logarithms are base 2 logarithms: log = log2.

Problem 1 [8 marks]

Generalize quickSelect1 to work on two input arrays. Let the resulting algorithm be called

quickSelect2Arrays(A,B, k). Arrays A and B are of size n and m, respectively, and k ∈

{0, 1, ..., n + m − 1}. Algorithm quickSelect2Arrays(A,B, k) should return the item that

would be in C[k] if C was the array resulting from merging arrays A and B and C was sorted

in non-decreasing order.

Your algorithm quickSelect2Arrays(A,B, k) must be in-place, i.e. only O(1) additional

space is allowed. Briefly and informally (one or two sentences) argue that the time complexity

of your algorithm is the same as of quickSelect1, i.e. O(v) in the average case where v is

the total number of elements in A and B, i.e. v = n + m. Hint: use the same pivot-value

for partitioning both arrays.

Problem 2 [4+5(+6)=9(+6) marks]

For this question, assume Quicksort algorithm selects the last element of A as pivot, and

partition(A, p) is as below:

1

partition(A, p)

A: array of size n, p: integer s.t. 0 ≤ p < n

Create empty lists small and large.

v ← A[p]

for each element x in A[0, . . . , p−1] or A[p+1 . . . n−1]

if x < v append x to small

else append x to large

i← size(small)

Overwrite A[0 . . . i−1] by elements in small

Overwrite A[i] by v

Overwrite A[i+1 . . . n−1] by elements in large

return i

a) Give the recurrence equation for Quicksort when the input array A contains n copies

of the same element, i.e. A = [x, x, . . . , x]. Briefly explain how you got your recurrence

equation. You are not required to solve the recurrence equation.

b) Suppose we use the following approach to choosing the pivot in Quicksort: First,

compute the mean n¯ of the elements in the array. Then choose as the pivot the element

x of the array, such that |x−n¯| is minimized, i.e., pick the element closest to the average

value in the array. Let us call this modified Quicksort algorithm MeanQuicksort.

Assume that the elements of the array form an arithmetic sequence (i.e., have the form

a, a+ k, a+ 2k, a+ 3k, . . . , a+ (n− 1)k), scrambled in some order. Show that, under

this distribution of array elements, MeanQuickSort always runs in O(n log n) time.

c) Bonus: Give an example for which MeanQuickSort in part (b) runs in Ω(n2) time,

and explain why this running time is achieved.

Problem 3 [5+4=9 marks]

You have found a treasure chest filled with n ≥ 3 coins. Exactly 2 coins are counterfeit, the

rest are genuine. All genuine coins weigh the same and the two counterfeit coins weigh the

same, but a counterfeit coin weighs less than a genuine coin. Your task is to separate the

genuine coins from the counterfeit coins. To accomplish this you will compare the weight

of pairs of subsets of the coins using a balance scale. The outcome of one weighing will

determine that each subset of coins weighs the same, or that one or the other subset of coins

weighs more.

a) Give a precise (not big-Omega) lower bound for the number of weighings required

in the worst case to determine which coins are genuine and which are counterfeit for

n ≥ 3. Briefly justify.

2

b) Describe an algorithm called FindGenuine to determine the genuine coins when n = 4.

Use the names C1, C2, C3, C4 for the four coins, and the function

CompareWeight ({first subset; second subset}) ,

which returns 1 if first subset weighs more, 0 if both subsets weigh the same, and −1 if

second subset weighs more. Your function should return the set of genuine coins. Give

an exact worst-case analysis of the number of weightings required by your algorithm.

For full marks, this should match exactly the lower bound from Part (a).

Problem 4 [6 marks]

Let A[0...n−1] be an unsorted array of positive integers, in the range of (0, ..., n5). Entries in

A are not necessarily unique. Design an algorithm that tests whether there are two numbers

in A that are exactly ten apart, i.e. |A[i]−A[j]| = 10 for some indexes i, j ∈ {0, 1, ...n− 1}.

For example, the algorithm should return “yes” if the array is A = [4, 1, 10, 6, 5, 11], because

numbers 1 and 11 are 10 units apart. It should return “no” on A = [10, 5, 13, 1, 14, 2]. The

worst-case run-time of your algorithm must be O(n). You can use O(n) additional space.

Problem 5 [4+4=8 marks]

a) Consider the following AVL-tree:

18

15 22

20

Insert key 23 into this AVL-tree. Then insert key 24 into the result. Show the resulting

AVL-tree. For full credit it is enough to show the correct final tree, but in case of error,

partial credit may be given for the intermediate correct trees. Use the algorithm and

rotations as defined in class. If you draw intermediate trees, clearly indicate which tree

is your final answer.

3

b) Consider the following AVL-tree:

12

5

2

1

9

11

20

22

Delete key 20 from this AVL-tree, using the algorithm from class. Show the resulting

AVL-tree. For full credit it suffices to show the correct final tree, but in case of error,

partial credit may be given for intermediate trees. If you draw intermediate trees,

clearly indicate which tree is your final answer.

Problem 6 [4+3+4=11 marks]

Let an AVL∗-tree be a binary search tree where for every node, the difference of heights

of its left and right subtree is at most 2. Let N(h) be the minimum number of nodes for

AVL∗-tree of height h.

a) What is N(h) for h ∈ {0, 1, 2, 3}?. For justification, it is sufficient to draw the smallest

AVL∗-trees of heights h ∈ {0, 1, 2, 3}.

b) Derive a recursive formula for N(h) for h ≥ 3. Give a brief explanation of your

derivation.

c) Show that in any AVL∗-tree of height h ≥ 0 with n nodes, we have h ≤ 3 log2(n).

4