1. Show that

(a)

(b)

2. Describe an algorithm which computes using at most seven multiplications.

3. A group of 10 students are queuing to enter a cinema. How many ways to form the queue knowing that there is a couple who want to stand near together?

4. Prove or disprove:

5. Let GCD be the algorithm to compute the greatest common divisors of two numbers. Describe a recursive algorithm to find greatest common divisors of n positive integers using GCD.

6. Let f and g be functions from real numbers to real numbers.

f(x) = 2x

g(x) = x + 2

Is the composition of f and g invertible? If it is invertible, find the inverse function.

7. What is the solution of the recurrence relation :

with

,

.

8. Marry invites m girls and n boys to her party. She wants them to play a game that requires them to sit in a row. In addition, she tries to arrange such that there is at least one boy between any two girls. How many arrangements satisfy her expectation for:

(a) m < n.

(b) m = n. Furthermore, if she expects them to sit interleave, how many arrangement are there?

9. In the expansion of

, where (n > 2)? What are the coefficients of the terms

,

.Explain.

10. Using sterling’s formula, give an approximation for

.

11. (a) Prove that any boolean function can be converted to a DNF (ORs of ANDs of the input variables or their negation). for example: f = A AND (B OR ~C) = (A AND B) OR (A AND ~C).

(b) Prove that any boolean function can be converted to a CNF (ANDs of ORs of the input variables or their negation).

12. Prove power set of N is uncountable.

13.

(a) Prove that the lower bound on the time complexity for searching a sorted list of real integers is O(log n).

(c) Describe an algorithm for searching in an n by n matrix with each row and each column sorted from left to right and up to down in increasing order. What is the running time of your algorithm?

14. What is the highest power of a prime p that divides n! ?

15.

(a) Prove by induction that you need to evaluate (n+1) points to determine polynomial of order n.

(b) If the coefficients of f(x) are restricted to be positive integers, then prove that you can determine f(x) by evaluating only two points. (hint: first point is f(1))

16. What is the number of different ways a convex polygon can be cut into triangles?

Filed under: Uncategorized | 13 Comments »