Lab 12

April 15, 2004

Partners

You may work with at most one other person on this assignment. If you do, you will both receive the same grade.

Purpose

The purpose of this in-lab is to (1) give you more experience with empirical investigations, (2) give you practical experience with several standard searching techniques, and (3) give you more practice with recursion.

Search Code Base

Copy the code that we covered in lecture on Wednesday, April 14th into a BlueJ project named lab12

Part I: Empirical Modification, 8 points

As we saw in lecture on Wednesday, the system clock has some pitfalls to it. Modify the code so that oneExperiment prints out the average number of array accesses per element instead of the average number of milliseconds per element.

Part II: Interpolation Search, 12 points

Interpolation search is described on pages 372-373 of the class textbook. Implement interpolationSearchRecursive. Modify test to check whether it is working correctly. Modify main and experiment so that empirical data is collected for each of the four search techniques.

What to Submit

Note: As always, partial credit is possible. If you don't finish the entire assignment, hand in whatever you can at the end of your lab period.

1. A printout of interpolationSearchRecursive.
2. A printout of the output that your program produces when it is run with the four searches.
3. A one page writeup that interprets the output of your program for each of the four searches. Try to explain any trends that you see in the output.

Before You Leave Lab

Delete the BlueJ projects that you created and empty the recycle bin. Thanks!