Answer to all the questions required :

coursework on algorithms is in the link(pdf file) : https://github.com/prettylittleliarr/xyz/blob/master/algos%20coursework.pdf

1. (4 pts) We want to prove the function f(n) = 3n2 + 4n -20 = 2(n2) by using the definition of 2. Namely we need to find c > 0 and no 2 0 such that: 3n2 + 4n - 20 2 cn for all n > no There are many combinations of c and no that will satisfy the definition. Try the following values for c. 1. Pick c = 2, determine the smallest no that satisfies the definition. 2. Pick c = 3, determine the smallest no that satisfies the definition. 3. Pick c = 4, what happens? 2. (16 pts) Rank the following functions by the order of growth rate (that is, list them in a list fi(n), f2(n), f3(n), . .. such that fi(n) = O(f2(n)), f2(n) = O(f3(n)), . ..). Partition your list into equivalent classes such that f(n) and g(n) are in the same class if and only if f (n) = O(g(n)). You must prove your answer (by limit test or other means). (V3) 1083, n2, In2n2, InInn, (Inn)inn, nininn, 4187, nlg2n, n!, (n - 1)!, (4/3)", n1/2 Note: Ig is the log function with base 2. In is the log function with base e. 1g'n means (Ign)2; In n2 means (Inn2)2. 3. (10 pts) Let f(n) and g(n) be two positive functions. (Namely f(n) > 0 and g(n) > 0 for all n.) State true or false for each of the following statements. If the statement is true, briefly prove it. If the statement is false, provide a counter example. (a) f(n) = O(g(n)) implies f(n) = o(g(n)). (b) f(n) + g(n) = O(max{f (n), g(n)}). (c) f(n) = 0(g(n)) implies 2f(n) = 0(29(n). . ( (us) f) = (u)f (P) f(n) 2 2 for all n.) (e) f(n) = O(g(n)) implies In(f(n)) = O(In(g(n)), (you may assume Ig(g(n)) 2 2 and 4. (2+4=6 pts) The number of distinct n-leaf full binary trees is given by the nth Catalan number: 2n - = (2n-2)! (n-1)! n! (a) For each n = 1, 2, 3, 4, calculate the value of Cn and draw all distinct n-leaf full binary trees. For n = 5, calculate the value of Cs and draw at least 5 distinct 5-leaf full binary trees. (b) Using Stirling's formula, prove On = 0 (4 5. (2+3=5 pts) Give asymptotically tight bounds of the following summations (by using integral method.) (a) ER_1 K1.5 - 2k + 3 (b) Ek=n/2 k Ink6. (9 pts) Give the asymptotic lower and upper bounds for T(n) in each of the following recurrences. Assume that T(n) is a constant for n is defined by: ao = 1, a1 = 3 and, for n 2 2, an = 4an-1 - 3an-2. Find the closed form for an. (b) The sequence is defined by: bo = 1, b1 = 2, b2 = 13 and, for n 2 3, bn = 3bn-2 + 2bn-3. Find the closed form for bn