due Tuesday, 9/21
Problems from the back of chapter 5: #5, 14, 15, 19, 20, 21, 31.
I know some of you have had trouble getting ahold of the text, so I've extended the due-date to Thursday.
Problems 20, 21, and 31 will require you to measure run-time of Java code. Use the techniques outlined in section 5.7 of the text and Figure 5.13. Basically, you will want to run the program for several values of n, recording the run-time of each. (A good starting point is to work with a series of doubling-values for n, such as 10K, 20K, 40K, 80K, etc.) Use a spreadsheet to build a table similar to Figure 5.13, where you record the values for the recorded times T(n), along with the ratio of T(n)/E(n), where E(n) is the big-oh function you think correct for the algorithm. If the ratio tends to remain relatively constant for larger values of n, then you have probably determined the big-oh run-time of the segment of code.
For measuring the time, try using System.nanoTime(). While the name implies nanosecond precision, this may not be the case on your machine. You'll get much more accurate results if the run-time is at least 5-10 seconds. As the execution of your code for small values of n will be much less than that, you'll want to time a loop running your code many times (call it m) and then divide the measured time bym to get a good approximation of the actual run-time of your code.