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

### 7 Responses

1. For #3, I think there should be an “i” following the summation.

2. For # 6 what do u mean by sketching the algorithms do u want pseudo code

• You can briefly describe how the algorithms work step by step in normal language like:

The algorithm run recursively:
– If the size of the array is 1, return it as the sorted array.
– If the size of the array is greater than 1, divide the array into two equal size parts. Sort each part then merge two sorted parts into a sorted array.

You can also write pseudo code to describe them but not copy the online pseudo codes.

3. For number 2, should be assume the statement can’t be disproved?