What we are doing: Using a program to run searches on datasets and collect observations about how many steps two different types of search algorithm require.

Why we are doing this: To think about algorithm efficiency at a high level of abstraction.

Collaboration: you may find it more fun to work with a partner on this lab. In that case, your homework assignment for this week should note the collaboration.

Review linear & binary search

In class, we have discussed both the linear search and the binary search.

1. If you have not already, write a brief description (a few sentences) of how a linear search works.
2. If you have not already, write a brief description (a few sentences) of how a binary search works. Be sure to include any assumptions the algorithm makes.

In class, we have discussed how efficient each of these algorithms might be. Now we take a more concrete, experimental approach.

Search experiments

The searchTest program

The program searchTest performs both a linear search and a binary search for randomly-selected items, and records the (approximate) number of comparisons performed by each search algorithm.

The mechanics of running these search experiments are as follows:

• Open a terminal window and move to the directory containing the searchTest program with the command:

    cd ~rodrigue8/courses/csc105/labs

• Run the program with the command:

    ./searchTest

• The program will ask you to enter the size of the sequence to be searched. I suggest you use values in the range from 1000 to 50,000, but you can also choose smaller or larger sizes for the array. The program then will report on each of the 60 trials (values searched for), and give aggregate results for each search algorithm and each search outcome.Note: Do not use commas when entering numbers.
• Note: After you run the above command the first time, you can use the up-arrow key at your keyboard to retrieve the same command again. After pressing the up-arrow key to get the desired command, just press Enter to run the program again.

Opening a speadsheet

Open a spreadsheet to collect data from your search experiments.

Ideally, you will be able to open a spreadsheet using LibreOffice Calc. However, when I test this earlier, LibreOffice did not have Calc installed on my MathLAN desktop. If you don’t have it, you will need to log in to your Grinnell OneDrive and use Excel online, or Google Sheets if you have an account.

Depending on what option you use, creating a chart from results will require slightly different steps (although the same in basic intent). This will be an opportunity for deciphering interfaces on the fly using intuitive understanding, a key skill for the digital age!

Collecting data from experiments

n this part of the lab, you will gather experimental data regarding the search times for both linear and binary searches, using various array sizes.

Run searchTest for a several (at least 10) array sizes between 1000 and 50,000. To “evenly” space these array sizes in a way that is meaningful for binary search, you could use powers of 2. For example,

Use your spreadsheet to record the results from each program run (i.e., for each array size in your experiment). You will need to record array sizes and average number of steps for:

1. successful searches with linear search,
2. unsuccessful searches with linear search,
3. successful searches using binary search, and
4. unsuccessful searches using binary search.

To do this, place the sizes and steps for (i) in columns A and B, respectively, the sizes and steps for (ii) in columns C and D, respectively, the sizes and steps for (iii) in columns E and F, respectively, and the sizes and steps for (iv) in columns G and H, respectively.

Do double-check your data entry! Typographical errors can add more spice than is intended to your results.

• Now we will the data use your spreadsheet to plot the data for each of the four tables you just created by making a separate graph for each table.We will say exactly how to do this in just a moment. To get a sense of how the search algorithm performance varies with array size, the horizontal axis of each of your graphs should indicate the array size, and the vertical axis should indicate the average number of steps required. You should conduct sufficient experiments so that a fairly consistent pattern emerges.

  Select two of the columns corresponding to the data for one type of search (e.g., columns A and B). In OpenOffice Calc you can create a graph from this data by selecting Chart… from the Insert menu. You will probably find that a “XY (Scatter)” chart is appropriate for this type of data. Once you have selected that, you may also find the subtype called “Points and Lines” to be appropriate. You should also check “Sort by X values.”

  As you click through the options with the “Next>>” button, be sure to label the X and Y axes appropriately and title the graph indicating the search algorithm (e.g., linear or binary) and whether the data is for successful or unsuccessful searches.

  Finally, I suggest that you use the same Y-axis scale for each pair of graphs that depict results from the same search algorithm. This will make a visual comparison of the graphs more meaningful. In OpenOffice Calc, you can set the Y-axis scale as follows. Double-click on the chart, then click on the “Format” menu, followed by the “Axis” entry, and finally “Y-axis” from the menu. In the dialogue box that appears, you can uncheck the “Automatic” selection and set both graphs of the search type to the same to the bound.

• Describe as many conclusions as you can draw from your experiments. For example, you might compare and contrast the various graphs you have made.

Acknowledgements

This lab has been developed by faculty teaching CSC 105 at Grinnell over time. It was most recently revised by Jerod Weinman, and it is his version that is adapted here with only small changes.

Created: Henry Walker, December 31, 2003
Revised: Henry Walker, February 27, 2006
Marge Coahran, March 14, 2007
Marge Coahran, April 3, 2008
Jerod Weinman, January 2, 2009
Jerod Weinman, March 15, 2011
Jerod Weinman, February 25, 2014
Jerod Weinman, January 6, 2015
Adopted from Run-Time Experiments