Q1)
RQS refers to the randomized quick select algorithm referred to as QuickSelect in the
handwritten notes of Subject 7 and RandSelect in Subject 7. Likewise DeSelect of Subject 7 is
also a similarly sounding DeSelect of the handwritten notes. Provide as asymptotically tight an
answer as you can.
1. What is the running time of RQS on m keys?
2. What is the worst-case running time of RQS on m keys?
3. What is the expected running time of RQS on m keys?
4. What is the running time of RQS on m sorted keys?
5. What is the running time of DeSelect on m sorted keys ?
Q2)
We have a graph where G=(V,E) with n vertices and m edges and vertices labeled 0 through
n-1.
The graph is represented with an adjacency matrix A. There is an array F of length n that
collects
information for the vertices: F[ i ] is the information collected for vertex i. The F[.] values are
distinct and in the range 1 through 2n+1.
What would the running time be for a time efficient sorting of (the elements of) array F (based on
the values of it)?
How long does this take if we use a time efficient approach?
Q3)
Professor I. M. Nuts invents the following FasterMy method.DetSelect returns an index of the
input array that contains the relevant statistic. DeSelect is as defined/described in the first
problem.
Assume DeSelect works ok for all problem sizes.
FasterMy(A,n)
FastMy(A,0,n-1);
FastMy(A,l,r);
1. if (ln$ edges and $m=o(n**2)$. Assume we have enough spare
memory i.e. memory is not an issue. Let us run page rank-for t=n iterations? What would the
running time of the synchronous page rank computation be?
Q7)
We have n individuals with ranks that can be integer or real but they are in an arbitrary and
unknown range. A comparison of two ranks take ‘time’ 1 independently of the rank’s value (real
or integer or small or large or ‘complicated’). Provide answers (select correct asymptotic answer
to the following questions). Individual A has higher rank than individual B if A’s rank value is
greater than B’s. Like- wise for lower ranking(s). Let X| 0 .. n-1] be a sequence represented with
an array that hold ranked values. Ig(n) is the logarithm base two of n; Igg(n) is defined as
lg(lg(n)) i.e. the log of the log of n. Likewise for Iggg(n). sqrt(n) is the square root of n function.
(a) Use an optimal comparison algorithm to find the rank of the 25-th lowest ranked individual
(b) Use an optimal comparison algorithm to find the rank of the Iggn-th highest ranked individual
(c) Use an optimal comparison algorithm to find the rank of the (n-sqrt(n))-th lowest ranked
individual
(d) Use an optimal comparison algorithm to find the ranke of the n/4-th lowest ranked individual
(the n/4-th lowest ranked individual and the individuals with rank lower than it form the bottom
quartile, aka quarter of individuals.)
Q)
True or False
1. The best case of InsertionSort is Theta(n).
2. Elementary school multiplication of two n-bit integers takes time O(n*n)
2a. We multiply two n-bit integers a and b. Let c=a*b. The number of bit of c is about n**2.
2b. We multiply a 2n-bit integer a and a 3n-bit integer b. Let c=a* b. The number of bit of c is
about 5n.
3. You have an input of n-1 9s followed by a lone 8. That is Run InsertionSort. The
number of comparisons performed is 2n-3.
4. The running time of MergeSort on input (a sorted sequence) is O(nlgn).
5. Function 2** (n/2) is asymptotically equal to 2**(n/3).
6. The order of growth of 2**(lgn) is Theta(n).
7. The order of growth of 2** (2*lgn) is Theta(n)
8. 2**n is asymptotically smaller than n!.
9. T(n)=2T(n/2)+nlgn has solution T(n)=Theta(nlgn).
10. T(n)= T(n/3)+T(2n/3)+nlgn has solution T(n) = O(n*Ign* Ign).
11. We can find the MAX and MIN of n keys, n a power of 2, in at most n+n/2 comparisons.
12. We can find the MAX and secondMAX (second largest) of n keys is at most n+lgn
comparisons.
13. The running time of BuildMaxHeap is Theta(nlgn) for building a MaxHeap with nlgn keys.
14. In a MinHeap H[.], already containing n keys, we use function HeapDecrease(A,i,k) that first
decreases the value A [i] from the current value by resetting it to A[i]=k that is smaller, and then
making sure the Heap is still a MinHeap. The running of such a HeapDecrease is O(lgn).
15. We are given k
Purchase answer to see full
attachment