Problem Set 4 Solution

$35.00 $30.80

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 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.

 

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

 

  1. 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