last revised March 13, 2005
| CSC 153 | Grinnell College | Spring, 2005 |
| Computer Science Fundamentals | ||
| Laboratory Exercise | ||
This laboratory exercise introduces some principles of algorithm effectiveness, including the amount of time and memory required for the algorithm. Big-O notation is introduced to provide an informal measure of the time or space required by an algorithm. These ideas are applied to the linear and binary search algorithms, discussed in the lab on searching.
The reading for this lab describes several factors related to effectiveness of algorithms. The reading then analyzes the run-time efficiency of both linear search and binary search algorithms.
The following table gives experimental measurements from one machine for the average time required for a linear search for several search trials.
| Array | Average Time | Average Time If |
|---|---|---|
| Size | If Value Found | Value Not Found |
| 1000 | 620 | 1248 |
| 2000 | 1260 | 2490 |
| 4000 | 2540 | 4960 |
Estimate the time for an average linear search of arrays of size 1500, 3000, 8000, and 16000. Briefly justify your answers.
Write a paragraph that summarizes the analysis in the reading for the binary search, using your own words.
The following table gives experimental measurements for the average time required for a binary search for several search trials.
| Array | Average Time | Average Time If |
|---|---|---|
| Size | If Value Found | Value Not Found |
| 1000 | 33 | 33 |
| 2000 | 37 | 37 |
| 4000 | 41 | 41 |
Why do you think the timings here are about the same, regardless of whether the item is found or not?
Estimate the time for an average linear search of arrays of size 1500, 3000, 8000, and 16000. Briefly justify your answers.
Be sure you do the previous parts of this lab before proceeding!!
Program ~walker/java/examples/searching/searchTest.java provides a framework for timing the linear and binary search algorithms, as described above. This program illustrates the use of a timing method System.currentTimeMillis(), which returns a time in milliseconds. As the algorithms run very quickly, the program repeats each search 1000 times, so timing measurements in milliseconds will yield appropriate numbers.
The program asks the use to set the minimum and maximum array sizes to be tested, as well as the number of trials to be tested at each array size. Program execution then picks elements at random, applies the search algorithms, and reports the timings. After arrays of one size are tested, the array size is doubled, and the process repeats.
Copy ~walker/java/examples/searching/searchTest.java to your account, compile it, and run it several times.
Review the code, and write a paragraph explaining how the code generates its output table. For example, be sure to identify what elements are placed in an array, how an item is selected for starting the search, how timing is done, and what algorithms are tried when.
Run the program for array sizes 1000 through 16000. Then run the program again for array sizes 1500 through 3000. Occasionally, one value in the table may be significantly larger than others. Such anomalies may be explained by various technical details of the operating system and machine environment. Ignoring any such unusual values, how do the results obtained from these runs compare with your estimates earlier in this lab? Briefly discuss any similarities or differences.
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-complexity.shtml
|
created January 14, 1998 last revised March 13, 2005 |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |