Question & Answer: For this computer assignment, you are to write and implement a C++ program to implement two search algori…..

For this computer assignment, you are to write and implement a C++ program to implement two search algorithms ( a linear search and a binary search) on randomly generated integers stored in vectors.

Put the implementations of your subroutines (described below) in your source file sub2.cc and their prototypes in your header file prog2.h.

void Vectors ( vector < int >& v1, vector < int >& v2, int s1, int s2 ) : Fills the elements of vectors v1 of size ARR_SIZE = 200 and v2 of size TEST_ARR_SIZE = 100 with random numbers, generated by two sets of pseudo–random numbers with the seed values s1 and s2, where s1 (defined as SEED1 = 1) is for v1and s2 (defined as SEED2 = 3) is for v2. To initiate a random number generator (RNG) with the seed value seed, execute the system function srand ( seed ) (only once), and to generate a random integer in the range [ LOW = 1, HIGH = 1000 ], execute: rand ( ) % ( HIGH – LOW + 1 ) + LOW.

bool linearSearch ( const vector < int >& v, int x ) : A linear search algorithm, where x is the searched item in vector v. It simply starts searching for x from the beginning of vector v to the end, but it stops searching when there is a match. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the find ( ) function in the STL.

bool binarySearch ( const vector < int >& v, int x ) : A binary search algorithm, where x is the searched item in vector v. If the search is successful, it returns true; otherwise, it returns false. To implement this routine, simply call the binary_search ( ) function in the STL.

int search ( const vector < int >& v1, const vector < int >& v2, bool (*p ) ( const vector < int >&, int ) ) : A generic search algorithm – takes a pointer to the search routine p ( ), and then it calls p ( ) for each element of vector v2 in vector v1. It computes the total number of successful searches and returns that value to the main ( ) routine as an input argument to the print routine printStat ( ), which is used to print out the final statistics for a search algorithm.

void sortVector ( vector < int >& v ) : A sort algorithm to sort the elements of vector v in ascending order. To implement this routine, simply call the sort ( ) function in the STL.

void printVector ( const vector < int >& v ) : Prints the contents of vector v on stdout, up to NO_ITEMS = 16 items on a single line except perhaps the last line. The sorted numbers need to be properly aligned on the output. For each printed number, allocate ITEM_W = 4 spaces for each item.

void printStat ( int totalSucCnt, int vectorSz ) : Prints the percent of successful searches as right-aligned, floating-point numbers on stdout, where totalSucCnt is the total number of successful comparisons and vectorSz is the size of the test vector.

Expert Answer

 

prog2.cpp
———————————————————–
#include “prog2.h”

// Driver program to test two search algorithms – linear
// search and binary search – on vector of integers.

int main ( )
{
// Define two empty vectors of ints for given sizes and
// fill them by random integers for given seed values.

vector < int > A ( ARR_SIZE ), B ( TEST_ARR_SIZE );
Vectors ( A, B, SEED1, SEED2 );

// Print test (1st) vector before sorting its elements.
cout << “Random Numbers Before Sorting:nn”;
printVector ( A );

// Sort test (1st) vector.
sortVector ( A );

// Print test (1st) vector after sorting its elements.
cout << “nRandom Numbers After Sorting:nn”;
printVector ( A );

// Print test values from 2nd vector.
cout << “nRandom Numbers Searched:nn”;
printVector ( B );

// Search each test value from 2nd vector in 1st vector
// using linear search algorithm.

cout << “nLinear Search:n”;
int counter1 = search ( A, B, linearSearch );
printStat ( counter1, TEST_ARR_SIZE );

// Search each test value from 2nd vector in 1st vector
// using binary search algorithm.

cout << “nBinary Search:n”;
int counter2 = search ( A, B, binarySearch );
printStat ( counter2, TEST_ARR_SIZE );

return 0;
}
——————————————————————————–
prog2.cpp
————————————————
#ifndef PROG2_H
#define PROG2_H

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <vector>
#include <algorithm>

using std::cout; using std::endl;
using std::setw; using std::right; using std::setprecision; using std::fixed;
using std::vector; using std::sort;
using std::find; using std::binary_search;

const int LOWEST_NUM = 1; //lowest number possible
const int HIGHEST_NUM = 1000; //highest number possible
const int ITEM_WIDTH = 5;
const int PER_LINE = 16;
const int ARR_SIZE = 200; //size of array with number to search through
const int TEST_ARR_SIZE = 100; //size of array filled with numbers to be searched for
const int SEED1 = 1;
const int SEED2 = 3;

