2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct! rrect Answer
Correct!
All of the following questions pertain to the binary search tree given below
The height of the given tree is 4 . (Input should be a non- negative integer).
We shall perform the following operation T.Insert(19)
The newly inserted node will be inserted as the right (input your answer as EXACTLY ¡°left¡± or ¡°right¡± without the quotation marks) child of
15
The height of the tree after insertion is 4 .
Answer 1:
4
Answer 2:
right Right
Answer 3:
15
(input should be a non-negative integer).
Answer 4:
o
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 3/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Question 2
3 / 3 pts
Given the binary search tree
the successor of 7 is 8 (input should be a non-negative integer).
Answer 1:
8
Correct!
4
Question 3
0 / 5 pts
Consider the following diagram:
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 4/20
Y
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
ou Answered
rrect Answer
Correct!
Given no prior knowledge on the height of the trees rooted at x, y, and z; as a result of performing a Left Rotate on node y, the height of the child of p where y used to be will:
Decrease by 1
Stay the same
Stay the same or increase by 1
Stay the same or decrease by 1
Stay the same, increase by 1, or decrease by 1
Increase by 1
Question 4
3.5 / 3.5 pts
The minimum value stored in a Binary Search Tree is always
The leaf that has the longest path from the root The leftmost value in the tree
o
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 5/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Question 5
3.5 / 3.5 pts
It is possible to know if two elements in a Binary Search Tree are inorder just by using the positions in the tree (i.e. without comparing them).
True False
Correct!
The rightmost value in the tree.
There is not enough information to determine the minimum
Question 6
10 / 10 pts
Given the code below where D is a priority queue and
P.Insert(x) takes ¦¨(s) time where s is the number of elements in the heap. P.ExtractMax() takes ¦¨(1) time where s is the number of elements in the heap.
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 6/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Select the answers that best match:
Suppose the size of the priority queue is initially 1.
The size of the data structure after the first while loop (lines 4-7) finishes executing is [ Select ] .
The runtime of the while loop on lines 4-7 is ¦¨( log(n)^2 ).
The size of the data structure on line 8 before the second while loop starts
execution is [ Select ]
The loop on lines 9-11 removes [ Select ]
the data structure.
The runtime of the loop on lines 9-11 is ¦¨(
.
[ Select ] The total run-time of the program is ¦¨( [ Select ]
elements from
). ).
Answer 1:
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 7/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
log(n)
Answer 2: log(n)^2
Answer 3: log(n)
Answer 4: log(n)
Answer 5: log(n)
Answer 6: log(n)^2
Question 7
8.33 / 10 pts
Given the code below where D is a priority queue implemented as a Max-Heap and
D.Insert(x) takes ¦¨(log(s)) time where s is the number of elements in the heap.
D.ExtractMax() takes ¦¨(log(s)) time where s is the number of elements in the heap.
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 8/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Select the answers that best match:
Suppose the heaps size is initially 1.
The size of the heap after the first loop (lines 3-5) finishes executing is
[ Select ]
.
The runtime of the loop on lines 3-5 is ¦¨( n^2 log(n) ).
The size of the heap on line 6 before the while loop starts execution is
[ Select ]
The loop on lines 7-11 removes [ Select ]
the heap.
The runtime of the loop on lines 7-11 is ¦¨( [ Select ]
The total run-time of the program is ¦¨( [ Select ] Answer 1:
.
elements from
). ).
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 9/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
ou Answered rrect Answer
Correct!
Correct!
Correct!
Question 8
5 / 5 pts
Given a Min-Heap, what is the time required to FIND (not extract) the minimum element of the Min-Heap?
¦¨(1) ¦¨(log(n)) ¦¨(n)
¦¨(n log(n))
Correct!
n^2
Answer 2: n^2 log(n)
Answer 3:
n^2
Answer 4:
log(n)
Answer 5:
log(n)^2
Answer 6:
n^2 log(n)
n
Y o
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 10/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Question 9
5 / 5 pts
Giventheflowingarrayrepresentingamax-heap:[53, 31, 46, 22, 16, 41, 21, 14, 3, 13, 9],performtheHeapExtractMaxoperationonit and enter the values of the resulting array below:
[ 46 , 31 , 41 , 22 ,16 ,9 , 21 ,14 ,3 , 13
Answer 1:
31
Answer 2:
41
Answer 3:
22
Answer 4:
16
Answer 5:
9
Answer 6:
21
Answer 7:
14
]
Answer 8:
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 11/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
3 Answer 9:
13
Question 10
13.33 / 15 pts
Given the following code:
Worst Case Run Time
The worst case asymptotic run-time of this algorithm being T(n) ¦¨( n log(n) )
For the expected time:
Let ET(n) be the expected run time of Func with input of size n.
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 12/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
The probability that k mod 5 = 0 is 1/5 , so the expected time of lines 11-13 is (1/5) * ET(n/5)
The expected time for the loop in lines 9-14 is ET(n/5)
The recurrence relation for the expected time is ET(n) = cn + ET(n/5)
The following questions are about the recursion tree of this recurrence relation (note you do not need to use a recursion tree and can instead use substitution):
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 n/5
The total amount of work done at the second child level (the one directly under the first child level) is n/25
The work on each level yields a decreasing geometric series series from the root to the leafs.
The asymptotic expected run-time of this algorithm being T(n) ¦¨( n log(n) ) Answer 1:
n log(n)
Answer 2: 1/5
Answer 3:
(1/5) * ET(n/5)
Answer 4: ET(n/5)
Answer 5:
cn + ET(n/5)
Answer 6: n/5
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 13/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
rrect Answer ou Answered
rrect Answer ou Answered
Answer 7: n/25
Answer 8:
decreasing geometric series
Answer 9: n
n log(n)
Question 11
0 / 5 pts
Assume that D is a Priority Queue implemented as a Max-Heap and that T is a binary search tree. Assuming that D initially has n elements and the binary search tree is initially empty, what is the height of T after the following code snippet executes?
¦¨(1) ¦¨(log(n)) ¦¨(n^(1/2)) ¦¨(n)
¦¨(n log(n))
o Y
o Y
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404
14/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
¦¨(n^2)
We cannot say given the information provided.
Question 12
5 / 5 pts
Color the nodes in the binary search tree below so that it is a Red-black tree. Your answer should be input exactly as “red” or “black” (without the quotation marks).
Node 6 is black Node 11 is red. Node 21 is red
Node 40 is black Node 46 is red
Node 48 is black Node 49 is
.
. .
.
. .
black
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 15/20
2021/4/19
Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct! rrect Answer
Correct! rrect Answer
Correct! rrect Answer
Correct! rrect Answer
Correct! rrect Answer
Correct! rrect Answer
Node 57 is red . Node 64 is black . Node 69 is red .
Answer 1:
black
Black
Answer 2:
red Red
Answer 3:
black Black
Answer 4:
red Red
Answer 5:
black Black
Answer 6:
black Black
o
o
o
o
o
Node 49 is
.
o https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404
16/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct! rrect Answer
Correct! rrect Answer
Correct! rrect Answer
Question 13
5 / 5 pts
True or false: The minimum value in a red-black tree is always the root
True False
Correct!
Answer 7: red
Red
Answer 8: black Black
Answer 9: red
Red
Question 14
10 / 10 pts
Answer the following questions about applying the method RBTreeInsert to insert the value of 24 to the red-black tree below. (As in class, black nodes have circles and red nodes have squares).
o
o
o
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 17/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
The initial color for the newly inserted node (before any fixes are applied) is red . The newly added node will be a 25 .
This violates the Red-Black tree rule that If a node is red, then both its children are black .
As a result we will need to fix the tree by first applying Case 1 (RBInsertFixupA) so Recoloring the parent, auncle, and grandparent of z .
As a result of this, the problem is fixed for the newly inserted node. However, node 35 is now a problem.
We fix the tree by first applying Case 1 (RBInsertFixupA) which performs the operation of Recoloring the parent, auncle, and grandparent of z .
The new problem node is now 43 which can be fixed by Coloring the root black .
Answer 1:
red
Answer 2:
25
Answer 3:
If a node is red, then both its children are black
Answer 4:
Case 1 (RBInsertFixupA)
Answer 5:
Recoloring the parent, auncle, and grandparent of z
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 18/20
2021/4/19 Midterm 2 (Remotely Proctored): SP21 CSE 2331 – Fndns 2: DS & Alg (8525)
Correct!
Correct!
Correct!
Correct!
Correct!
Correct!
Answer 6: 35
Answer 7:
Case 1 (RBInsertFixupA)
Answer 8:
Recoloring the parent, auncle, and grandparent of z
Answer 9: 43
Answer 10:
Coloring the root black
Question 15
5 / 5 pts
Consider a version of table expansion where we increase the size of the table by 100 whenever the table is full. (For instance, a table with size 10 is expanded to size 110. A table with size 100 is expanded to size 200.) Each insertion without table expansion takes ¦¨(log(s)) time, where s is the number of elements in the table. Table expansion takes ck time where k is the number of elements in the new table. Initially, the table is empty and has size 4.
What is the Amortized run-time of each insertion (i.e. (Total cost of n insertions)/n)
Constant or ¦¨(1) Logarithmic or ¦¨(log(n)) Linear or ¦¨(n)
https://osu.instructure.com/courses/95559/quizzes/523230?module_item_id=6066404 19/20