## Homework 6

Homework 6 is due on Wednesday, August 4th.

0. Read Chapter 12. 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. Construct deterministic finite-state automata  that recognizes each of these languages.
a. The set of bit strings that have at most two 0s
b. The set of bit strings that have exactly two 0s.
2. Prove Pumping Lemma (problem 22, page 827).
3. Construct finite-state automata that recognizes the regular sets:
a. 10*1*
b. 0*(10 $\cup$11)*
4. Construct a Turing machine that computes the function f(n) = 2n for all nonnegative integers n.
5. There are ten red and ten blue balls in a box. Randomly get out 5 balls. What is the probability to get 5 red balls?
6. What is the probability  of these events when we randomly select a permutation of {1, 2, .., n} where $n \geq 4$.
a. 1 precedes 2.
b. 1 immediately precedes 2.
c. n precedes 1 and n-1 precedes 2

Homework 5 is due on Wednesday,  July 14th.

0. Read Chapter 10. 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. Design an algorithm that reconstruct a tree from its preorder and inorder traversals.

2. Let T be a tree with n vertices. How many connected component are there when:

a,  p edges are removed (p<n-1).

b,  p vertices are removed (p<n).

If the number of connected components can not be counted, explain why.

3. Count the number of leaves of a complete binary tree of height h.

4. Discuss the A* algorithm and compare that to Depth first search and Breadth first search.

5. The Eucledian Minimum Spanning tree is is a minimum spanning tree of a set of n points in ℝd, where the weight of the edge between each pair of points is the distance between those two points. Give an algorithm for computing the Euclidean Minimum Spanning tree.

## 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).

## Homework 2

Homework 2 is due on Monday, May 31st.

1. Read Chapter 4. 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 lectur

2. To successfully complete a B.S. degree in CISE, students must satisfy the following requirements:

• Complete at least 5 of 10 core courses.
• Complete at least 72 credit hours.

Know that each course worths 3 credit hours and there are 20 optional coures. A student plans to complete the degree with minimum number of credit hours. How many choice does he have, no matter the order of selected courses.

3. Seven darts are thrown onto a circular dartboard of radius 10 units. Can we show that there will always be two darts  which are at most 10 units apart?

4. Lattice paths are paths in the plane from (0, 0) to (x, y) (x, y are integers) where at each step you must move either one unit up or one unit right. Count the number of lattice paths from (0, 0) to (x, y).

5. How many 9-digit numbers are there if each has exactly one 5 digit and a 4 digit?

## Homework 1

Homework 1 is due on Monday, May 24th.

1. Read Chapter 1 and 4.1, 4.2. 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

2. Prove or disprove:

$(A \vee B)\wedge(A \vee C \vee \neg B) \equiv (B \wedge C) \vee (A \wedge \neg B) \vee (A \wedge \neg C)$

3. Working at the local pizza parlor, I have a stack of unbaked pizza doughs. For a most pleasing presentation, I wish to arrange them in order of size, with the largest pizza on the bottom. I’m able to place my spatula under one of the pizzas and flip over the whole stack above the spatula (reversing their order). This is the only move I can do to change the order of the stack; however, I am willing to keep repeating this move until I get the stack in order. Is it always possible for me to get the pizzas in order? Prove your answer.

4. Explain what’s wrong with this reasoning: The students set off home for the weekend. Their teacher said: “You shall have an examination at nine in the morning one day next week; but you will not know in advance which day-it will be a surprise.” “Suppose,” thought one to herself with the desperation available only to the damned and the examinable: “Suppose we were still unexamined until Friday. I know there will be an examination some time this week, and so I would be able to expect the Friday examination. Therefore the teacher cannot possibly leave it until Friday.”  “Suppose further,” she thought to herself: “Suppose that I am still unexamined on Thursday. I know the examination cannot be on Friday, so it would have to come on Thursday. But then too I would have been able to predict its day. So, the teacher cannot leave it until Thursday either. Or Wednesday… or Tuesday… or Monday.. In fact, he cannot possibly set any examination at all, since no day would be a surprise!” And when the teacher handed out exam papers at nine o’clock on Wednesday morning — wasn’t she surprised!

5. Project idea: Investigating Automated Theorem Provers.