SOLVED EECS 376 Homework 3

 1. The ideas behind the Karatsuba algorithm can be applied to multiply things other than integers. Let A(x) = a0 + a1x + · · · + an−1x n−1 and B(x) = b0 + b1x + · · · + bn−1x n−1 be two polynomials of degree at most n − 1. For simplicity, assume that n is a power of 2, and that any arithmetic operations (e.g., addition, multiplication) between two coefficients can be done in constant time. Give a Divide-and-Conquer algorithm to compute the coefficients of the product polynomial A(x) · B(x) in O(n log2 3 ) time, and prove its correctness and running time. Solution: 2. Design an algorithm that given two positive integers x and y, computes x y , using O(log y) integer multiplications. You can assume that multiplying any two integers takes 1 operation. For example, computing x 2 takes 1 operation. Hint: Consider the cases when y is even and y is odd separately. Solution: 3. Consider the recurrence T(n) = √ n · T( √ n) + O(n). (a) Explain why the master theorem cannot be applied directly to give a closed form for T(n). (b) Define S(n) = T(n)/n. Using substitution, write a recurrence for S(n). (c) Let n = 2m and define R(m) = S(2m) = S(n). Using this substitution, write a recurrence for R(m). (d) Use the Master Theorem and the above recurrence to get an asymptotic expression for R(m), then use it to get asymptotic expressions for S(n) and finally T(n). 1 EECS 376: Foundations of Computer Science  Homework 3 Due 8:00pm, Sept 20 (accepted until 9:59 pm, no credit after) Hint: You may need to use that √ n = √ 2m = 2m/2 Solution: 4. Rank the following recurrences by asymptotic growth. You must show all work. • T(n) = 9T(n/4) + 1 • U(n) = 6U(n/4) + n 1.5 log2 n • V (n) = 8V (n/4) + n 1.5 Solution: 5. The matrix Ht is a n × n matrix where n = 2t . It is defined recursively, where H0 = (1), and in general, Ht+1 =  Ht Ht Ht −Ht  For example, H2 =   1 1 1 1 1 −1 1 −1 1 1 −1 −1 1 −1 −1 1   Given a vector x ∈ Z n , there is a trivial algorithm that uses O(n 2 ) operations to compute the matrix-vector product Htx, by first computing the matrix Ht and then computing its product with x. Describe an algorithm that computes Htx in O(n · t) = O(n log n) operations. Note: Recall how matrix vector multiplication works. If we have a n × n matrix A and a vector x ∈ Z n , their product is calculated by taking the dot product of x with each row in A. (That is, if the row is [a1, a2, ..., an] and x =      x1 x2 . . . xn      , then the dot product is a1x1 + a2x2 + ... + anxn). For example, here we have a 2 × 2 matrix A and a vector x ∈ Z 2 . Ax =  a b c d x1 x2  =  ax1 + bx2 cx1 + cx2  Moreover, instead of multiplying each individual row and column, we can also multiply matrices in blocks. For example, if we have a 4 × 4 matrix A and a vector x ∈ Z 4 , we can break A into 4 smaller matrices, say 2 × 2 matrices H, I, J, K. We can also break x into 2 vectors ~x1 and ~x2 each of size 2. This would give the following formulation of the product Ax. Ax =  H I J K ~x1 ~x2  =  H~x1 + I~x2 J~x1 + K~x2  . 2 EECS 376: Foundations of Computer Science