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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: