2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Question 2
10 / 10 pts
ASSUME THAT Foo(A[],n) TAKES ¦¨(n) TIME. Given the following code
The cost of executing line 4 is ci times. The outer loop runs n^2 .
The complexity T(n) ¦¨( n^4 ).
Answer 1:
ci
Answer 2:
n^2
Answer 3:
n^4
Correct!
Correct!
Correct!
True False
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 3/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Question 3
15 / 15 pts
Given the code below:
The inner loop (lines 5-7) runs approximately i^(1/2) times. The value of i on the first iteration is 1 .
The value of i on the second iteration is [ Select ]
The value of i on the last iteration is [ Select ]
The outer loop runs approximately [ Select ]
The sum created by expanding T(n) is a(n) [ Select ]
. .
times.
.
(An increasing sum is one whose terms get larger as the summation index increases, a decreasing sum is one whose terms get smaller as the summation index increases).
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 4/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
The complexity T(n) ¦¨( ).
Answer 1:
i^(1/2)
Answer 2:
1
Answer 3:
4
Answer 4:
n^3
Answer 5:
log_4 (n)
Answer 6:
increasing geometric sum
Answer 7:
n^(3/2)
[ Select ]
Question 4
15 / 15 pts
Given the following code
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 5/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
The recurrence relation is T(n)= cn^3 + T(n-3)
The following questions are about the recursion tree of this recurrence relation (you do not need to draw the tree, but it is easier to name entries in the tree than in the equivalent substitutions):
The total amount of work done at the root is cn^3 .
The total amount of work done at the first child level (the one directly under the root) is c(n-3)^3 .
The total amount of work done at the second child level (the one directly under the first child level) is c(n-6)^3 .
The height of the tree (or the total number of substitutions required) is approximately n/3 .
The total amount of work done at the ith level (or the pattern for the terms of the substitution) is c (n-3i)^3 .
And the asymptotic run-time of this algorithm is T(n) ¦¨( n^4 )
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 6/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Answer 1:
cn^3 + T(n-3)
Answer 2: cn^3
Answer 3: c(n-3)^3
Answer 4: c(n-6)^3
Answer 5: n/3
Answer 6:
c (n-3i)^3
Answer 7: n^4
Question 5
13.13 / 15 pts
Given the following code
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 7/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
The recurrence relation is T(n)= cn + 8T(n/2)
The following questions are about the recursion tree of this recurrence relation (you do not need to draw the tree, but it is easier to name entries in the tree than in the equivalent substitutions):
The total amount of work done at the root is cn
The total amount of work done at the first child level (the one directly under the root) is 4cn
The total amount of work done at the second child level (the one directly under the first child level) is 16cn
The height of the tree (or the total number of substitutions required) is log_2(n) .
The total amount of work done at the ith level (or the pattern for the terms of the substitution) is (4^i) cn . The formatting here isn’t great, I apologize!
The summation generated by summing the recursion tree from the root to the
leaves is a(n)
[ Select ]
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 8/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
ou Answered rrect Answer
And the asymptotic run-time of this algorithm is T(n) ¦¨(
[ Select ]
Answer 1:
cn + 8T(n/2)
Answer 2:
cn
Answer 3:
4cn
Answer 4:
16cn
Answer 5:
log_2(n)
Answer 6:
(4^i) cn
Answer 7:
)
increasing geometric summation
Answer 8:
n^3
n log(n)
Question 6
8.57 / 10 pts
Y o
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 9/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Given the following code:
Worst case:
In the worst case for loop on lines 6-12 runs approximately n times. This happens when k mod 6 > 2
In that case T(n) ¦¨( n^2 )
Expected Time:
The probability that the if statement in lines 9-11 is skipped is 4/6 .
Let X be the number of times that the if statement in lines 9-11 is skipped (i.e. does not return).
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 10/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
rrect Answer ou Answered
Correct!
Correct!
Correct!
The E(X) ¦¨( ET(n) = [ Select ]
Answer 1:
n
Answer 2:
k mod 6 > 2
Answer 3:
n^2
Answer 4:
3/6
Answer 5:
1
Answer 6:
cn^2 + c * E(X)
Answer 7:
n^2
) (recall ¦¨(1) means constant) ¦¨( n^2 )
4/6
[ Select ]
Question 7
10 / 10 pts
Given the following algorithm
o Y
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 11/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Worst Case Run Time
The recurrence relation for the worst case running time is T(n)= cn^2 + 8T(n/2) .
For the expected time:
Let ET(n) be the expected run time of the function with input of size n.
The probability that k is divisible by 3 on line 11 is 1/3 , so the expected time of lines 11-13 is (1/3) * ET(n/2)
The expected time for the loop in lines 9-14 is (8/3) * ET(n/2)
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 12/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
The recurrence relation for the expected time is ET(n) = cn^2 + (8/3) * ET(n/2)
Answer 1:
cn^2 + 8T(n/2)
Answer 2: 1/3
Answer 3:
(1/3) * ET(n/2)
Answer 4:
(8/3) * ET(n/2)
Answer 5:
cn^2 + (8/3) * ET(n/2)
Question 8
2.5 / 5 pts
The Open-Address hash-table below was filled by the function h(K,j)=(K+3j)mod 9.
Which of the following keys results in an overflow error when inserted into the Hash Table? Select ALL answers that apply.
Note: you are not actually inserting ANY of these elements, consider each element independently and perform no actual insertions.
(9,D9) (20,D20)
0
1
2
3
4
5
6
7
8
(10,D10)
(11,D11)
(5,D5)
(6,D6)
(26,D26)
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 13/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
ou Answered
Correct!
(21,D21) (14,D14) (25,D25)
(15,D15)
Question 9
10 / 10 pts
Given the following code
Y
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 14/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Assume the Hash Table is implemented using Open Address Hashing and that the size of the table is at least 2n.
Expected Case:
The body of the for loop takes c time in the expected case. Therefore, the expected runtime ET(n) ¦¨( log(n) ).
Worst Case:
The body of the for loop takes ci time in the worst case. Therefore, the worst case runtime T(n) ¦¨( log(n)^2 ).
Answer 1:
c
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 15/17
2021/4/19 Midterm 1 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Question 10
5 / 5 pts
Suppose that
Algorithm A has a best case running time of ¦¨(n^2)
Algorithm A has a worst case running time of ¦¨(n^3 log(n))
Which of the following are valid expected case running times for Algorithm A?
Select ALL that apply!
¦¨(log(n))
¦¨(n log(n)) ¦¨(n^2)
¦¨(n^2 log(n)) ¦¨(n^2 / log(n)) ¦¨(n^3)
¦¨(n^3 / log(n)) ¦¨(n^4)
Correct! Correct!
Correct! Correct!
Answer 2: log(n)
Answer 3: ci
Answer 4: log(n)^2
https://osu.instructure.com/courses/95559/quizzes/513559?module_item_id=5958712 16/17