Aassignment will be submitted in Crowdmark and not in UM Learn. Proofs will be graded on both correctness and presentation. Clearly explain all of your steps. Two important comments:  No asymptotic notation may be used in any of the questions on this assignment.  Different questions will ask you to count different quantities. Read each set of instructions carefully. Questions 1. [8 marks] Find f(n), the number of primitive operations that the following program executes as a function of the input n. Show your work, and simplify your final answer until no summation notation appears. 1 //pre: (n is an integer) ? (n >= 1) 2 sum ? 0 3 j ? 1 4 m ? 2*n 5 while (j <= m) 6 k ? 1 7 while (k <= j) 8 prod ? j*k 9 sum ? sum + prod 10 k ? k+1 11 j ? j+1 Make sure that you count primitive operations and not steps. Refer to page 4 of CostFunctions 1 from this weeks lecture slides for a complete list of primitive operations. 1 2. Parts (a) and (b) below refer to the following code. Assume that A is an integer array of length n, where n = 1. 1 //pre: A.length >= 1 2 n ? A.length 3 j ? 0 4 while (j < n) 5 if (A[j] < 0) 6 k ? j+1 7 while (k < n) 8 A[k] ? A[k] + n 9 k ? k+1 10 j ? j+2 (a) [9 marks] Find f(n), the number of steps that the following program executes as a function of the array length n, in the worst case. Use the definition of a step discussed in pages 810 of CostFunctions 1 and used throughout the Week 4 content. You can assume that A.length is a primitive operation. Show your work, and simplify your final answer until no summation notation appears. You will have to consider separately the case where n is even and the case where n is odd. Write your answer as a piecewise-defined function of n: f(n) = ? ? ? f1(n), n even f2(n), n odd (b) [2 marks] Consider the specific instance where n = 7. Give an example of an array A of length 7 such that the worst case number of steps will occur if A is the input to this code. Briefly (1-3 sentences) justify why the worst case will occur when your example is used as the input. 2 3. Parts (a) and (b) below refer to the following code. Assume that A is an array of integers whose length n is even and at least 2. In this question, you will count array accesses, not steps. An array access is any instance in which a value A[k] is used in a calculation or comparison, or any instance in which a new value is assigned to A[k]. Do not count the operation A.length, since this command does not use a particular entry in A. 1 //pre: (A.length >= 2) ? (A.length is even) 2 n ? A.length 3 if (A[0] < A[n-1]) 4 i ? 0 5 while (i < n/2) 6 tmp ? A[i] 7 A[i] ? A[n-1-i] 8 A[n-1-i] ? tmp 9 i ? i+1 10 sum ? 0 11 j ? 0 12 while (j < n) 13 if (A[j] % 2 == 0) 14 sum ? sum + A[j] 15 else 16 k ? j 17 while (k < n) 18 sum ? sum + A[k] 19 k ? k+1 20 j ? j+1 (a) [8 marks] Find f(n), the number of array accesses performed in this code as a function of the array length n, in the worst case. Make sure you are counting array accesses and not steps. Show your work, and simplify your answer until no summation notation appears. (b) [2 marks] Consider the specific instance where n = 8. Give an example of an array A of length 8 such that the worst case number of steps will occur if A is the input to this code. Briefly (1-3 sentences) justify why the worst case will occur when your example is used as the input. 3 4. Let a0, . . . , an-1 and b0, . . . , bn-1 be two sequences of integers, both of length n, where n = 1. I want to write an algorithm to evaluate nX-1 i=0 X i j=0 (ai + bj ). Assume that the arrays A and B contain the values of my two sequences. That is, A.length=n, B.length=n, and A[i]= ai and B[i]= bi for all i, 0 = i = n - 1. In this question, you will count the number of times addition and multiplication are performed. Count every instance of the + or * operators, and do not count any other steps. In all cases, show your work and simplify your cost function until no summation notation appears. (a) [4 marks] Here is Version 1 of my algorithm. 1 //pre: A and B as described above 2 sum ? 0 3 i ? 0 4 while (i < n) 5 j ? 0 6 while (j <= i) 7 sum ? sum + A[i] + B[j] 8 j ? j+1 9 i ? i+1 Find f1(n), the number of additions performed by this code as a function of the sequence length n. (There is no multiplication.) (b) [4 marks] I notice that I can rewrite my sum as nX-1 i=0 X i j=0 (ai + bj ) = nX-1 i=0 ? ? X i j=0 ai + X i j=0 bj ? ? = nX-1 i=0 ? ?(i + 1)ai + X i j=0 bj ? ? . Using this new expression, I try to make my algorithm more efficient. Here is Version 2. 1 //pre: A and B as described above 2 sum ? 0 3 i ? 0 4 while (i < n) 5 sum ? sum + A[i]*(i+1) 6 j ? 0 7 while (j <= i) 8 sum ? sum + B[j] 9 j ? j+1 10 i ? i+1 4 For this new algorithm, find f2(n), the number of additions and multiplications performed as a function of the sequence length n. (c) [3 marks] Finally, I notice that I am repeatedly recalculating the same sum of B[j] terms. I rewrite my desired sum further as nX-1 i=0 X i j=0 (ai + bj ) = nX-1 i=0 ? ?(i + 1)ai + X i j=0 bj ? ? = nX-1 i=0 ((i + 1)ai + si), where the new term si is defined recursively by s0 = b0, si+1 = si + bi+1. Here is Version 3 of my algorithm. 1 //pre: A and B as described above 2 sum ? 0 3 innerSum ? 0 4 i ? 0 5 while (i < n) 6 sum ? sum + A[i]*(i+1) 7 innerSum ? innerSum + B[i] 8 sum ? sum + innerSum 9 i ? i+1 Find f3(n), the number of addition and multiplication operations performed by this algorithm as a function of the sequence length n. 5