1. Sort the following functions by increasing order of complexity; if applicable, you need to prove stronger results that involve "small-o" or "small-ω" notations. Also, show your work with detailed explanation, just writing the order will not provide you any credit.
n!, 2n, nlgn, n Ig n, n√n
2. Prove the followings:
a) k=2Σn-1 k lg k ≤ ½ n2lgn - n2/4
b) k=0Σn(nk)2 = (2nn)
3. Prove that in the array Pin procedure PERMUTE-BY-SORTING, the probability that all elements are unique is at least 1 - 1/n. (hint: we are not looking for the exact probability, rather we are looking for a lower bound, so you can simplify your probability expression by choosing a suitable lower bound, the inequality (1 - x)n ≥ 1- nx can be useful)
4. Consider the following randomized algorithm for searching for a value x in an unsorted array A consisting of n elements; pick a random index i into A; if A[i] = x, then we terminate; otherwise, we continue the search by picking a new random index into A. This process continues until we find an index j such that A[j] = x or until we have checked every element of A. Note that, we pick from the whole set of indices each time, so that we may examine a given element more than one. Now, answer the following questions:
a) Write pseudocode for a procedure RANDOM-SEARCH to implement the strategy above.
b) Suppose that there is exactly one index i such that A[i] = x. What is the expected number of indices into A that we must pick before we find x and RANDOM-SEARCH terminates?
c) Generalize your solution for the above part, for the cases when there are k ≥ 1 indices i such that A[i] = x.
d) Now, find the expected number of indices into A that we pick for the case when there are no indices such that A[i]= x.
5. For the following recurrences, find a good asymptotic upper bound using recursion tree method
a) T(n) = 4T(n/2) + n
b) T(n) = 2T(n/2) + n lg n
6. For the following recurrences, find a good asymptotic upper bound using Master method (if applies) and substitution method
a) T(n) = 4T(n/2) + n2√n
b) T(n) = 4T(n/3) + n lg n
c) T(n) = 2T(n/2) + n lg n
d) T(n) = 2T(n/4) +√n
7: Proof the correctness of BubbleSort. For an array of size ri, what is the expected number of exchanges the BubbleSort algorithm performs considering a uniform random permutation.