CSCI 340 Computer Assignment 2 Spring 2018 (10 points)

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/csci340spring2018. 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 vectors 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 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

#include
	#include
	#include
	#include
	#include
	#include
	using std::setw;
	using std::cout;
	using std::endl;
	using std::vector;
	using std::srand;
	using std::rand;
	using std::sort;
	const int DATA_SIZE = 100;
	const int SEARCH_SIZE = 50;
	const int DATA_SEED = 11;
	const int SEARCH_SEED = 7;
	/***************************************************************
	genRndNums
	Use: This function generates random numbers using the srand()
	and rand() functions.
	Parameters: A reference to a vector v and an integer seed.
	Returns: None
	***************************************************************/
	void genRndNums( vector& v, int seed )
	{
	}
	/***************************************************************
	linearSearch
	Use: Performs a slow linear search across a vector. Also uses
	the find method, which is slow.
	Parameters: A reference to a constant vector called inputVec.
	Plus an integer named x.
	Returns: Either true or false.
	***************************************************************/
	bool linearSearch( const vector& inputVec, int x)
	{
	}
	/***************************************************************
	binarySearch
	Use: Implement the binary search algorithm using STL algorithm
	binary_search().
	Parameters: A reference to a vector of type integer called
	called inputVec. Plus an integer called x.
	Returns: A bool.
	***************************************************************/
	bool binarySearch( const vector& inputVec, int x)
	{
	}
	/***************************************************************
	search
	Use: Returns the amount of times a search was successful.
	Parameters: Two references to a constant vector of type integer
	named inputVec and searchVec. A pointer to a function called p
	that takes a reference to a constant vector of type integer.
	Returns: An integer.
	***************************************************************/
	int search( const vector& inputVec, const vector& searchVec,
	bool (*p)( const vector&, int) )
	{
	}
	/***************************************************************
	sortVector
	Use: Sorts a vector in ascending order.
	Parameters: Takes a reference to a vector of type integer
	name inputVec.
	Returns: None.
	***************************************************************/
	void sortVector (vector& inputVec)
	{
	}
	/***************************************************************
	printStat
	Use: Prints the percent of successful searches as floating
	point numbers.
	Parameters: An int called totalSucCnt, and an int called
	vec_size.
	Returns: None.
	***************************************************************/
	void printStat (int totalSucCnt, int vec_size)
	{
	}
	/***************************************************************
	print_vec
	Use: Prints the contents of vector.
	Parameters: A reference to a constant vector of type int called
	vec.
	Returns: None.
	***************************************************************/
	void print_vec( const vector& vec )
	{
}
	int main() {
	vector inputVec(DATA_SIZE);
	vector searchVec(SEARCH_SIZE);
	genRndNums(inputVec, DATA_SEED);
	genRndNums(searchVec, SEARCH_SEED);
	cout << "----- Data source: " << inputVec.size() << " randomly generated numbers ------" << endl;
	print_vec( inputVec );
	cout << "----- " << searchVec.size() << " random numbers to be searched -------" << endl;
	print_vec( searchVec );
	cout << " Conducting linear search on unsorted data source ..." << endl;
	int linear_search_count = search( inputVec, searchVec, linearSearch );
	printStat ( linear_search_count, SEARCH_SIZE );
	cout << " Conducting binary search on unsorted data source ..." << endl;
	int binary_search_count = search( inputVec, searchVec, binarySearch );
	printStat ( binary_search_count, SEARCH_SIZE );
	sortVector( inputVec );
	cout << " Conducting linear search on sorted data source ..." << endl;
	linear_search_count = search( inputVec, searchVec, linearSearch );
	printStat ( linear_search_count, SEARCH_SIZE );
	cout << " Conducting binary search on sorted data source ..." << endl;
	binary_search_count = search( inputVec, searchVec, binarySearch );
	printStat ( binary_search_count, SEARCH_SIZE );
	return 0;
	}