## Description

Similar to Assignment 1, you are to implement two search algorithms (linear search and

binary search) in C++ on randomly generated integers stored in vectors. In this

assignment, you will use routines from STL to implement these algorithms.

Assignment2.cc is provided to you at the directory:

/home/turing/mhou/public/csci340spring2019.

In this file, the main function is already implemented. You are required to implement the

following functions:

• void genRndNums ( vector < int >& v, int seed ) : This

routine generates random integers in the range [ LOW = 1, HIGH = 100 ]

and puts them in vector v. Initializes the random number generator (RNG) by

calling the function srand() with the seed value seed, and generates random

integers by calling the function rand(). To use srand and rand, you need

the header . The vector v is already allocated with space. Use

vector’s member function to get the size of the vector.

• bool linearSearch ( const vector < int >& inputVec,

int x ) : A linear search algorithm, where x is the searched item in vector

inputVec. 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 from the STL .

• bool binarySearch ( const vector < int >& inputVec,

int x ) : A binary search algorithm, where x is the searched item in vector

inputVec. If the search is successful, it returns true; otherwise, it returns

false. To implement this routine, simply call the binary_search()

function from the STL .

• int search ( const vector < int >& inputVec, const

vector < int >& searchVec, 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

searchVec in vector inputVec. 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 >& inputVec ) : A sort

algorithm to sort the elements of vector inputVec in ascending order. To

STL algorithms

2 CSCI 340

implement this routine, simply call the sort() function from the STL

.

• void printStat ( int totalSucCnt, int vec_size ) : Prints

the percent of successful searches as floating-point numbers on stdout, where

totalSucCnt is the total number of successful comparisons and vec_size

is the size of the test vector.

• void print_vec ( const vector < int >& vec ): This routine

displays the contents of vector vec on standard output, printing exactly

NO_ITEMS = 10 numbers 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 = 6 spaces on standard output. You can re-use the

implementation of this routine from Assignment 1, but remember to change the

values of related constants.

Programming Notes:

• Include any necessary headers and add necessary global constants.

• You are not allowed to use any I/O functions from the C library, such as scanf

or printf. Instead, use the I/O functions from the C++ library, such as cin or

cout.

• You need to use correct implementation of print_vec from the first

assignment. Please seek help from the TAs if necessary.

• Execute the srand ( ) function only once before generating the first random

integer with the given seed value SEED. The rand ( ) function generates a

random integer in the range [ 0, RAND_MAX ], where the constant value

RAND_MAX is the largest random integer returned by the rand ( ) function

and its value is system dependent. To normalize the return value to a value in the

range [ LOW, HIGH ], execute:

rand ( ) % ( HIGH – LOW + 1 ) + LOW.

• In the final version of your assignment, you are not supposed to change existing

code, including the main method, provided to you in the original source file

assginment2.cc.

• To compile the source file, execute “ g++ -Wall assignment2.cc –o

assignment2.exe”. This will create the executable file assignment2.exe.

To test your program, execute “./assignment2.exe &>

assignment2.out”, which will put the output (including any error messages)

in file assignment2.out. You can find the correct output of this program in

file assignment2.out in the directory shown in the last page.

3 CSCI 340

• Add documentation to your source file.

• Prepare your Makefile so that the TA only needs to invoke the command “make”

to compile your source file and produce the executable file assignment2.exe.

• When your program is ready, submit your source file and Makefile to your TA by

following the Assignment Submission Instructions.