ITEC 122 2008fall ibarland

home—info—lectures—exams—archive

hw08
running times; big-Oh

When showing that one function is big-Oh of another, use the definition of big-Oh and find specific constants c,k satisfying the definition of big-Oh¹

1. Rosen p.191, #14 (5ed: p.142 #14). You need only answer “true” or “false”.
2. Rosen p.191, #10. (5ed: p.142 #10) (This is a proof.)
3. Extra credit Rosen p.191, #16. (5ed: p.142 #16) (This is a proof.)
4. Rosen p.191, #18. (5ed: p.142 #18) (This is a proof.)
5. p.177 #10 (algorithm to calculate xⁿ). How many multiplications and divisions, exactly, does your algorithm require?
6. p.199 #4 (#steps to calculate x^2^k)
7. Current computers can have a clock speed of about 3GHz — 3 billion bit-operations per second (!). Complete the following table with the most appropriate:
   • “≤ one μs” (one microsecond — 10^-6s)
   • “≤ one second”,
   • “≤ one day”,
   • “≤ one year”,
   • “≤ one millenium” (=1000yrs),
   • “≤ one universe-lifetime” (=10¹⁰yrs)
   • “longer”,

   problem size	bit operations needed
   problem size: n	log n	n	n²	n3	2n
   10
   100
   1000
   106 (million)
   109 (billion)

8. p.179 #54 (making change w/o nickels). For those problems where the greedy algorithm doesn't use the smallest number of pennies/dimes/quarters, show how to give change that does use the smallest number of coins.

   Aside: This problem is interesting because Rosen shows that the greedy algorithm is optimal when nickels are included, but now we see that in other situations the greedy algorithm isn't optimal. Rosen's proof is not as 'obvious' as it might seem, since it depends on nickels in some crucial way.

   Aside, continued: Mathemeticians immediately start to wonder: When considering different types of coins, what conditions are sufficient to guarantee that the greedy algorithm will work? What conditions are necessary, to guarantee this?

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Dec.15 (Mon)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu