1. (20 points) Consider a representation for integers of arbitrary length that uses a vector of integers to store each digit as a separate element. Each element in the vector is between 0 and 9 (inclusive) and together they represent a larger integer, with the least significant digit first. So, the vector:[83901] would represent the number 10,938. There are no leading zeros in the numbers. a. Write a function that takes two such vectors and returns a new vector in the same format) storing the product of the two inputs. You may assume as a precondition that the input vectors do not contain elements that are not single, positive digits. You should also enforce this as a postcondition on your output. Your solution must allow integers of arbitrary length without overflow. (For example, do not convert any vector to a single integer, since this doesn't allow arbitrary length.) Hint: do this like you would do multiplication by hand, digit-by-digit, using the "grade-school algorithm". b. What is the running time of your function in Big-O notation if both input vectors have size n? 2. (10 points) There is an algorithm for matrix multiplication that multiplies twonxn matrices by performing 7 recursive calls, each of which multiplies twon/2xn/2 matrices. The additional work performed during each call is O(n). a. Write a recurrence relation that describes the running time of the algorithm for a problem of size n. b. Use the Master Theorem (Lecture 07 - Recurrence relations.pdf ) to determine the running time of the algorithm using Big-O notation