Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

COMP 2080 Winter 2022 – Assignment 3 This assignment is due by 11:59pm on Wednesday March 2. Submission instructions. Your assignment will be submitted in Crowdmark and not in UM Learn. Proofs will be...

1 answer below »

COMP 2080 Winter 2022 – Assignment 3
This assignment is due by 11:59pm on Wednesday March 2.
Submission instructions. Your assignment will be submitted in Crowdmark and not in UM
Learn.
Proofs will be graded on both co
ectness 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 week’s 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 a
ay 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 a
ay length n, in the worst case. Use the definition of a step discussed
in pages 8–10 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 a
ay 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 a
ay of integers
whose length n is even and at least 2.
In this question, you will count a
ay accesses, not steps. An a
ay 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 a
ay accesses performed in this code as a function of
the a
ay length n, in the worst case. Make sure you are counting a
ay 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 a
ay A of
length 8 such that the worst case number of a
ay accesses 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
n−1∑
i=0
i∑
j=0
(ai + bj).
Assume that the a
ays 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
n−1∑
i=0
i∑
j=0
(ai + bj) =
n−1∑
i=0
 i∑
j=0
ai +
i∑
j=0
j
 = n−1∑
i=0
(i + 1)ai + i∑
j=0
j
 .
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
n−1∑
i=0
i∑
j=0
(ai + bj) =
n−1∑
i=0
(i + 1)ai + i∑
j=0
j
 = n−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
Answered 2 days After Feb 27, 2022

Solution

Chirag answered on Mar 01 2022
101 Votes
CamScanner 03-02-2022 18.10
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here