CSCI 340 Two Search Algorithms

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

Put the definitions of all constants and the prototypes of your subroutines in your header file *twosort.h*, and put the implementation of the `main()` routine in your source file *twosort.cc*, along with the implementations of of your subroutines, as described below.

Do the followings in your `main()` routine:
1) Define two empty vectors for sizes `ARRAY_SIZE = 200` and `TEST_ARRAY_SIZE = 100`.
2) Pass these two vectors as arguments to the subroutine `generateVectors(...)`. Also pass the seed values `SEED1 = 1` and `SEED2 = 3` to this subroutine.
3) Print the elements of the test (1st) vector before sorting its elements by calling the subroutine `printVector(...)`.
4) Sort the elements of the 1st vector by calling the subroutine `sortVector(...)`.
5) Print the elements of the 1st vector after sorting its elements by calling the subroutine `printVector(...)`.
6) Print the test values in the 2nd vector by calling the subroutine `printVector(...)`.
7) Search each test value from the 2nd vector in the 1st vector using the linear search algorithm by calling the subroutine `searchVector(...)`.
8) Print the statistical values for the linear search by calling the subroutine `printStat()`.
9) Search each test value from the 2nd vector in the 1st vector using the binary search algorithm by calling the subroutine `searchVector(...)`.
10) Print the statistical values for the binary search by calling the subroutine `printStat()`.

Create the following subroutines:
- `void generateVectors(vector<int> &v1, vector<int> &v2, int s1, int s2)`: Fills the elements of vectors `v1` and `v2` with random numbers, generated by two sets of pseudo-random numbers with the seed values `s1` and `s2`, where `s1` is for `v1` and `s2` is for `v2`. To initiate a random number generator `rand` with the seed value seed, execute the system function `srand(seed)` (only once for each vector), 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 from 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 from the STL.
- `int searchVector(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 from the STL.
- `void printVector(const vector<int > &v)`: Prints the contents of vector `v` on stdout, up to `NUM_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 floating-point numbers on stdout, where `totalSucCnt` is the total number of successful comparisons and `vectorSz` is the size of the test vector.

**Programming Notes:**

- Prepare your Makefile (you need to construct and add Makefile) so that the TA only needs to invoke the command make to compile your source file and produce the executable file **twosort**. Make sure you use exactly the same file names specified here, i.e. **twosort**, in your Makefile, otherwise your **submission will get 0 points**.

**Assignment 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.

- Add documentation to the appropriate source files as discussed in your class.

When your program is ready for grading, ***commit*** and ***push*** your local repository to remote git classroom repository and follow the _**Assignment Submission Instructions**_.