Comp 251: Mid-term examination
March 10, 2022
• Answer the questions in Crowdmark.
– Q1 contains True/False questions. Q2 contains multiple choice questions. Click the correct responses directly in Crowdmark
Copyright By PowCoder代写 加微信 powcoder
– Q3 and Q4 are composed of text questions (i.e., questions that require short typed answers). For these you answer directly in the text box provided.
• The exam will be open from 2:30 pm to 4:10 pm. We cannot accept late submissions, and Crowdmark may lock at any time after your timer reaches 0.
• The prompt for each question will appear above its corresponding text box. It is your responsibility to guarantee that you submit your answers in the right place. Answers submitted under the wrong question may not be graded.
• The clarity and presentation of your answers is part of the grading. Answers poorly presented may not be graded. This includes the clarity of the writing.
• The allowed material is:
– Everything that is posted in myCourses and Ed-Lessons. – The two reference books. •
The material that is not allowed:
– Google and other search engines.
– StackOverflow and other Q&A sites. – Chegg and comparable websites.
• It is strictly forbidden to use any external help, including online tutoring systems, or to provide aid to someone else. You are not allowed to communicate to anyone during the exam.
• This exam contains a mandatory academic integrity statement that you should agree with and sign. We will not grade the exam otherwise.
True or False
1. Please select the right answers.
(a) (1 point) For a specific algorithm, its best case running time is always asymptotically strictly lower than its worst case running time.
(b) (1 point)
(c) (1 point)
If f(n) is O(g(n)), then g(n) is O(f(n)) B. False
Performing one rotation always preserves the AVL property.
(d) (1 point)
with n elements is at most n − 1.
(e) (1 point)
(f) (1 point)
(g) (1 point)
A fixed-length encoding is always a prefix code.
Assuming that T1 is O(f) and that T2 is O(f), then T1 T2
An AVL tree with 7 nodes could be of height 4.
The number of unique, successive UNION operations in a union-find data structure
COMP 251 – Midterm #1 Page 3 of 16
Winter 2021
Multiple Choice
2. Please select the right answers.
(a) (5 points) Consider the AVL tree below:
We want to insert a new key with value 20 in the tree. Only one of the following trees represents an intermediate step in the insertion process, which is that tree?
15 10 25 10 15 25
(b) (4 points) We created an AVL tree which contains n × 2n elements. Which of the following
options is the tightest Big-O complexity for searching an element in that AVL?
A. O(n×log(n)) B. O(n×2n)
C. O(n) Explanation:
= O(log(n × 2n))
= O(log(n)) + O(log(2n))
= O(log(n)) + O(nlog(2))
= O(log(n)) + O(n)
D. O(log(n))
E. Any of the previous options is right.
(c) (5 points) Consider the following red-black tree (on which we omit the nil nodes).
COMP 251 – Midterm #1 Page 4 of 16 Winter 2021
A. One B. Two C. Three
50 65 80 90
We want to insert the node 35. Which cases are found during the insertion (and re-balancing of the tree)?
A. Case1andCase2
B. Case 1 and Case 3
C. Case2andCase3
D. Case1,Case2andCase3
E. Any Case, because the given tree is not a red-black tree
(d) (3points) WhichofthefollowingstatementsistruewhensolvingtherecurrenceT(n)=8T(n/8)+ n3.5 using the Master Theorem.
A. It can be solved using case 1 of the Master Theorem.
B. It can be solved using case 2 of the Master Theorem.
C. It can be solved using case 3 of the Master Theorem.
D. It can not be solved using the Master Theorem because it does not hold the regularity condi- tion of case 3.
E. It can not be solved using the Master Theorem because none of the initial conditions of the three cases apply to it.
(e) (3 points) Given the following min-heap, how many nodes will change their place once we have deleted the node 2.
COMP 251 – Midterm #1
Page 5 of 16
Winter 2021
E. The given tree is not a min-heap
COMP 251 – Midterm #1 Page 6 of 16 Winter 2021
(f) (3 points) Which will be a tight upper bound for the following code:
public static int mistery(int n) {
int count = 0;
if (n < 1000) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = 0; k < n*n; k++) {
for (int i = 0; i < n; i++) {
return count;
A. O(1) B. O(n) C. O(n2) D. O(n3) E. O(n4)
COMP 251 - Midterm #1
Page 7 of 16
Winter 2021
Text Questions - miscellaneous
(8 points) Given the following integers {1, 2, 3}, notice that if we insert those integers into an empty AVL tree in the following order 2 1 3, we will perform zero rotations when the numbers are inserted.
Now, given the following integers {9, 1, 4, 5, 8, 3, 6}, please report the sequence in which these integers must be inserted into an empty AVL tree such that no rotations are performed to balance the tree.
(the order within parenthesis can change) 5 (3 8) (1 4 6 9)
4 (1 8) (3 5 6 9)
4 (6 3) (1 5 8) 9 or 4 (6 3) (1 5 9) 8
6 (3 8) (1 4 9) 5 or 6 (3 8) (1 5 9) 4
6 (4 8) (5 9 3) 1 or 6 (4 8) (5 9 1) 3
6 (4 9) (5 8 1) 1 or 6 (4 9) (5 8 1) 3
-8 pts if there is no answer or it can not be marked.
-8 pts if the answer results in rotations
-2 pts the reported tree is the right sequence, but it is incomplete (apply this comment for each missing node)]
(b) (11 points) Simulate the behavior of a hash table storing integers given the following conditions:
• The initial array length is m = 5.
• The set uses linear probing for collision resolution.
• The used hash function is h(k, i) = (h′(k) + i) mod m, where h′(k) = k
• When the load factor exceeds 0.5, the table enlarges to double capacity (i.e. m = 2m) and then rehashes all the stored values, from index 0 to m − 1.
• Aninsertionfailsifstrictlymorethanhalfofthebuckets(i.e.,ifnum_hits>m/2evaluates to true) are tried without success.
Please insert the following numbers 37, 27, 7, 47, 17, 57 based on the conditions mentioned above and answer the following questions.
COMP 251 – Midterm #1 Page 8 of 16 Winter 2021
i) Did any value fail to be inserted? If so, type the number, if not, type NA.
-2 pts there is no answer or it can not be marked. -2 pts the reported number is not NA]
ii) Type the final size of the table.
-3 pts there is no answer or it can not be marked. -3 pts the reported number is not 20]
iii) What is the load factor of the final table?
COMP 251 – Midterm #1 Page 9 of 16 Winter 2021
-3 pts there is no answer or it can not be marked.
-2 pts the reported number is not 6/12; however, the value is right for the size of the table and insert failures reported by the student ]
iv) In what slot (index) is located the number 17?
-3 pts there is no answer or it can not be marked.
-3 pts the reported number is not 17]
-1 pts if the report number is 18 (due to not rehashing all the stored values from index 0 to m − 1
COMP 251 – Midterm #1 Page 10 of 16 Winter 2021
(c) (11 points) Remember that we defined the height of a (sub)tree as the length of the longest path from the root of the (sub)tree to a leaf.
In a union-find data-structure, we want to implement the union-by-height(x, y) function. To do so, we store the following information as metadata in every node:
• hx – The height of the tree rooted at x
• nx – The number of nodes in the tree rooted at x
For this question, please give the big-O notation representing a tight bound for the time that it would take to update the heights of all the nodes that need to be modified after the call of the union-by-height(x, y) function.
You should briefly justify your answer and describe the worst case.
O(1), worst case when hx == hy.
Explanation: when you do union(x, y), you need to find the roots of the trees containing x and y and then you modify the parent p[ ] of one of them. In doing so, at most only one node has its height modified, namely the rep of the new (merged) tree which was the rep of either x’s or y’s tree. So updating the heights is easy and fast .
-11 pts there is no answer or it can not be marked.
-11 pts the reported complexity, the justification and the complexity are wrong.
-7 pts the reported complexity is wrong, the justification, however, is correct and no worst case is given.
-6 pts the reported complexity is wrong; however, it is due to the fact that the student as- sumed certain things (i.e., the update was not AFTER the call of the union-by-height), the assumptions are clear in the justification and worst case.
-5 pts no complexity is reported; however the justification and worst case are right;
-5 pts the reported complexity is right; The justification and worst case are wrong/not given; -3.5 The complexity and worst-case reported are right; however there is no justification; -3.5 The complexity and the justification reported are right, but worst-case is wrong/not re- ported]
COMP 251 – Midterm #1 Page 11 of 16 Winter 2021
Text Questions – Algorithm Paradigms
4. During the reading week, four Comp251 students (each student following a different strategy) made the decision to prepare the exam by studying together. All of the four students (brute-force, DP, Greedy and Divide&Conquer) had the same goal for the midterm. They wanted to get 85 points in the exam (to guarantee an A in the exam). They formalized the problems as follows. Given an array X of positive integers that represent the points of every question in the midterm , and a target integer T that represent the aimed score of the students. Is there a subset of questions in X that add up to exactly T ? Notice that there can be more than one such subset. For example, imagine that the exam is composed by 7 questions with the following points X = [8, 6, 7, 5, 3, 10, 9] and the students aim to obtain a grade of T= 15, the answer is True, because the subsets [8, 7] and [7, 5, 3] and [6, 9] and [5, 10]allsumto15. Ontheotherhand,ifX=[11,6,5,1,7,13,12]andT=15,theanswerisFalse.
(a) (8 points) The brute-force student deducted that the answer for the problem will be True iff only one of the following statements is True:
• There is a subset of X that includes x and whose sum is T . • There is a subset of X that excludes x and whose sum is T .
Based on that analysis, the brute-force student came up with the following algorithm.
public static boolean bruteForce(int[] X, int i, int T){
if (T == 0){
return true;
if(T < 0 || i == 0) {
return false;
boolean with = bruteForce(X,i-1,T-X[i]);
boolean wout = bruteForce(X,i-1,T);
return with || wout;
Please report the recurrence (in mathematical notation) satisfied by the above algorithm. Also, please report the solution of that recurrence.
You are expected to provide the answer following the notation covered in class, for example, the recurrence for merge sort is T(n) ≤ 2T(n/2) + n and its solution is O(n × log(n)), in class we found the solution using the three covered methods (induction/substitution, recursion tree and Master theorem), here you can use the one of you preference.
COMP 251 - Midterm #1 Page 12 of 16 Winter 2021
T (n) <= 2T (n − 1) + O(1)
T(n) = (2n)
Description => just substitute 2T (n − 1) = 2(2T (n − 2)) = 2(2(2(T (n − 3)) = 2n OR In the worst case: for example, when T is larger than the sum of all elements of X, the recursion tree for this algorithm is a complete binary tree with depth n, and the algorithm considers all 2n subsets of X.
-8 pts there is no answer or it can not be marked.
-8 pts the reported recurrence is not right.
-5 pts the reported recurrence is not right, but the student was pretty close (e.g., an error in the constant factor).
-4 pts the recurrence is right, but its solution is wrong.
-5 pts The recurrence is wrong, but the complexity is rigth.]
(b) (22 points) The DP students claims that the problem can be reformulated as follows. Fix the original input array X[1 . . . n] and define the boolean function S(i, t) == true if and only if some subset of X [i . . . n] sums to t. This new function produce the following DP algorithm.
Algorithm 1 DP(X[1. . . n], T) returns a boolean
S[n + 1, 0] ← T rue fort←1toT do
S[n + 1, t] ← F alse end for
for i ← n downto 1 do S[i,0] ← True
for t ← 1 to X[i] − 1 do
S[i, t] ← S[i + 1, t] end for
fort←X[i]toT do
S[i, t] ← S[i + 1, t] OR S[i + 1, t − X[i]]
end for end for
return S[_, _]
i) (4 points) Please report (using Big-O notation) a tight bound for the algorithm. Hint(Notice
that you need to fill the table S)
COMP 251 – Midterm #1 Page 13 of 16 Winter 2021
-4 pts there is no answer or it can not be marked.
-4 pts the reported complexity is wrong
-3 pts the reported complexity is wrong; however, you have the feeling that the students was “close”
-1 pts the reported complexity contains typos]
ii) (4points)Pleasenoticethatthelastlineofthealgorithm(i.e.,returnS[_,_])doesnotreport the indexes of the cell where the solution is located. Please report the indexes by changing the “_” characters with the right values.
return S[1, T ]
-4 pts there is no answer or it can not be marked.
-4 pts the reported return is wrong
-1.5 pts the return seems right, but the student changed the indexes (S[0, T −1] or S[T, 1] orS[0,T]orS[1,T −1]orS[T,0]orS[T −1,1])]
COMP 251 – Midterm #1 Page 14 of 16 Winter 2021
iii) (8 points) Given the positive numbers X = [1, 2, 3] and T = 4. The students run the algorithm and they filled the table S as follows (see below); however, during the copy/paste process the second row got lost. For this question, please report the values of the missing row (if you think, for example, that all the row must contain Trues, please type T T T T T)
-8 pts there is no answer or it can not be marked.
-8 pts the reported row is wrong
-2.5 pts the row seems right, but there are “typos” there, please apply this deduction for each typo in the answer]
iv) (6 points) The brute force student claims that the DP algorithm is fancy; however, in some instances the brute force approach will be faster than the dynamic programming approach. The dynamic programming student says that it is not possible because DP is always faster than a complete search approach. If you think that the DP student is right, please justify why a DP approach is always better than a complete search approach, if by contrary, you think the Brute force student is right, please provide the instances of the problem for which the DP approach will be slower than the complete search approach. (Please make clear in your answer which of the two students is right)
The complete search student is right, if the target sum T is significantly larger than 2n, this DP algorithm is actually slower than the recursive algorithm, because it is wasting time solving subproblems that the recursive algorithm never considers.
-6 pts there is no answer or it can not be marked.
-6 pts the student says that the DP student was right
-4 pt if the student says that brute force was right, but the student did not report the instance of the problem (or the instance is wrong).
-2 pt if the student says that brute force was right, the student reported the instance of the problem, but the answer lacks clarity
If you said the brute force is right and give a reasonable example or explanation, I would give you full marks.
If you just compared the two method but didn’t determine who is right, I would deduct some marks]
COMP 251 – Midterm #1 Page 15 of 16 Winter 2021
(c) (3 bonus points) The greedy student claims that there is a better strategy to solve this problem. With no surprise, the student claims that a greedy choice will make the trick, the student propose the following algorithm.
1. Order the array X by size: x1 ≤ x2 ≤ /dots
2. Introduce s = 0, as the current sum and j = 1 as the current index 3. Ifs+xj ≤T,increments(i.e.,s=s+xj)
4. If s == T, return True
5. Increment j
6. If j < n, then return to step 3, otherwise return F alse.
The algorithm seems to work in the provided examples and the greedy student claims that it will work for all the instances. If you agree with the greedy student, please report an improvement to the algorithm to make it faster (hint: notice that we did not control the case when s > T) by adding a step to the algorithm. If you do not agree with the greedy student, please provide a counter example.
Counter example [11,10,10] and T = 21
-3 pts there is no answer or it can not be marked. -3 pts the student did not report a counter-example. -1 pt the counter-example is not clear.]
COMP 251 – Midterm #1 Page 16 of 16 Winter 2021
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com