Question 1) Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures;
i) f(n) = θ(f(n/2))
ii) f(n) = O((f(n))2)
iii) f(n) = O(g(n)) implies g(n) = Ω(f(n))
b) Prove that Pr{A | B} + Pr{ A‾ | B} = 1.
Question 2)a) Give examples of relations that are:
i) Reflexive and symmetric but not transitive
ii) Reflexive and transitive but not symmetric
iii) Symmetric and transitive but not reflexive
b) Demonstrate the operation of counting sort on the array A = [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2].
Question 3)a) Let A and B be finite sets, and f : A −> B be a function. Demonstrate that:
i) If f is injective, then |A| ≤ |B|
ii) If f is surjective, then |A| ≥ |B|
b) Demonstrate that any connected, undirected graph G = (V, E) satisfies |E| ≥ |V| - 1.
Question 4)a) Demonstrate the operation of Heap sort on array A = [5, 13, 2, 25, 7, 17, 20, 8, 4].
b) What is the running time of heap sort on an array A of length n that is already sorted in increasing order? What about decreasing order?
Question 5) Write notes on the following topics:
• Graph and trees
• Radix and Bucket Sort
• Counting and Probability
• Lower bounds for sorting