## Description

Total 100 points.

Problem 1. (5 points) Let x be a real number and n an integer. Show that

rxs n if and only if x ¤ n x 1:

[Hint: Use the de nition for rxs n given as the second fact among the four facts in slide #39 in the lecture slides on Sets and Functions. What you are proving here is the last fact in the same slide.]

Problem 2. (15 points) Let n be a positive integer. Show that if n is a perfect square, then

Problem 3. (10 points) Let f_{1}; f_{2}; f_{3} be functions from the set N of natural numbers to the set R of real numbers. Suppose that f_{1} Opf_{2}q and f_{2} Opf_{3}q. Is it possible that

Problem 4. (10 pts 3 = 30 points) Determine whether each of the following statements is true or false. In each case, answer true or false, and justify your answer (by giving a direct proof if it is true, or a proof by contradiction if it is false; always use the de nition involving the absolute values, as given in class).

Problem 5. (10 points) Let k be a xed positive integer. Show that

_{1}k _{2}k _{n}k _{O}_{p}_{n}k 1q

holds.

Problem 7. (5 pts 3 = 15 points) Suppose that you have two algorithms A and B that solve the same problem. Algorithm A has worst case running time T_{A}pnq 2n^{2} 2n 1 and Algorithm B has worst case running time T_{B}pnq n^{2} n 1.

- Show that both T
_{A}pnqand T_{B}pnq are in Opn^{2}q. - Show that T
_{A}pnq2n^{2}Opnq and T_{B}pnq n^{2}Opnq.

- Explain which algorithm is preferable.

Checklist:

- Did you type in your name and UIN?

- Did you disclose all resources that you have used?

(This includes all people, books, websites, etc. that you have consulted.)

- Did you electronically sign that you followed the Aggie Honor Code?

- Did you solve all problems?

- Did you submit both of the .tex and .pdf les of your homework to the correct link on eCampus?

5