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 f1; f2; f3 be functions from the set N of natural numbers to the set R of real numbers. Suppose that f1 Opf2q and f2 Opf3q. 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
1k 2k nk Opnk 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 TApnq 2n2 2n 1 and Algorithm B has worst case running time TBpnq n2 n 1.
a) Show that both TApnq and TBpnq are in Opn2q.
b) Show that TApnq 2n2 Opnq and TBpnq n2 Opnq.
c) 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
