## Midterm 1 Practice

1. Show that
(a) $x^2 + 1000x = O( x^3 )$
(b) $x^2 + 1000x = \Omega(x)$

2. Describe an algorithm which computes $x^{96}$ 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: $f (cn) = \theta(f (n))$

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 :

$a_n = 3a_{n-1} - 2a_{n-2}$

with $a_1 = 4$, $a_2 = 6$.
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 $(x + 1/x )^n$ , where (n > 2)? What are the coefficients of the terms $1/x$ , $1/x^2$.Explain.
10. Using sterling’s formula, give an approximation for $O\left ( \binom{n}{n/2} \right )$.
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?

### 13 Responses

1. are you going to give us the solution for the practice exam?

• It’s rather better to give hints. You should try to solve the problems, try to make some guesses. Even you make wrong guesses, you can “feel” the problem better and do the midterm better. Midterm’s problems are not the same as midterm practice’s.

2. I haven’t received any questions here and assume that all problems are easy :D. Following is some hints if you think it’s useful.
2. If you now $x^a$ and $x^b$ you can compute $x^{a+b}$ with just one application. Especially, if a = b, we can compute $x^{2a}$ with one multiplication knowing only $x^a$. Now we have to break down the problem: $96 = 64 + 32$. It takes 6 multiplications to compute $x^2, x^4, ..., x^{64}$. The last multiplication is used to compute final output.

3. 3. Consider that couple as one person. But you should notice that, they, the couple, can exchange the positions. The result is 2.9!

4. 4. It’s not true. Find a function such that the constant c affects the order of f(cn).

5. 5. $GCD (a_1, a_2, ... , a_n) = GCD (GCD(a_1, a_2, ..., a_{n-1}), a_n)$

6. 8
a, Arrange the boys first then girls choose their positions which are between boys or two ends. The result is n!n!/(n-m)!
b, This one is different because the order must be G B G B … or B G B G … each one has 10!10! arrangements. Total is 2.10!10!

7. $(x + \frac{1}{x})^n = \sum_{k=1}^n \binom{n}{k}x^k (\frac{1}{x})^{n-k}$. The coefficient of 1/x is $\binom{n}{k}$ where k+1 = n – k. The coefficient of $1/x^2$ is $\binom{n}{k}$ where k+2 = n – k.

8. 10.
$\frac{\sqrt{2\pi n}(n/e)^n}{\pi n (n/2e)^n} = \frac{\sqrt{2}2^n}{\sqrt{\pi n}}$

9. 12.
Suppose the power set of N is countable, then subsets of N can be list as x1, x2, …. Consider the set X such that i is in X iff i is not in xi. Denote the index of X in the sequence of subsets is k. If k is in xk then k is not in X or xk. If k is in xk, then k is in X or xk. It’s a contradiction.

10. 13
a, We build a decision tree, each comparison creates two children. Because the out put is any of n number, thus the height of the tree is at least O(log n)
b, The number at position (0,0) is the smallest and (n, n) is the largest. Start with (0, 0) we move right along the row while the value is less than searched value, then move down along the column while the value is less than searched value. Then move right along the row, down along the column. It’s sure that the process will meet the searched value.

The algorithm requires at most n+n moves. Time complexity is O(n).

11. 14.
$p, 2p, 3p ...$ each number contribute 1 to the power of p in n!.
$p^2, 2p^2, ...$ each contribute 2 to the power of p in n!.
….
Thus the highest power of p in n! is $\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + ... + \lfloor n/p^k \rfloor$

12. 15
b, Consider $f(x) = \sum_{i=0}^n a_ix^i$
$f(1) = \sum_{i=0}^n a_i$
$f( f(1)) = \sum_{i=0}^n a_i(f(1)^i$
Because $a_i < f(1) \forall 0\leq i \leq n$, we can express f(f(1)) as a number with base f(1) and $a_i$ is the $i^{th}$ digit. Thus we only need to know f(1) and f(f(1)) to determine f(x)