[SOLVED] Cs 170 – homework 2 –

List the names and SIDs of the members in your study group. If you have no collaborators, write “none”.Provide a proof of each of the following properties of Θ: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.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 MediansLet 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.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.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.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.Give a 3-part solution.The Hadamard matrices H₀,H₁,H₂,… are defined as follows:H₀ is the 1 × 1 matrix [1]For k > 0,H_k is the 2^k × 2^k matrix H_k = 1 −1 v = _−1_1Note that since H₂ is a 4 × 4 matrix, and the vector has length 4, the result will be a vector of length 4.Compute u₁ = H₁(v₁ + v₂) and u₂ = H₁(v₁ − v₂) to get two vectors of length 2. Stack u₁ above u₂ to get a vector u of length 4. What do you notice about u?vector, respectively. Therefore, they are each vectors of length . Write the matrix-vector product H_kv in terms of H_k−1, v₁, and v₂ (note that H_k−1 is a matrix of dimension , or 2^k−1 ×2^k−1). Since H_k is a n×n matrix, and v is a vector of length n, the result will be a vector of length n.The n-th roots of unity are the n complex numbers ω such that ωⁿ = 1. They are:e^2πik/n,                 k = 0,1,2,…,n − 1Hint: 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.