4. (20 points total - Matlab coding) In this problem you will design and analyze a...

Transcribed Image Text:

4. (20 points total - Matlab coding) In this problem you will design and analyze a divide and conquer algorithm that uses similar ideas to the fast Fourier transform (look up the fast Fourier transform algorithm in the textbook, and in particular "matrix block multiplication" in Section 2.5, if you need more ideas to get started). Consider the family of matrices recursively defined as follows: matrix Mo= 1, namely, the 1-by-1 matrix consisting of the number 1; and for each positive integer k the matrix M is a 2*-by-2* matrix defined by combining 4 copies of the smaller matrix Mk-1 as Mk Mk-1 [3-flip(x-1)] where the function "flip" flips a matrix vertically. Your goal is to construct an O(nlogn) algorithm so that given a column vector v of length n = 2*, you return the product Mxv. (a) (15 points) Fill in the provided stencil weirdmultiply.m. You might find the Matlab function flip useful: it flips the order of elements of a vector. (b) (5 points) As in the previous problem, add a few lines of comments explaining as clearly as possible why your code is correct; and explain its runtime. (As a warning and hint, your algorithm cannot construct Mx, since this would take time n, which is more than you are allowed. Instead, taking inspiration from the fast Fourier transform algorithm, try to design a divide-and-conquer algorithm for multiplying by these matrices Mk that, on input of size n = 2k, makes 2 recursive calls of size = 2*-1, and then does O(n) additional work to manipulate the results into the correct answer. Note that the obvious recursive algorithm would make 4 recursive calls of size to deal with each of the 4 submatrices in the definition of Mk, but 4 is too slow for us and we can only afford 2 recursive calls if we want to run in O(nlogn) time.) 4. (20 points total - Matlab coding) In this problem you will design and analyze a divide and conquer algorithm that uses similar ideas to the fast Fourier transform (look up the fast Fourier transform algorithm in the textbook, and in particular "matrix block multiplication" in Section 2.5, if you need more ideas to get started). Consider the family of matrices recursively defined as follows: matrix Mo= 1, namely, the 1-by-1 matrix consisting of the number 1; and for each positive integer k the matrix M is a 2*-by-2* matrix defined by combining 4 copies of the smaller matrix Mk-1 as Mk Mk-1 [3-flip(x-1)] where the function "flip" flips a matrix vertically. Your goal is to construct an O(nlogn) algorithm so that given a column vector v of length n = 2*, you return the product Mxv. (a) (15 points) Fill in the provided stencil weirdmultiply.m. You might find the Matlab function flip useful: it flips the order of elements of a vector. (b) (5 points) As in the previous problem, add a few lines of comments explaining as clearly as possible why your code is correct; and explain its runtime. (As a warning and hint, your algorithm cannot construct Mx, since this would take time n, which is more than you are allowed. Instead, taking inspiration from the fast Fourier transform algorithm, try to design a divide-and-conquer algorithm for multiplying by these matrices Mk that, on input of size n = 2k, makes 2 recursive calls of size = 2*-1, and then does O(n) additional work to manipulate the results into the correct answer. Note that the obvious recursive algorithm would make 4 recursive calls of size to deal with each of the 4 submatrices in the definition of Mk, but 4 is too slow for us and we can only afford 2 recursive calls if we want to run in O(nlogn) time.)