Major  Graded

Student
Tanvi Mathur

Total Points
49 / 85.34 pts

Question 1
1 10 / 10 pts

1.1 1.1 5 / 5 pts

 − 0 pts Correct

− 5 pts Incorrect

− 4 pts Ouptut correct till first level (counting from 0)

− 3 pts Ouptut correct till second level

− 2 pts Ouptut correct till third level

− 1 pt Ouptut correct till 4th level

1.2 1.2 5 / 5 pts

− 1.5 pts Base case/termination case missing/incorrect

− 2 pts Log base missing but explanation correct

− 4 pts Answer correct but explanation missing/incorrect

− 2 pts Answer correct with but partially correct explanation

− 5 pts Incorrect/Unattempted

− 1 pt m taken as constant, rather than variable

 − 0 pts All Correct

Question 2
2 8.5 / 10 pts
+ 0 pts Incorrect/not-attempted

+ 10 pts correct

 + 0.5 pts Correct base case of recursion, (method 1)A[0] or (method 2)A[len(A)-1]

 + 2.5 pts Correct recursive call,

(method 1)A[n]*x**n + R_Polyeval(A,n-1,x)
(method 2)A[len(A)-(n+1)] + x*R_Polyeval(A,n-1,x)

 + 1 pt Time Complexity for Recursion is correct, O(n) or O(nlogn)

 + 2 pts Correct derivation for the time complexity of recursion (method 1)T(n) = T(n-1) +logn or (method 2)T(n) =
T(n-1) + c

 + 0.5 pts Correct arguments for iterative case loop (1,n+1) or (1,len(A))

 + 1.5 pts Correct updation inside the loop, result+=A[i]*(x**i)

 + 0.5 pts Time Complexity of Iterative case is correct, O(n) or O(nlogn)

+ 1.5 pts Correct Derivation of TC for iterative case

+ 4 pts correct iterative case

 "**" operator takes O(logn) times

Question 3
3 4 / 5 pts
+ 5 pts Correct Answer

 + 1 pt Partially Correct Answer : computed conjugate correctly

return Complex(self.real, -self.imaginary)

 + 2 pts Partially Correct Answer : computed the division correctly

mag = c.mag()
product = self.mul(c.conjugate())
return Complex(product.real / mag, product.imaginary / mag)

+ 1 pt Partially Correct Answer : computed the division correctly but there are minor errors in the code

+ 2 pts Partially Correct Answer : computed reciprocal correctly

conjugate = self.conjugate()
mag = self.mag()
return Complex(conjugate.real / mag, conjugate.imaginary / mag)

 + 1 pt Partially Correct Answer : computed the reciprocal correctly but there are minor errors in the code

+ 0 pts Wrong Answer / Not Attempted

Question 4
4 10 / 10 pts

 − 0 pts Correct

− 1.5 pts intialization condition inside i loop (eg sum=0) is not correct

− 1 pt abs function is not used while calculating sum

− 1.5 pts if condition is not correct before return false statement

− 4 pts i==j not handled

− 10 pts Incorrect/Not Attempted

− 1 pt Range for inner loop incorrect

− 1 pt Range for outer loop incorrect

Question 5
5 7 / 10 pts
− 0 pts Correct

− 10 pts Incorrect / NA

− 7 pts brute force or TC more than O(n + m)

− 4 pts Correct Algorithm but complexity analysis missing/incorrect

 − 3 pts Algorithm partially incorrect

− 2 pts Complexity explanation partially incorrect

 c update step incorrect

Question 6
6 0 / 5 pts
− 0 pts Correct answer

 − 0.67 pts First loop: statement 1(count of 1s) incorrect

 − 0.67 pts First loop: statement 2 (count of 2s) incorrect

 − 0.66 pts First loop: statement 3 (count of 3s) incorrect

 − 1 pt Second loop: statement 1 (correct placement of 1s) incorrect

 − 1 pt Second loop: statement 2 (correct placement of 2s) incorrect

 − 1 pt Second loop: statement 3 (correct placement of 3s) incorrect

− 2 pts First loop is correct, the second loop is not O(n)

− 4 pts Solution is not O(n)

− 1 pt Partially incorrect placements

Question 7
7 1 / 5 pts
+ 5 pts Correct solution ( n2 logn) with all steps correct (other rubrics do not apply)

 + 2 pts Substitution steps are correct

+ 0.5 pts Termination case identification is correct

+ 2 pts Summation of n2 + (n/2)2 ... part for complexity calculation is correct

+ 0.5 pts Correct identification of dominant term in expression

