Laboratory 8
Due at the beginning of class, Wednesday, 4/2
In today's lab you will experiment with the running times for different search algorithms that we learned in class.
The code for this lab is available in the directory:
Start the lab as follows:
To understand how this works, open the key.h file. Note that there is a public data member declared as:
bool operator ==(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key()== y.the_key();
}
Now look at the search_compare.cc file. This program sets the list_size to 20 and the number of searches to be performed at 100. It then creates a list containing the given number of odd numbers and calls test_search().
test_search() tests the number of comparisons performed by the sequential_search() function by setting the Key::comparisons variable to zero, and then running searches for 100 randomly selected odd numbers within the list (to test successful searches). After printing the results, test_search() then repeats this process to test for the number of comparisons performed by sequential_search() for unsuccessful searches (by searching for randomly selected even numbers). Look carefully at the test_search() function and make sure you understand the code.
Also provided for you in the search_compare.cc file are two functions:
Your task is to generalize the search_compare.cc program to do the following:
The code for recursive_binary_2() from the book is as follows:
{
Record data;
if (bottom <= top) {
int mid = (bottom + top)/2;
the_list.retrieve(mid, data);
if (data == target) {
position = mid;
return success;
}
else if (data < target)
return recursive_binary_2(the_list, target, mid + 1, top, position);
else
return recursive_binary_2(the_list, target, bottom, mid - 1, position);
}
else return not_present;
}
The purpose of the function, run_recursive_search_2(), is to initialize the variables, bottom and top, to 0 and the_list.size() -1 when calling recursive_binary_2(). (See the implementations for binary_search_1).
To test your code, you should compile the file, search_compare.cc. This file includes not only the list.h file, but also the list.cc file (this is necessary so that the correct object code can be created for the given List_entry type). It also includes key.h and key.cc files. Therefore, to compile use the command:
Sample Output:
When you are done making the modification, here is an example of what your
output should look like for a user input of 15:
radius% ./search_compare Enter the size of the list to test: 15 Timing and testing of search algorithms on a list of size 15 Testing successful comparisons for sequential search: Successful Sequential Search Statistics: Total number of comparisons was 868 Average number of comparisons per search was 8.68 Testing successful comparisons for binary search 1: Successful Binary Search 1 Search Statistics: Total number of comparisons was 492 Average number of comparisons per search was 4.92 Testing successful comparisons for binary search 2: Successful Binary Search 2 Search Statistics: Total number of comparisons was 548 Average number of comparisons per search was 5.48 Testing unsuccessful searches for Sequential search: Unsuccessful Sequential Search Statistics: Total number of comparisons was 1500 Average number of comparisons per search was 15 Testing unsuccessful searches for Binary search 1: Unsuccessful Binary 1 Search Statistics: Total number of comparisons was 494 Average number of comparisons per search was 4.94 Testing unsuccessful searches for Binary search 2: Unsuccessful Binary 2 Search Statistics: Total number of comparisons was 800 Average number of comparisons per search was 8
b. Explain your results for part a for a list length of 100 based on the formulas for the running time of each of the search algorithms given in the text. Do your results match what you would predict from these formulas?
Sequential search (unsuccessful): n
binary_search_1 (successful and unsuccessful): lg(n) + 1
binary_search_2 (successful): (2(n+1)/n) lg(n+1) -3 =~ 2lg(n) -3
binary_search_2 (unsuccessful): 2lg(n)
Parts c - e: Run the search_compare program to answer questions in parts c - e. You will need to test multiple values of n to answer the questions.
c. For what values of n does sequential search do fewer average comparisons than binary_search_1 for successful searches? For unsuccessful searches? (Consider all possible values of n > 0 in your answer, not simply the values given in part a.)
d. For what values of n does sequential search do fewer average comparisons than binary_search_2 for successful searches? For unsuccessful searches? (Consider all possible values of n > 0 in your answer).
e. For what values of n does binary_search_2 do fewer average comparisons than binary_search_1 for successful searches? For unsuccessful searches? (Consider all possible values of n > 0 in your answer).
f. Draw the comparison trees for binary_search_1 and binary_search_2 for n = 7.
What To Turn In.
Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file (e.g. specification of the stack class).
Reminder.
Be sure to save a copy of each file in your labs directory. It is your responsibility
to keep the copies of all programs written for this course until your
graded assignment is returned.
Home | | Syllabus | | Assignments | | Lecture Notes