This is a CIS problem. please do all parts of the question. Thank you!

5. (14 pts.] Consider the typical matrix-vector multiplication operation: given a (dx ) matrix A (i.e., a squared matrix with d rows and d columns), and a d-dimensional (row) vector . (i.e., a vector with d elements; or equivalently, a matrix with d rows and a single column), where d is a positive integer, compute the d-dimensional (row) vector y = Ar. That is, using 0-based indexing, for all i = 0,1,...,0-1, y = 2;-) 234;, where az; is the element in the ith row and jth column of matrix A. Consider the following algorithm, MATRIX VECMULT (Algorithm 5), for this operation, assumming that A and 3 are represented using 2-dimensional and 1- dimensional arrays, respectively, as typically done. The algorithm uses an auxiliary algorithm, VECMULT (Algorithm 6), which takes as input two arrays of numbers, z and x, and a positive integer d, where the size of both z and or is at least d. Assume that the input to this auxiliary algorithm VECMULT (Algorithm 6) is passed by value. Algorithm 5 MATRIXVECMULT(A. 1, d) 1: y = new 1-dim array of d numbers 2: new 1-dim array of d numbers 3 for 10 to d=1 do for: 0 to d- I do yli E VECMULT(2, 1.d) Te return y Algorithm 6 VECMULT(2, 1, d) 1: if do then return 0 2: return z[d 11*1d-1+ VECMULT(z.r. d = 1) (a) Provide the tightest characterization possible of the running time and space complexity of the algorithm MATRIX VecMULT (Algorithm 5), using either big-Oh and big-Omega, or simply big-Theta, as a function of the input value d. Tirre Space (b) Provide the tightest characterization possible of the running time and space complexity of the same algorithm MatrixVecMutt (Algorithm 5), using either big-Oh and big- Omega, or simply big-Theta, now as a function of the input size n; that is, n characterizes the size of the input to the algorithm as a function of the input value d. Time Space (c) Is this a linear-time algorithm? Please circle your answer and explain briefly but clearly. In addition, if you answered 'No'. please clearly state what type of algorithm it is in terms of running time. Yes No (d) Please write, using pseudocode. a linear-time and linear-space algorithm for the same task