completing worksheet

//--------------------------------------------------------------------

//

// Laboratory C, In-lab Exercise 1 search.cpp

//

// Implementation of a set of searching routines

//

// from "A Laboratory Course in C++ Data Structures" (Roberge,Brandle,Whittington)

//--------------------------------------------------------------------

template

int linearSearch ( DT keyList [], int numKeys,

DT searchKey, int &index )

// Linear search routine. Searches the first numKeys keys in keyList

// for searchKey. If searchKey is found, then returns 1 with index

// returning the array index of the entry containing searchKey.

// Otherwise, returns 0 with index returning the array index of the

// entry containing the largest key that is smaller than searchKey

// (or -1 if there is no such key).

{

int result; // Result returned

index = 0;

while ( index keyList[index] )

index++;

if ( index

result = 1; // searchKey found

else

{

index--; // searchKey not found

result = 0;

}

return result;

}

//--------------------------------------------------------------------

template

int binarySearch ( DT keyList [], int numKeys,

DT searchKey, int &index )

// Binary search routine. Searches the first numKeys keys in keyList

// for searchKey. If searchKey is found, then returns 1 with index

// returning the array index of the entry containing searchKey.

// Otherwise, returns 0 with index returning the array index of the

// entry containing the largest key that is smaller than searchKey

// (or -1 if there is no such key).

{

int low = 0, // Low index of current search range

high = numKeys - 1, // High index of current search range

result; // Result returned

while ( low

{

index = ( low + high ) / 2; // Compute midpoint

if ( searchKey

high = index - 1; // Search lower half

else if ( searchKey > keyList[index] )

low = index + 1; // Search upper half

else

break; // searchKey found

}

if ( low

result = 1; // searchKey found

else

{

index = high; // searchKey not found, adjust index

result = 0;

}

return result;

}

//--------------------------------------------------------------------

template

int unknownSearch ( DT keyList [], int numKeys,

DT searchKey, int &index )

// Unknown search routine. Searches the first numKeys keys in keyList

// for searchKey. If searchKey is found, then returns 1 with index

// returning the array index of the entry containing searchKey.

// Otherwise, returns 0 with index returning the array index of the

// entry containing the largest key that is smaller than searchKey

// (or -1 if there is no such key).

{

int result; // Result returned

index = 0;

while ( index

index++;

if ( index

result = 1; // searchKey found

else

{

index--; // searchKey not found

result = 0;

}

return result;

}

//--------------------------------------------------------------------

//

// Laboratory C, In-lab Exercise 2 sort.cpp

//

// Implementation of a set of sorting routines

//

//

// from "A Laboratory Course in C++ Data Structures" (Roberge,Brandle,Whittington)

//--------------------------------------------------------------------

template

void selectionSort ( DT keyList [], int numKeys )

// Selection sort routine. Sorts the first numKeys keys in keyList

// into ascending order.

{

DT temp; // Temporary storage used in swapping

int minPt, // Index of the smallest key in the remaining entries

j, k; // Loop counters

for ( j = 0 ; j

{

minPt = j;

for ( k = j+1 ; k

if ( keyList[k]

minPt = k;

temp = keyList[j];

keyList[j] = keyList[minPt];

keyList[minPt] = temp;

}

}

//--------------------------------------------------------------------

template

void quickSort ( DT keyList [], int numKeys )

// Quicksort routine. Sorts the first numKeys keys in keyList into

// ascending order.

{

quickPartition(keyList,numKeys,0,numKeys-1);

}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template

void quickPartition ( DT keyList [], int numKeys,

int left, int right )

// Recursive partner of the quickSort routine. Partitions the array

// entries between left and right into two subarrays. One subarray

// contains the keys that are less than or equal to splitValue, and

// the other contains the keys that are greater than splitValue.

// Recursively sorts each of these subarrays.

{

DT splitValue, // "Mid" value to use in splitting

temp; // Temporary storage used in swapping

int splitL, // Keys in [left..splitL-1] are

splitR; // Keys in [splitR+1..right] are > splitValue

splitValue = keyList[ ( left + right ) / 2 ];

splitL = left; // Start at left and move toward right

splitR = right; // Start at right and move toward left

do

{

// Go right until key >= splitValue found.

while ( keyList[splitL]

// Go left until key

while ( splitValue

if ( splitL

{

temp = keyList[splitL]; // Swap keys

keyList[splitL] = keyList[splitR]; // at limits

keyList[splitR] = temp;

splitL++; // Continue

splitR--; // partitioning

}

}

while ( splitL

// Sort each subarray.

if ( left

quickPartition(keyList,numKeys,left,splitR);

if ( splitL

quickPartition(keyList,numKeys,splitL,right);

}

//--------------------------------------------------------------------

template

void unknownSort ( DT keyList [], int numKeys )

// Unknown sort routine. Sorts the first numKeys keys in keyList into

// ascending order.

{

DT temp; // Temporary storage used in swapping

int j, k; // Loop counters

for ( j = 0 ; j

for ( k = numKeys-1 ; k > j ; k-- )

if ( keyList[k-1] > keyList[k] )

{

temp = keyList[k];

keyList[k] = keyList[k-1];

keyList[k-1] = temp;

}

}

--------------------------------

//

// Laboratory C, In-lab Exercise 1 timesrch.cpp

//

// Timing program for a set of searching routines

//

//

// from "A Laboratory Course in C++ Data Structures" (Roberge,Brandle,Whittington)

//--------------------------------------------------------------------

// Computes the length of time that it takes to execute a given

// searching routine. Searches for numSearches keys in an ordered

// array of numKeys integers.

#include

#include

#include // For exit()

#include "timer.h"

#include "sort.h"

#include "search.h"

using namespace std;

//--------------------------------------------------------------------

// By default Windows XP has a time resolution of 15.625 milliseconds

// This is called a quantum. To get 3 significant figures in a measured

// result you will need to ensure that you measure times at least

// 100 times longer than the minimum resolution. Tweak numRepetitions

// until you get a minimum time > 1.5s for 1000 keys. On my system

// (numRepetitions == 700) gets me ~ 3.1s at 1000 keys.

//Default timing multiplier

const int numRepetitions = 700; // Number of times to repeat each

// search -- several repetitions

// may be needed in order to

// produce a meaningful timing

//Extra timing multipliers

const int LIN_MULT = 2; // Some algorithms are much faster

const int BIN_MULT = 18; // than the others and need an

const int UNK_MULT = 1; // extra boost to produce a reliable

// timing number. These have been tuned

// to produce similar times at 1000 keys.

const int numSearches = 1000; // Number of searches to perform

// This provides a variety of

// search sets to help remove bias

// from results

//--------------------------------------------------------------------

int main ()

{

Timer searchTimer; // Timer for searching routine

int *keyList, // Array of integer keys

numKeys, // Number of array entries

searchSet[numSearches], // Array of keys to search for

dummy, // Status returned by search

index, // Index returned by search

j, k; // Loop counters

double timePerSearch; // Time per search (in seconds)

// Get the number of keys.

cout

cin >> numKeys;

if ( numKeys

{

cout

exit(1);

}

// Allocate the array of keys.

keyList = new int [numKeys];

if ( keyList == 0 )

{

cout

exit(1);

}

// Initialize the array of keys and the search set.

for ( j = 0 ; j

keyList[j] = rand();

quickSort(keyList,numKeys);

for ( j = 0 ; j

searchSet[j] = rand();

// Output header

// We're doing science here. Let's set the scientific flag for numerical

// output, and set output precision slightly higher than measurement

// precision

cout

cout

cout

cout

cout

// Linear search --

// Determine how long it takes to search for the keys in

// searchSet. Repeat the searches numRepetitions times.

searchTimer.start();

for ( j = 0 ; j

for ( k = 0 ; k

dummy = linearSearch(keyList,numKeys,searchSet[k],index);

searchTimer.stop();

timePerSearch = searchTimer.getElapsedTime() /

( double(numSearches) * double(numRepetitions*LIN_MULT) );

//Output sample info for Linear Search

cout

// Binary search --

// Determine how long it takes to search for the keys in

// searchSet. Repeat the searches numRepetitions times.

searchTimer.start();

for ( j = 0 ; j

for ( k = 0 ; k

dummy = binarySearch(keyList,numKeys,searchSet[k],index);

searchTimer.stop();

timePerSearch = searchTimer.getElapsedTime() /

( double(numSearches) * double(numRepetitions*BIN_MULT) );

cout

// Unknown search --

// Determine how long it takes to search for the keys in

// searchSet. Repeat the searches numRepetitions times.

searchTimer.start();

for ( j = 0 ; j

for ( k = 0 ; k

dummy = unknownSearch(keyList,numKeys,searchSet[k],index);

searchTimer.stop();

timePerSearch = searchTimer.getElapsedTime() /

( double(numSearches) * double(numRepetitions*UNK_MULT) );

cout

// Deallocate the array of keys.

delete [] keyList;

return 0;

}

Enter the number of keys (must be at le (s) S Search Number of Total Time Type Searches linear Search 1400000 3.898e+00 binarySearch 12600000 1.813e+00 unknownSearch 700000 3.866e+00 Press any key to continue The 2.087e-004 is equivalent to 2.087*10* or 0.0002087. Plot the graph and answer the questions (Step 2 - Step 5). Worksheet for F Complete the table by recording the Time per Search column. This involves plotting the time that it takes to run the three algorithms with different numbers of keys. In the end, you will have three lines for the three searches: linear, binary, and unknown. You can use the following four sets of (Time per Search) data to plot the graph. Enter the number of keys (must be at least 1999) : 1998 enter the number of keys (must be at least 1080) : 2000 Time per Search Type Number of Total Time Searches Search(s) Search Number of Total Time ! Time per Type Searches (5) Search(s) linear Search 1400000 1.284e-20 8.600-07 pinarySearch | 12600000 1.184e-00 8.762e-88 unknown Search 7000001 1.182e-00 1.689e-86 Press any key to continue Enter the number of keys (must be at least 1000): 3980 linearSearch 1400000 binarySearch 12600000 anknown Search 700000 Press any key to continue 2.496e-80 1.224e-00 2.330e-80 1.729e-06 9.214-08 3.329e-86 Enter the number of keys (must be at least 1888): 486 Time per Tint per Search Type Number of Total Time Searches (s) Search Type Number of Total Time Searches Search(s) Search(s) linear Search 1400000 binary Search 12600000 unknown Search 700000 Press any key to continue 3.616e+00 1.275e+00 3.414e- 2.583e-06 LinearSearch 1488000 1.012-07 binarySearch 12682080 4.877e-06 unknown Search 708880 Press any key to continue 6.880-00 1.981e+82 6.299e+80 4.857e-86 1.589e-e7 8.999-06 rt 2 Part 1 - Performance or Searching Routines The following questions are taken from A laboratory Course in C++ Data Structures, by Roberge, Brandle and Whittington: Step 2: Complete the following table by recording the Time per Search of the linear Search), binarySearch(), and unknownSearch) routines for each of the values of numKeys listed in the table. Execution Times of a Set of Searching Routines Routine Number of Keys 1000 2000 3000 4000 linear Search() ON ) binaryScarch) Orlog U unknownSearch Step 3: Plot the results below Search Time (10 seconds) 1 Number of Keys in List (NumKeys) Step 4: Consider the two routines in the table above with known big O execution times. Which one should run faster? Describe the expected shape of the curve straight or curved) for both algorithms. Step 5: Using the code in the file search.h and your measured execution times as a basis, what is the execution time (Big O) of the unknownSearch() routine. Briefly explain your reasoning behind this estimate. Enter the number of keys (must be at le (s) S Search Number of Total Time Type Searches linear Search 1400000 3.898e+00 binarySearch 12600000 1.813e+00 unknownSearch 700000 3.866e+00 Press any key to continue The 2.087e-004 is equivalent to 2.087*10* or 0.0002087. Plot the graph and answer the questions (Step 2 - Step 5). Worksheet for F Complete the table by recording the Time per Search column. This involves plotting the time that it takes to run the three algorithms with different numbers of keys. In the end, you will have three lines for the three searches: linear, binary, and unknown. You can use the following four sets of (Time per Search) data to plot the graph. Enter the number of keys (must be at least 1999) : 1998 enter the number of keys (must be at least 1080) : 2000 Time per Search Type Number of Total Time Searches Search(s) Search Number of Total Time ! Time per Type Searches (5) Search(s) linear Search 1400000 1.284e-20 8.600-07 pinarySearch | 12600000 1.184e-00 8.762e-88 unknown Search 7000001 1.182e-00 1.689e-86 Press any key to continue Enter the number of keys (must be at least 1000): 3980 linearSearch 1400000 binarySearch 12600000 anknown Search 700000 Press any key to continue 2.496e-80 1.224e-00 2.330e-80 1.729e-06 9.214-08 3.329e-86 Enter the number of keys (must be at least 1888): 486 Time per Tint per Search Type Number of Total Time Searches (s) Search Type Number of Total Time Searches Search(s) Search(s) linear Search 1400000 binary Search 12600000 unknown Search 700000 Press any key to continue 3.616e+00 1.275e+00 3.414e- 2.583e-06 LinearSearch 1488000 1.012-07 binarySearch 12682080 4.877e-06 unknown Search 708880 Press any key to continue 6.880-00 1.981e+82 6.299e+80 4.857e-86 1.589e-e7 8.999-06 rt 2 Part 1 - Performance or Searching Routines The following questions are taken from A laboratory Course in C++ Data Structures, by Roberge, Brandle and Whittington: Step 2: Complete the following table by recording the Time per Search of the linear Search), binarySearch(), and unknownSearch) routines for each of the values of numKeys listed in the table. Execution Times of a Set of Searching Routines Routine Number of Keys 1000 2000 3000 4000 linear Search() ON ) binaryScarch) Orlog U unknownSearch Step 3: Plot the results below Search Time (10 seconds) 1 Number of Keys in List (NumKeys) Step 4: Consider the two routines in the table above with known big O execution times. Which one should run faster? Describe the expected shape of the curve straight or curved) for both algorithms. Step 5: Using the code in the file search.h and your measured execution times as a basis, what is the execution time (Big O) of the unknownSearch() routine. Briefly explain your reasoning behind this estimate