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:

4. Compare and

5. Rewrite the proof (given in pages 176-177 of the book) showing that the Halting Problem is unsolvable using the diagonalization proof of 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).

### Like this:

Like Loading...

Filed under: Uncategorized |

Brady Nash, on June 7, 2010 at 6:24 am said:For #3, I think there should be an “i” following the summation.

cot3100su10, on June 7, 2010 at 9:38 am said:That’s right. I corrected it. Thanks.

Craig Andres, on June 7, 2010 at 12:10 pm said:For # 6 what do u mean by sketching the algorithms do u want pseudo code

cot3100su10, on June 7, 2010 at 12:55 pm said: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.

Craig Andres, on June 7, 2010 at 1:45 pm said:ok thank you

Uri Ramirez, on June 8, 2010 at 11:57 pm said:For number 2, should be assume the statement can’t be disproved?

cot3100su10, on June 9, 2010 at 5:32 am said:I made a mistake here. It is power set of A (B), not super set of A (B).