Algorithms Problem Set
Basic Algorithms — Spring 2020 — Problem Set 7 Due: Wed, April 29, 11am 1. Mastering the Master Theorem. Use the “Master Theorem,” as discussed in class, to solve the following recurrences: (a) T (n) ≤ 2T (bn/4c) +O( √ n) (b) T (n) ≤ 2T (bn/4c) +O(n0.51) (c) T (n) ≤ 3T (bn/3c) +O(n) (d) T (n) ≤ 16T (bn/4c) +O(n1.5) (e) T (n) ≤ 7T (bn/2c) +O(n2) 2. Weighing coins. You are given n coins — they all look identical, and all have the same weight except one, which is heavier than all the rest. You also have a balance scale, on which you can place one set of coins on one side, and another set of coins on the other, and the scale will tell you whether the two sets have the same weight, and if not, which is the heavier set. Suppose that performing one such weighing takes one minute, and in addition, you have to pay a fee of m dollars, where m is the total number of coins placed on the scale in that weighing. Design and analyze a strategy that will identify the heavy coin in O(log n) minutes and at a cost of O(n) dollars. You may analyze the your strategy using the Master Theorem. You may not assume that n has any special form (although you might want to first think about the case where n is a power of 2). 3. Quasi-linear recursion tree analysis. Suppose we have an algorithm that on inputs of size n, recursively solves two problems of size n/2, with a “local running time” t(n) that satisfies c1n log2(n) ≤ t(n) ≤ c2n log2(n) for some constants c1, c2 and all n ≥ 2. For simplicity, assume that n is a power of 2. Also, assume that n ≥ 2 and the recursion stops when n = 2. Let T (n) be the total running time of the algorithm on inputs of size n. Prove that d1n(log2(n)) 2 ≤ T (n) ≤ d2n(log2(n))2 for some constants d1, d2 and all n ≥ 2. Note that the Master Theorem is not directly applicable here. However, you should prove this using a recursion tree analysis, similar to the one that was used to prove the Master Theorem in class. Hint: for each level j, estimate the number of subproblems at that level, and the local running time for each subproblem at that level. 4. Uneven divide and conquer (1). Suppose we have an algorithm that on problems of size n, if n ≥ 10, it recursively solves two subproblems, one of size b0.7nc and one of size b0.2nc. Furthermore, the “local running time” is O(n). Prove that T (n) = O(n) using a recursion tree analysis. Hint: Let Sj be the sum of all subproblem sizes at level j. Show that Sj+1 ≤ 0.9Sj for all j ≥ 0. To get started, suppose the subproblems at level j have sizes n1, . . . , nk, so Sj = ∑ i ni. 5. Uneven divide and conquer (2). Suppose we have an algorithm that on problems of size n, if n ≥ 10, it recursively solves two subproblems, one of size b0.9nc and one of size b0.1nc. Furthermore, the “local running time” is O(n2). Prove that T (n) = O(n2) using a recursion tree analysis. Hint: Let Sj be the sum of the squares of the subproblem sizes at level j. Show that Sj+1 ≤ 0.82Sj for all j ≥ 0. To get started, suppose the subproblems at level j have sizes n1, . . . , nk, so Sj = ∑ i n 2 i . 1 6. Roots to coefficients. You are to design an efficient algorithm for the following problem. The input is a list of elements a1, a2, . . . , an ∈ F , where F is some field. The output is the coefficient vector of the polynomial (X − a1)(X − a2) · · · (X − an) ∈ F [X]. For example, if the input is the 1, 2, 3, 4, the output would be (24,−50, 35,−10, 1), which is the coefficient vector of the polynomial (X − 1)(X − 2)(X − 3)(X − 4) = 24− 50X + 35X2 − 10X3 +X4. A simple but not very efficient algorithm would run as follows: f ← 1 for i ∈ [1 . . n] do f ← f · (X − ai) output f Note that in general, if we have f = c0 + c1X + · · ·+ cdXd, and a ∈ F , then we have f · (X − a) = −ac0 + (c0 − ac1)X + · · ·+ (cd−1 − acd)Xd + cdXd+1. This means that in the above algorithm, each loop iteration can be implemented so as to cost Θ(i) operations in F , and hence the total cost of the above algorithm is Θ(n2) operations in F . Your task is to design a faster algorithm for this problem. That is, your algorithm should use o(n2) operations in F . To this end, you may make use of a fast polynomial multiplication algorithm Mul that takes as input two polynomials in F [X] and outputs their product (inputs and outputs are represented by their coefficient vectors). You may assume that the algorithm Mul runs in time O(dα), where d is a bound on the degrees of the input polynomials, and α is a constant, where 1 < α="">< 2. use a divide and conquer strategy to design your algorithm. you may analyze the running time of your algorithm using the “master theorem” from class. 2 2.="" use="" a="" divide="" and="" conquer="" strategy="" to="" design="" your="" algorithm.="" you="" may="" analyze="" the="" running="" time="" of="" your="" algorithm="" using="" the="" “master="" theorem”="" from="" class.="">