//function prototypes
void Vectors(vector <int>& vec1, vector <int>& vec2, int seed1, int seed2);
bool linearSearch(const vector <int>& vec, int itemSearch);
bool binarySearch(const vector <int>& vec, int itemSearch);
int search(const vector <int>& vec1, const vector <int>& vec2, bool(*p)(const vector <int>&, int));
void sortVector(vector <int>& vec);
void printVector(const vector <int>& vec);
void printStat(int totalSucCnt, int vectorSz);

#endif
————————————————————–
sub2.cpp
———————————
#include “prog2.h”

/******************************
Function: Vectors()
Returns: Nothing
Arguments: A reference to a vector of integers called, vec1
A reference to a vector of integers called, vec2
A integer to hold seed value, seed1
A integer to hold seed value, seed2
Purpose: Fills elements of vec1 and vec2 with random numbers
*******************************/
void Vectors(vector <int>& vec1, vector <int>& vec2, int seed1, int seed2) {
srand(seed1); //fills vectors with random numbers
for(int i = 0; i != ARR_SIZE ; i++)
vec1.at(i) = rand() % (HIGHEST_NUM – LOWEST_NUM + 1) + LOWEST_NUM;

srand(seed2);
for(int i = 0; i != TEST_ARR_SIZE ; i++)
vec2.at(i) = rand() % (HIGHEST_NUM – LOWEST_NUM + 1) + LOWEST_NUM;
}

/******************************
Function: linearSearch()
Returns: True, if item was found
False, if item was not found
Arguments: A reference to a constant vector of integers, vec
A integer to be searched for, itemSearch
Purpose: Linear Search Algorithm, searches for the integer held in item search in the vector.
Starts from beginning and stops when a match in found.
******************************/
bool linearSearch(const vector <int>& vec, int itemSearch) {
return find(vec.begin(), vec.end(), itemSearch) != vec.end(); //returns the true of false, if the number was found or not
}

/******************************
Function: binarySearch()
Returns: True, if item was found
False, if item was not found
Arguments: A rerference to a constant vector of integers, vec
A integer to be searched for, itemSearch
Purpose: Binary Search Algorithm, searches for the integer held in itemSearch in the vector
*******************************/
bool binarySearch(const vector <int>& vec, int itemSearch) {
return binary_search(vec.begin(), vec.end(), itemSearch);
}

/******************************
Function: search()
Returns: A integer that holds the total number of
successful searches and returns that value
Arguments: A reference to a constant vector of integers called, vec1
A reference to a constant vector of integers called, vec2
Purpose:computes the total number of successful searches
and returns that value
*******************************/
int search(const vector <int>& vec1, const vector <int>& vec2, bool(*p)(const vector <int>&, int)) {
vector<int>::const_iterator vecIt; //iterator
int succCnt = 0; //successful count

for(vecIt = vec2.begin(); vecIt != vec2.end(); vecIt++) {
if(p(vec1,*vecIt)) //passes vector one (numbers to be searched through), and dereferenced iterator of vector two (itam to be searched for)
succCnt++;
}

return succCnt;
}

/*******************************
Function: sort()
Returns: Nothing
Arguments: A referance to a vector of integers, vec
Purpose: Sorts the vector in ascending order
********************************/
void sortVector(vector <int>& vec) {
sort(vec.begin(), vec.end());
}

/*******************************
Function: printVector()
Returns: Nothing
Arguments: A reference to a vector of integers, vec
Purpose: Prints the the vector
********************************/
void printVector(const vector <int>& vec) {
vector<int>::const_iterator vecIt;
int itemCnt = 0;

for(vecIt = vec.begin(); vecIt != vec.end(); vecIt++) {
if (itemCnt % PER_LINE == 0) {
if (itemCnt != 0) //makes a new line if desired numbers of items per line is reached
cout << endl;
}
cout << fixed << right << setw(ITEM_WIDTH) << *vecIt;
itemCnt++;
}
cout << endl;
}

/********************************
Function: printStat()
Returns: Nothing
Arguments: A integer that holds sie of vector, vectorSz
A integer that holds number of successful comparisons, totalSucCnt
Purpose: Prints percent of successful searches
*********************************/
void printStat(int totalSucCnt, int vectorSz) {
cout << setprecision(2) << ”     Percent of Successful Searches = ” << ((double)totalSucCnt / vectorSz) * 100 << “%” << endl;
}

Still stressed from student homework?
Get quality assistance from academic writers!