Problem Set 4 Solution

$35.00 $30.80


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





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.


  1. Show that both TApnqand TBpnq are in Opn2q.
  2. Show that TApnq2n2   Opnq and TBpnq  n2   Opnq.


  1. Explain which algorithm is preferable.






  • 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?