CPSC 170 Lab 5
Searching and Sliders

As usual, create a lab5 subdirectory for today's lab, open this document in FireFox, and start eclipse.

Timing Search Algorithms

Last week you recorded the runtime of two sorting algorithms. This week, let's try something similar with two search algorithms. To begin, download the following files to your lab5 directory:

Begin by adding options 6 (Linear Search) and 7 (Binary Search) to the menu in RunTimes.java. These options should be implemented in the dispatch method by

  1. Asking the user for a target value. What is a target value that will result in the worst-case behavior?
  2. Performing and timing the appropriate search (using the Search class).
  3. Displaying a message indicating whether or not the target was found and how long it took to execute the search.
Don't forget that the array must be sorted to do binary search! Since sorting can take a long time, You probably will want to create a new menu option that allows you to populate the list with an ordered set of data (i.e. 0,1,2...N). Do not sort it every time the user selects binary search -- this takes too long -- but remind the user that it should be sorted, and when you run the program remember to sort it once before you do binary search.

Try collecting some data on the sort times. What happens when you run the search on 1000 elements? 10,000? 1,000,000? 10,000,000 (This one doesn't work so well does it?) Can you explain why?

So what you should have observed is that your search time is too fast - even with a huge number of elements. If there were 1 million elements in your array, how many comparisons does the binary search need to perform?

So these algorithms aren't really all that different, right? They both execute so fast, we don't even notice. But what if our computer were not completely dedicated to your search. Suppose that there were searches coming in from around the globe! We can simulate this kind of load by introducing a delay at each step of processing. What happens to our performance if we introduce a 10 msec delay at each step of the algorithm? We can do this using the timer class to execute the main loop of our algorithm. (Remember how we did this for the visual search last week?) To accomplish this, you will modify the Searching class as follows:

  1. Add the following static instance variables to the class 
       static int min, max, mid, index;
   static boolean found ;
   
   static Timer timer;
   static Comparable[] theList;
   static Comparable theTarget;
  2. Create two private static innner classes: LinearListener and BinaryListener. The actionPerformed methods for each of these classes should effectively be the body of the two algorithms. When the algorithm stops (target is found or not present), the listener should stop the timer.
  3. The bodies for the two search methods should be replaced with code that
When you have this code implemented, try searching on lists of size 1000, 10000, and 1000000. Now can you tell the difference betweent the run-time of these two algorithms?

Sliders

You have been working with GUI components for quite some time now. You have probably noticed a pattern: Instantiate the control, manipulate some of it's instance data and set up a listener. All that really varies between the various contronls is what instance data you manipulate and what listeners you assign to it.

Sliders are another commonly used GUI control that follow this same pattern. They are used to provide input along a specified range; they raise an event whenever the input value changes.

  1. Download the files:
  2. Study the description of the slider class on p522 in your book.
  3. Add a vertical slider to the BouncerPanel (on the left side of the ReboundPanel) that controls the speed of the bouncing ball. Note: you will need to add a method to reboundPanel as well.

    HAND IN: