12/13/2020 Midterm Test: Attempt review
Dashboard / My courses / LE/EECS3101 E – Design and Analysis of Algorithms (Fall 2020-2021) / Midterm Test / Midterm Test
Started on State Completed on Time taken Grade
Monday, 26 October 2020, 4:00 PM Finished
Monday, 26 October 2020, 6:29 PM 2 hours 29 mins
19 out of 100
Question 1 Correct
Mark 5 out of 5
in the plane, where the three coefficients This problem can be solved efficiently in the worst case in ( ? ) time.
a.
b.
c.
d. That’s impossible, since there are infinitely many candidates to check
Your answer is correct.
Use extended Euclid’s GCD algorithm as explained in LS4.
The correct answer is (the number of bits, not the magnitude). So, none of the given choices are correct.
Everyone was granted 5/5 on this question.
The correct answer is:
Comment:
are integers expressed with at most
We are given the equation of a line
bits. We want to determine whether line passes through any point with integer coordinates.
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 1/16
,c,b,a
Ln L 0=c+yb+xa
Θ
n
n gol
)3( n
n2
n gol
12/13/2020 Midterm Test: Attempt review
The solution to the recurrence is
a. b. c. d.
Your answer is correct.
LS3, page 67: Akra-Bazzi with p = 2. The correct answer is:
( ? ).
Question 3 Correct
Mark 6 out of 6
Consider the following pair of recurrences:
for , and for,and .
Most efficient time complexity to compute for any given n is ( ? ) . a.
b.
c. These two recurrences depend on each other and the problem does not have a solution d.
Your answer is correct.
See how we solved a Generalization of the Fibonacci Sequence in one of the live sessions. Set up a vector-matrix equation, then use the repeated doubling technique.
The correct answer is:
Question 2 Correct
Mark 4 out of 4
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 2/16
Θ = )n( T
n gol 2n + )4/n( T4 + )2/n( T3 = )n( T
Θ nA
2 = 1B = 0B 1= 1A= 0A
2 ≥ n 2≥n
2−nA4 + 1−nB5 = nB 2−nB3+1−nA2= nA
n gol n2
n 2gol 2n
44gol +32goln ngolgolngol 2n
n gol 2n
n
n gol
n 2gol 2n
12/13/2020 Midterm Test: Attempt review
An array of distinct integers is said to be undulating if its sequence of elements alternates between increasing and decreasing, that is,
foreveryoddindex ,and foreveryevenindex . For example, the following 16-element array is undulating:
The problem is to permute the elements of any given non-empty array of What is the time complexity of this problem?
a.
b.
c. \( \Theta (n^2 )\)
d. \( \Theta (n \log \log n ) \)
Your answer is incorrect.
distinct integers so that the permuted array is undulating.
Incrementally scan through the elements and maintain as LI that the scanned portion is undulating. To maintain LI, you may need to swap the current scanned element with its predecessor.
The correct answer is: \( \Theta (n) \)
We are given two arrays \(A[1..n]\) and \(B[1..n]\) of arbitrary real numbers. Their Cartesian Sum \( A\oplus B \) is the collection of the \( n^2 \) elements of the form \( A[i] + B[j] \) for \( i = 1..n\) and \( j = 1..n\). The problem is to compute the median of \( A \oplus B \) . This problem can be solved most efficiently, in the comparison based model, in the worst-case in
Question 5 Incorrect
Mark 0 out of 6
a. \( \Theta (n) \) time, since median of \(A \oplus B\) is median of A plus median of B.
b. \( \Theta (n \log n) \) time, by a suitable algorithm in the decision tree model.
c. \( \Omega( n^2 \log n )\) time, based on the Information Theory Lower Bound.
d. \( \Omega (n^2)\) time, since we need to at least inspect all \(n^2\) elements of \(A\oplus B\).
Your answer is incorrect.
First sort A and B. Now \(A \oplus B\) may be viewed as an n-by-n matrix with sorted rows and columns. Now apply exercise 6(c) of LS5 that was solved during the live sessions.
The correct answer is:
\( \Theta (n \log n) \) time, by a suitable algorithm in the decision tree model.
Question 4 Incorrect
Mark 0 out of 5
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 3/16
i
]1+i[A > ]i[A i ]1+i[A < ]i[A ]n . .1[A
n
)n gol n(Θ )n(Θ
12/13/2020 Midterm Test: Attempt review
We are given a collection S of n points in the 3 dimensional space, each point with integer x,y,z coordinates between 1 and n. We want to sort the points in S in ascending order of distance from the origin. This can be accomplished most efficiently in the integer RAM model, in the worst-case time \(\Theta\)( ? ).
a. \( n^2 \)
b. \( n \log n \) c. \( n \) d.\(n^3 \)
Your answer is incorrect.
Apply 3-round RadixSort in base n.
The correct answer is: \( n \)
Suppose \(f(n)\) = \(O(n^6 \log \log n)\) and \(g(n)\) = \(\Omega(n^2 \log^2 n)\). Then
a. \(f(n) + g(n)\) = \(O(n^6~\log \log n)\)
b. \(\frac{f(n)}{g(n)}\) = \(\Omega \left( \frac{n^4 \log \log n}{\log^2 n} \right) \) c. \(\frac{f(n)}{g(n)}\) = \(O \left( \frac{n^4 \log \log n}{\log n} \right) \)
d. \(f(n) \ast g(n)\) = \(\Theta(n^8 ~\log^2 n ~\log \log n ) \)
Your answer is incorrect. Notethat\(1/\log^2n =O(1/\logn)\).
The correct answer is:
\(\frac{f(n)}{g(n)}\) = \(O \left( \frac{n^4 \log \log n}{\log n} \right) \)
Question 7 Incorrect
Mark 0 out of 4
Question 6 Incorrect
Mark 0 out of 4
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 4/16
12/13/2020 Midterm Test: Attempt review
Suppose \(f(n) = 2^{\sqrt{2n}}\). The solution to the recurrence \( T(n)=2T\left(~n - \log(f(n) )~\right) + f(n)\) is \(T(n)=\Theta\)( ? ).
a. \(f(n) \log n\)
b. \( f(n) \log ( f(n) ) \)
c. None of the other choices
d. \(f(n)\)
Your answer is incorrect.
Look up our recursive solution to the 4-stack version of the Towers of Hanoi Problem. The correct answer is: \( f(n) \log ( f(n) ) \)
Question 9 Incorrect
Mark 0 out of 5
Suppose you're consulting for a bank that's concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank cards that they've confiscated, suspecting them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank cards corresponding to it, and we'll say that two cards are equivalent if they correspond to the same account.
It's very difficult to read the account number off a bank card directly, but the bank has a high-tech "equivalence tester" that takes two bank cards and, after performing some computations, determines whether they are equivalent.
Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another? Assume that the only feasible operations you can do with the cards are to pick up two of them and plug them in to the equivalence tester. Their question can be answered most efficiently in the worst-case with \(\Theta\)( ? ) invocations of the equivalence tester.
a. \(n\log n\)
b. None of the other choices
c. \(n \log \log n\)
d. \(\sum_{i=1}^{\lfloor n/2 \rfloor} ~(n-i)\) e. \(n\)
Your answer is incorrect.
See VLSI Cheap Testing (LS4, p. 32), and Majority Problem (LS5, Exercise 24, p. 140).
The correct answer is: \(n\)
Question 8 Incorrect
Mark 0 out of 6
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 5/16
12/13/2020 Midterm Test: Attempt review
\( \sum_{i=1}^{ \lceil \log n \rceil} \sum_{j=1}^{2^i} \frac{ 7(i+3)^2 ~(j+6)^4 } { (4^i~+~4i^2)~(2j \log j ~+~ 5j) } \) = \( \Theta \) ( ? ).
a. \( n^4 \log n \)
b. \( n^3 / \log n \)
c. \( n^2 \log n \)
d. None of the other choices
Your answer is incorrect.
Arithmetic inner-sum, geometric outer-sum.
The correct answer is: \( n^2 \log n \)
Question 11 Incorrect
Mark 0 out of 7
The input is a collection S of n elements, where each element has a primary key and a secondary key, all distinct. We want to construct a (pointer based) binary tree T with n nodes and place the elements of S, each in a distinct node of T, such that T is a Binary Search Tree with respect to the primary keys, and is a Heap Ordered Tree with respect to the secondary keys. Tree T can be constructed most efficiently in the worst-case in \(\Theta\)( ? ) time.
a. \(n \log n~\log\log n\) b. \(n^2\)
c. Such a tree T with all the given requirements may not exist d. \(n\log n\)
e. \(n\)
Your answer is incorrect.
First sort the collection on their primary key. Then insert them incrementally at the end of the right shoulder of T, followed by repeated left- rotations on their parent link as many as necessary to restore heap order on the secondary key. MP (measure of progress) is twice the number of elements yet to be inserted into T plus the length of the right shoulder of T.
The correct answer is: \(n\log n\)
Question 10 Incorrect
Mark 0 out of 5
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 6/16
12/13/2020 Midterm Test: Attempt review
Fill in the underlined blank for the following algorithm.
algorithm product \(( x , y)\)
// Pre-Condition: \(x\) and \(y\) are natural numbers // Post-Condition: returns the product of the input pair
begin
\(r \leftarrow 0\) while ( \(y > 0\) ) do
// Loop Invariant: _____________________________ // fill in this line if ( \( (y\mod 2) = 1\) ) then \( r \leftarrow r+x\)
\(x \leftarrow x+x\)
\(y \leftarrow \lfloor y/2 \rfloor \)
end-while
return \(r\) ; end
a. product of the input pair equals the current value of \( r ~+~ x*y \)
b. all of the other choices
c. \( r \) will eventually become the product of the input pair
d. the loop repeatedly adds \(x*(y \mod 2)\) to \(r\), doubles \( x \), and halves \(y\)
Your answer is incorrect.
Loop Invariant is a logical assertion on the current state of the algorithm data. It is not code-description or other such commentary.
The correct answer is:
product of the input pair equals the current value of \( r ~+~ x*y \)
Question 12 Incorrect
Mark 0 out of 5
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 7/16
12/13/2020 Midterm Test: Attempt review
Let \(T\) be an arbitrary binary tree with \(n\) internal nodes and \(n+1\) external nodes. Suppose the weight of a node \(x\) is defined as \ (w(x) = 2^{- depth(x)}\). The internal weight of \(T\), \(InW(T)\), is defined as the sum of the weights of internal nodes of \(T\). Similarly, the external weight of \(T\), \(ExtW(T)\), is defined as the sum of the weights of external nodes of \(T\). Based on these definitions we have
a. None of the other choices
b. \(InW(T) > ExtW(T) \ast \log n\)
c. \( InW(T) \ast ExtW(T) \leq \log (n+1)\)
d. \(InW(T) + ExtW(T) = \sum_{i=1}^{n} 2^{-i} +\sum_{i=1}^{n+1} 2^{-i} \)
Your answer is incorrect.
\(ExtW(T)=1\) and \(2(1-2^{-n}) \leq InW(T) \leq \log (n+1) \). The latter bounds are based on how (im)balanced \(T\) is.
The correct answer is:
\( InW(T) \ast ExtW(T) \leq \log (n+1)\)
\( \left( ~ \log ( (n^3)! ) + n \sqrt{n} \log ( (n!)^2 ) ~ \right) \left( \sum_{i=1}^{n^2} \frac{i}{\log i} \right) \) = Θ( ? ) .
a. \( n^{7.5} \log n \log \log n \) b. None of the other choices
c. \( n^7 \)
d. \( n^3 \log^2 n \)
Question 14 Incorrect
Mark 0 out of 4
Your answer is incorrect.
\(\log(x!)=\Theta (x\log x)\), \(\log (x^2)=2\log x\), Last sum is arithmetic: number of terms is \(n^2\), max term is \(n^2 / \log(n^2)\).
The correct answer is: \( n^7 \)
Question 13 Incorrect
Mark 0 out of 5
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 8/16
12/13/2020 Midterm Test: Attempt review
The solution to the recurrence \( T(n)=8 T(\sqrt{n})+ ( \log^3 n) ( \log\log n) \) is \(T(n) = \Theta \) ( ? ).
a. \(\log^3 (n \log n) \)
b. \( (\log^3 n )~\log^2 (\log n )\) c. \( n \log n \)
d. \( \log^3 (n^3 \log n) \)
Your answer is correct.
Use substitution \(m = \log n\)
The correct answer is:
\( (\log^3 n )~\log^2 (\log n )\)
Question 16 Incorrect
Mark 0 out of 4
We have two divide-&-conquer algorithms, let’s call them A and B, where A calls B. Their time complexities, \(T_A(n)\) and \(T_B(n)\), are expressed by the following recurrence relations
Then
\( T_A(n) ~=~ 8 T_A(n/2) ~~+~~T_B(n)~+~\Theta(n^2 \sqrt{n} ) \) \( T_B(n) ~=~ 12 T_B(n/3) ~~+~~ \Theta(n^3\log^3 n) \)
a. \( T_A(n) ~=~\Theta(n^2 \sqrt{n} ) \) b. \( T_A(n) ~=~\Theta(n^3\log^3 n) \) c. \( T_A(n) ~=~\Theta(n^3\log^4 n) \) d. \( T_A(n) ~=~\Theta(n^4\log n) \)
Your answer is incorrect.
Use the Master Theorem. First solve for \(T_B(n)\), then plug that into the first recurrence to solve for \(T_A(n)\).
The correct answer is:
\( T_A(n) ~=~\Theta(n^3\log^4 n) \)
Question 15 Correct
Mark 4 out of 4
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 9/16
12/13/2020 Midterm Test: Attempt review
Suppose \(A[1..n]\) is an array of n elements, where each element is a positive integer at most \(c\), for some unspecified constant \(c\).
If we denote the worst-case time complexity to sort \(A[1..n]\) by T_{QS}(n)\), then
a. \(T_{MS}(n) = \Theta (n) ~~ ,~~ T_{QS}(n) = \Theta (n\log n)\)
b. \(T_{MS}(n) = \Theta (n\log n) ~~ ,~~ T_{QS}(n) = \Theta (n^2)\) c. \(T_{MS}(n) = \Theta (n) ~~ ,~~ T_{QS}(n) = \Theta (n^2)\)
d. \(T_{MS}(n) = \Theta (n\log n) ~~ ,~~ T_{QS}(n) = \Theta(n)\)
Your answer is incorrect.
In this problem QuickSort has at most constant recursion depth.
The correct answer is:
\(T_{MS}(n) = \Theta (n\log n) ~~ ,~~ T_{QS}(n) = \Theta(n)\)
MergeSort as \( T_{MS}(n) \), and by randomized QuickSort as \(
Question 18 Incorrect
Mark 0 out of 4
We are given a Binary Search Tree (BST) \(T_1\) holding \(n\) distinct comparable elements. The problem is to construct an equivalent BST \ (T_2\) that holds the same collection of elements as \(T_1\), but has height at most \(\log n\). This problem can be solved efficiently in the worst-case in \(\Theta\)( ? ) time.
a. \(n\)
b. \(n\log n\) c. \(1\)
d. \(\log n\)
Your answer is incorrect.
Inorder traverse and list elements in a sorted array. Then recursively split array in halves to form balanced BST.
The correct answer is: \(n\)
Question 17 Incorrect
Mark 0 out of 6
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 10/16
12/13/2020 Midterm Test: Attempt review
We are given a binary tree T with n nodes, where each node \(x\) stores a real number \(w[x]\) called its weight. Node weights may be negative, zero, or positive. For any pair of nodes \(x\) and \(y\) in T, let \(path(x,y)\) denote the unique simple path between them (i.e., up from \(x\), along its ancestral path, to the nearest common ancestor of \(x\) and \(y\), then down to \(y\), along ancestral path of \(y\)). The weight of this path, denoted \(W(x,y)\), is the sum of the weights of the nodes on the path. We want to compute the maximum path weight in T, i.e., \(\max\{~W(x,y)~|~x \in T,~y \in T~\}\).
We intend to solve this problem in \(O(n)\) time by a post-order traversal of T with appropriately strengthened post-condition. Suppose our recursive post-order algorithm is OptimumPathWeight(r) that is initially invoked at node \(r=root[T]\). The Post-Condition for this recursive call says among the returned values we have
a.
b.
c.
d.
1.
1. 2.
1.
2. 3.
1.
2. 3. 4.
MaxPairWeight=maximumpathweightbetweenanypairofdescendantsof\(r\).
MaxPairWeight=maximumpathweightbetweenanypairofdescendantsof\(r\). Max2RootWeight = maximum path weight between \(r\) and any one of its descendants.
MaxLRWeight=maximumpathweightbetweenanynodeinleftsubtreeof\(r\)or\(r\)itself,andanynodeinrightsubtreeof\ (r\) or \(r\) itself.
MaxLWeight = maximum path weight between any two nodes in left subtree of \(r\).
MaxRWeight = maximum path weight between any two nodes in right subtree of \(r\).
MaxLRWeight = maximum path weight between any node in left subtree of \(r\) or \(r\) itself, and any node in right subtree of \(r\) or \(r\) itself.
MaxLWeight = maximum path weight between any two nodes in left subtree of \(r\).
MaxRWeight = maximum path weight between any two nodes in right subtree of \(r\).
\(\max\{\) 0, MaxLRWeight, MaxLWeight, MaxRWeight \(\}\)
Your answer is incorrect. The correct answer is:
1. MaxPairWeight = maximum path weight between any pair of descendants of \(r\).
2. Max2RootWeight = maximum path weight between \(r\) and any one of its descendants.
Question 19 Incorrect
Mark 0 out of 6
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 11/16
12/13/2020 Midterm Test: Attempt review
Problem:
Input: a natural number n, and the values of \(\sin(x)\) and \(\cos(x)\) for some unspecified angle \(x\) (i.e., the angle is not part of the input).
Output: \(\sin(nx)\).
Restriction: Only real RAM elementary operations are allowed. That excludes any trigonometric function calls. This problem can be solved efficiently in the worst-case in \(\Theta\)( ? ) time.
a. \(\log n\)
b. \(n\)
c. \(2^n\)
d. This is impossible e. \(n\log n\)
Your answer is incorrect.
Euler’s formula: \(e^{inx}=\cos(nx)+i\sin(nx)=(\cos(x)+i\sin(x))^n\). Now use repeated doubling. Separately maintain the real and imaginary parts of the current complex number.
The correct answer is: \(\log n\)
◄ Midterm Academic Pledge
Jump to…
Instructions ►
Question 20 Incorrect
Mark 0 out of 5
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 12/16
12/13/2020 Midterm Test: Attempt review
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 13/16
12/13/2020 Midterm Test: Attempt review
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 14/16
12/13/2020 Midterm Test: Attempt review
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 15/16
12/13/2020 Midterm Test: Attempt review
https://eclass.yorku.ca/eclass/mod/quiz/review.php?attempt=442205&cmid=54898 16/16