1. Prove that log10n is O(n) but log10n is not (n).

2.Prove that for any natural number n 1 then 1 + 21 + 22 + ... + 2n = 2(n+1) 1

3. Find the greatest common divisor(gcd) by Euclids Algorithm of a and b with a b is given by int gcd (int a, int b) { int r = 0; while (b > 0) { r = a % b; a = b; b = r; } return r ; } Show that the number of operations of the while loop is no more than log(a) plus some very small constant.

4. Prove that the solution of recurrence of T(n) = 2T(n/2)+ O(n) is (n log2 n). Assume here that n=2t and T(1) = 1.

5. Give a pseudo code description of the O(log n) time algorithm for computing the power xn. Also draw the recursion trace of this algorithm for the computation of 29.

6. Prove by Math. Induction that a perfect binary tree has 2h+1-1 nodes, where h is the height of the tree.

7. Draw the binary search tree by insert the following keys 44, 19, 69, 6, 24, 61, 82, 0, 7, 59, 62. Then print the items using the level order, Pre-order, In-order, Post-order traversal.