Description
For this computer assignment, you are to write and implement a C++ program to implement two search algorithms (linear search and binary search) on randomly generated integers stored in vectors. The program is partially implemented. You can obtain the source file assignment1.cc at /home/turing/mhou/public/csci340spring2019. In this file, several routines are already provided for you. They include the main() routine, the average_comparisons() routine and the random_number() routine. You are required to implement the following routines in your program: • int linear_search(const vector& inputVec, const int x, int& comparisons) : A linear search algorithm, where x is the searched item in vector inputVec. It simply starts searching for x from the beginning of vector to the end, but it stops searching when there is a match. If the search is successful, it returns the position of the found element; otherwise, it returns -1. You need to save the number of comparisons (between x and a vector element) conducted in this search in the parameter comparisons. • int binary_search ( const vector < int >& inputVec, const int x, int& comparisons ) : A binary search algorithm, where x is the searched item in vector inputVec. If the search is successful, it returns the position of the found element; otherwise, it returns -1. The same as above, you need to save the number of comparisons in the parameter comparisons. Note that only equivalence comparisons are counted. • void print_vec ( const vector < int >& vec ) : This routine displays the contents of vector vec on standard output, printing exactly NO_ITEMS = 8 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 = 4 spaces on standard output. Programming Notes: • Do not change existing implementation in assignment1.cc. But you need to 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. Search Algorithms 2 • To compile the source file, execute “ g++ -Wall assignment1.cc –o assignment1.exe”. This will create the executable file assignment1.exe. To test your program, execute “./assignment1.exe &> assignment1.out”, which will put the output (including any error messages) in file assignment1.out. Depending on the implementation of binary search, there may be correct outputs of slight difference. You can find the correct output files assignment1.out1 and assignment1.out2 in the directory shown in the last page. • 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. • When your program is ready, submit your source file and Makefile to your TA by following the Assignment Submission Instructions.
