CS170 - Homework 2 - Solved

Asymptotic Properties
Provide a proof of each of the following properties of Θ:

(a)    For all fixed 

(b)    Consider , where α is a constant. Three different things may happen, depending on the value of α:

(i)        Show that if 

(ii)      Show that if 

(iii)    Show that if 0 

           Median of Medians
The Quickselect(A, k) algorithm for finding the kth smallest element in an unsorted array A picks an arbitrary pivot, then partitions the array into three pieces: the elements less than the pivot, the elements equal to the pivot, and the elements that are greater than the pivot. It is then recursively called on the piece of the array that still contains the kth smallest element.

(a)    Consider the array A = [1,2,...,n] shuffled into some arbitrary order. What is the worst-case runtime of Quickselect(A, n/2) in terms of n? Construct a sequence of ‘bad’ pivot choices that achieves this worst-case runtime.

(b)    The above ‘worst case’ has a chance of occurring even with randomly-chosen pivots, so the worst-case time for a random-pivot Quickselect is O(n2).

Let’s define a new algorithm Better-Quickselect that deterministically picks a better pivot. This pivot-selection strategy is called ‘Median of Medians’, so that the worst-case runtime of Better-Quickselect(A, k) is O(n).

Median of Medians

1.    Group the array into bn/5c groups of 5 elements each (ignore any leftover elements)
2.    Find the median of each group of 5 elements (as each group has a constant 5 elements, finding each individual median is O(1))

3.    Create a new array with only the bn/5c medians, and find the true median of this array using Better-Quickselect.

.    Return this median as the chosen pivot
Let p be the chosen pivot. Show that for least 3n/10 elements x we have that p ≥ x, and that for at least 3n/10 elements we have that p ≤ x.

(c)    Show that the worst-case runtime of Better-Quickselect(A, k) using the ‘Median of Medians’ strategy is O(n).

Hint: Using the Master theorem will likely not work here. Find a recurrence relation for T(n), and try to use induction to show that T(n) ≤ c · n for some c > 0.

4           Werewolves
You are playing a party game with n other friends, who play either as werewolves or citizens. You do not know who is a citizen and who is a werewolf, but all your friends do. There are always at least two more citizens than there are werewolves.

Your goal is to identify one player who is certain to be a citizen.

Your allowed ‘query’ operation is as follows: you pick two people. You ask each person if their partner is a citizen or werewolf. When you do this, a citizen must tell the truth about the identity of their partner, but a werewolf doesn’t have to (they may lie or tell the truth about their partner).

Your algorithm should work regardless of the behavior of the werewolves.

(a)     Show how to solve this problem in O(nlogn) queries (where one query is asking a pair of people to identify the other person).

You cannot use a linear-time algorithm here, as we would like you to get practice with divide and conquer.

Give a 3-part solution.

(b)    (Extra Credit) Can you give a linear-time algorithm?

Give a 3-part solution.

5           Hadamard matrices
The Hadamard matrices H0,H1,H2,... are defined as follows:

H0 is the 1 × 1 matrix [1]

For k > 0,Hk is the 2k × 2k matrix

Hk−1
Hk−1
Hk−1
−Hk−1
 

Hk =

(a)     Write down the Hadamard matrices H0, H1, and H2.

(b)    Compute the matrix-vector product H2 ·v where H2 is the Hadamard matrix you found above, and

 1 

−1 v = −1

1

Note that since H2 is a 4 × 4 matrix, and the vector has length 4, the result will be a vector of length 4.

(c)     Now, we will compute another quantity. Take v1 and v2 to be the top and bottom halves of v respectively. Therefore, we have that

 

Compute u1 = H1(v1 + v2) and u2 = H1(v1 − v2) to get two vectors of length 2. Stack u1 above u2 to get a vector u of length 4. What do you notice about u?

(d)    Suppose that

 

is a column vector of length n = 2k.
v1 and v2 are the top and bottom half of the
vector, respectively. Therefore, they are each vectors of length  . Write the matrix-vector product Hkv in terms of Hk−1, v1, and v2 (note that Hk−1 is a matrix of dimension  , or 2k−1 ×2k−1). Since Hk is a n×n matrix, and v is a vector of length n, the result will be a vector of length n.

(e)     Use your results from (c) to come up with a divide-and-conquer algorithm to calculate the matrix-vector product Hkv, and show that it can be calculated using O(nlogn) operations. Assume that all the numbers involved are small enough that basic arithmetic operations like addition and multiplication take unit time. You do not need to prove correctness.

6           Warmup: FFT
The n-th roots of unity are the n complex numbers ω such that ωn = 1. They are:

                                                                 e2πik/n,                 k = 0,1,2,...,n − 1

(a)     Find an n-th root of unity ω such that for all n-th roots of unity z, z = ωk. In other words, find an ω such that all n-th roots of unity are powers of ω.

(b)    Show that the squares of the 2n-th roots of unity are the n-th roots of unity.

Hint: This requires showing two things: (1) the square of every 2n-th root of unity is an n-th root of unity, and (2) every n-th root of unity is the square of some 2n-th root of unity.

(c)     For a given n-th root of unity ω = e2πik/n, determine all of the 2n-th roots of unity whose squares are ω.