## Homework 4

Homework 4 is due on Thursday, July 1st.

0. Read Chapter 9. Indicating in at most three sentences one or more of the following: the passage in the reading— including its page number—you:

• Found most difficult
• Found most surprising
• Would like to have discussed in the next lecture

1. Show that Dijkstra’s algorithm may not work if edges can have negative weights

2. Show that for any undirected graph with |V|  >= 2 nodes there exist two vertices with the same degree.

3. Let G be a graph and v a vertex in G with degree  at most half the average degree of the Graph. Show that deleting the vertex v (and all incident edges) does not decrease the average degree of the Graph.

4. Let $G = (V;E)$ be a graph that has at least 5 vertices. The complement of $G$ is a graph $\bar{G} = (V, \bar{E})$  on the same vertices such that two vertices of $\bar{G}$ are adjacent if and only if they are not adjacent in $G$. Show that $G$ or $\bar{G}$ contains a cycle

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

## Homework 3

Homework 3 is due on Wednesday, June 9th.

0. Read Chapter 2, 3. Indicating in at most three sentences one or more of the following: the passage in the reading— including its page number—you:

• Found most difficult
• Found most surprising
• Would like to have discussed in the next lecture

1. Let f and g be the injective functions from the set of real numbers to the set of real numbers. Prove or disprove the composition of f and g is also a injective functions?

2. Prove that if A is subset of B, then the super set of A is subset of the super set of B.

3. Is there an integer k such that: $n^2 + \log n\sum_{i=1}^{i=n}i = \theta(n^k)$

4. Compare $\theta(n!)$ and $\theta \left ( n^{n/2} \binom{n}{n/2}\right )$

5. Rewrite the proof (given in pages 176-177 of the book) showing that the Halting Problem is unsolvable using the diagonalization proof of $card(\mathbb{N}) \neq card (\mathbb{R})$ that we discussed in class.

6. Briefly sketch and give complexity bounds for at least 5 different sorting algorithms you find online.

7. Follow exercise 5.17 to proof Fermant’s little theorem.

8. Project idea: cryptography (start by reading 240-244).