problem 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.

problem 2)a) Give exs 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].

problem 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.

problem 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?

problem 5) prepare notes on the following topics:

• Graph and trees

• Radix and Bucket Sort

• Counting and Probability

• Lower bounds for sorting