+ 0 pts No submission/ Incorrect submission

 − 1 pt partially correct substitution

1 wrong expression, and answer

Question 8
8 0 / 10 pts
+ 1.33 pts For part 1
The two loop blanks - 1.33 mark
All other blanks - 1.33 mark each

+ 2.67 pts For part 1: Two blanks correct

+ 4 pts For part 1: Three blanks correct

+ 5.32 pts For part 1: Four blanks correct

+ 6.65 pts For part 1: Five blanks correct

+ 8 pts For part 1: Completely correct. All the 6 blanks are correct.

+ 2 pts For part 2: Correct answer

min_cost = min(M[r-1])
np = M[r-1].count(min_cost)

+ 0 pts Part 2: Considered all the paths that contribute towards the minimum cost for reaching the cells at the last
row.

 + 0 pts Completely incorrect

+ 0.5 pts partial mark for part2

Question 9
9 Resolved 0.5 / 5 pts
+ 0 pts Wrong/Not attempted

 + 1 pt Algorithm always terminates with a value

+ 2 pts (Prime case) Returned Value is always correct for any natural number input i.e.
For all integer I, in range (0, m),
m is not divisible by I i.e. m % I > 0

+ 2 pts (Non-Prime case) Returned Value is always correct for any natural number input i.e.
For any integer K, in range (m, n],
there exists an integer, I in (0, K),
s.t. K is divisible by I i.e. K % I = 0

 − 0.5 pts Informal Statement

 Regrade Request Submitted on: May 11

I have tried to prove that numbers greater than m//2 can never divide m. So if 2<i<m//2
never divided m it is prime.

marks awarded are correct

Reviewed on: May 12

Question 10
10 2 / 5 pts
+ 5 pts ---------------- Correct answer ----------------
Loop invariant 1 : m ≤ Lx , ∀x ∣ 0 ≤ ​ x<i
Loop invariant 2 : m ≤ Lx , ∀x ∣ 0 ≤ x ≤ i
​

def min(L) :
m = L[0]
for i in range( 1, len(L) ):
.# Loop invariant : m <= L_x, for all x<i
if L[i] < m : m = L[i]
.# Loop invariant : m <= L_x for all x<=i
return m

---------------- Alternatnative ----------------

Loop invariant 1 : m ≤ Li−1 ​

Loop invariant 2 : m ≤ Li ​

---------------- Alternatnative ----------------

Loop invariant 1 : m = min( L[0 : i])
Loop invariant 2 : m = min( L[0 : i + 1] )

 + 2 pts Consolation mark :

• m ≤ Li ​

• m ≤ Li ? ​

• Li< m → m = Li ​

• m < Li , ∀i ∣ 0 ≤ i < Len(L)

​

• m = min( L[0 : i] ) ∣∣ m = min( L[0 : i + 1] )

+ 1 pt ( only if above marks are inapplicable )

Consolation mark :
•L
• L[0]
• L[i]
• Len(L)
• i < Len(L)
•i ∈ [ 1, len(L) )

+ 0 pts Incorrect / Unattempted / Ambiguous / Irrelevant /

Insignificant : (i, m)

Question 11
11 5 / 5 pts

 + 1 pt Partially correct return statement in the line function as a, b, c are not passed as list

 + 1 pt Partially correct return statement in the plane function as a,b,c,d are not passed as list

 + 2 pts Correct Final Output:

yvalue = [0,-1,-2,-3,-4]

+ 0 pts Incorrect or No Solution

 + 1 pt Correct return statement in the line and plane function where a,b,c,d are passed as a list:

Line function:
return linear([a,b,c])

Plane function:
return linear([a,b,c,d])
Question 12
bonus 1 / 5.34 pts
+ 5.34 pts Correct

+ 2.34 pts In worst case time complexity, the sub problems chosen will always be of length 2 ∗ n/3

Hence the recurrence relation will be T (n) = T (2 ∗ n/3) + O(1)

+ 2 pts Solving the recurrence relation we get the worst case time complexity as O(log 3 n). ​

2 ​

 + 1 pt As O(log 3 n) ​
log2 n
= O( log 3 ) = O(logn)
​

2 ​

2
​

2 ​

+ 0.5 pts Correct time complexity but explanation missing

+ 1 pt Partially correct recurrence.

T (n) = T (n/3) + T (2 ∗ n/3) + O(1) or
T (n) = T (n/3) + O(1)

+ 1 pt Solved the partially correct recurrence.

+ 0 pts Incorrect or no solution

 You are supposed to divide the array into two unequal parts not into three parts
1