Reference no: EM13920349

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!, 2ⁿ, n^lgn, n Ig n, n√n

2. Prove the followings:               

a) _k=2Σ^n-1 k lg k ≤ ½ n²lgn - n²/4

b) _k=0Σⁿ(ⁿ_k)² = (²ⁿ_n)

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) + n²√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.