def matvec_gen(n): ''' Function to generate a random matrix of dimension n x n and a random vector of length n ''' A = [[1] * n for i in range(n)] x = [1 for i in range(n)] return A, x 

def matvec_mul(A,x): ''' Function to multiply a matrix A and a vector x ''' n = len(x) b = [] for ii in range(0,n): new = 0 for jj in range(0,n): new = new + A[ii][jj]*x[jj] b.append(new) return b 

5. In class, we talked about matrix-vector multiplication and the time complexity of algorithms. This problem will integrate these topics as well as give you a first-hand encounter with time complexity. On Piazza, under the Resources tab, you will find two files: 1) matvec mul.py contains a Python function for multiplying an n x n matrix by an n-length vector, where n is the number of columns/rows. The inputs to the function are a matrix A and a vector r, and the function returns their product Ar 2) matvec-gen.py contains a Python function for generating an nx n matrix and an n-length vector You will find this useful for completing this problem. Download these files as they will help you analyze the complexity of matrix-vector multiplication (you are free to write your own functions if you would like, but make sure they work properly. In a nutshell your task will be to generate pairs of n n matrices/vectors of varying size n, run the matvec,mul algorithm on each of these pairs, plot the runtime of each input, and analyze the time complexity of matvec mul. (a) Generate pairs of n n matrices/vectors for each value of n (b) Run the matvecmul algorithm on these matrices 10.20.30. . . 100 (c) Compute the wall clock time and modify the matvec mul algorithm to compute the number of operations (additions +multiplications) for each value ofn. Report the total number of additions and multiplications for n 10, 20,30, 40 (d) On a coordinate plane, plot the total number of additions and multiplications (operations) for each n. Do a little bit of research to find out the function which gives the exact number of operations for matrix-vector multiplication. On the same coordinate plane, plot the graph of this function Write a short paragraph comparing these two graphs and commenting on whether they agree or not. Refer to the tutorial posted on Piazza (also under the Resources tab) if you're not familiar with plotting in Python. Label your axes and include this figure with your assignment. (e) On a separate coordinate plane, plot your computed wall clock time T(n) of matvec mul for each input size n. Find a function f(n) that approximately fits these data points. Label your axes and include this figure with your assignment 5. In class, we talked about matrix-vector multiplication and the time complexity of algorithms. This problem will integrate these topics as well as give you a first-hand encounter with time complexity. On Piazza, under the Resources tab, you will find two files: 1) matvec mul.py contains a Python function for multiplying an n x n matrix by an n-length vector, where n is the number of columns/rows. The inputs to the function are a matrix A and a vector r, and the function returns their product Ar 2) matvec-gen.py contains a Python function for generating an nx n matrix and an n-length vector You will find this useful for completing this problem. Download these files as they will help you analyze the complexity of matrix-vector multiplication (you are free to write your own functions if you would like, but make sure they work properly. In a nutshell your task will be to generate pairs of n n matrices/vectors of varying size n, run the matvec,mul algorithm on each of these pairs, plot the runtime of each input, and analyze the time complexity of matvec mul. (a) Generate pairs of n n matrices/vectors for each value of n (b) Run the matvecmul algorithm on these matrices 10.20.30. . . 100 (c) Compute the wall clock time and modify the matvec mul algorithm to compute the number of operations (additions +multiplications) for each value ofn. Report the total number of additions and multiplications for n 10, 20,30, 40 (d) On a coordinate plane, plot the total number of additions and multiplications (operations) for each n. Do a little bit of research to find out the function which gives the exact number of operations for matrix-vector multiplication. On the same coordinate plane, plot the graph of this function Write a short paragraph comparing these two graphs and commenting on whether they agree or not. Refer to the tutorial posted on Piazza (also under the Resources tab) if you're not familiar with plotting in Python. Label your axes and include this figure with your assignment. (e) On a separate coordinate plane, plot your computed wall clock time T(n) of matvec mul for each input size n. Find a function f(n) that approximately fits these data points. Label your axes and include this figure with your assignment