1. Create two programs that search lists of words. Both lists are identical, except for the sort order, and each contain 60000 words. Treat the first list as if it is unsorted, even though it is sorted by word size. Use the linear search program given in the class/text to search the unsorted list. Use the binary search to search the sorted list. Both programs will be fed by the same list of words to search for. Some of the words are in the list, some are not. Both programs must include the following:

• Both programs must be instrumented in two ways.
  • Count Compares. The compares counter should be a global variable (declared at the beginning of the program, before main). I will discuss how to do this during the lab period. We will be judging the efficiency of the search by the number of compares it makes. Every time you use an if statement to determine whether a word is in the list, increment the global counter.
  • Run Time. This uses the built in clock in the include file <time.h> to measure elapsed time. Again this will be demonstrated during the lab. We will be judging the efficiency of the search by how long it takes to complete the search. Here is an example program on how to time: timeMeasure.cpp
• When you receive a word from the input list, print it to cout. The input list is searchWords.txt. Your program will take each word in this list and search for it in main list of words. Then print out how many compares it took. For example your output should be similar to the following:

dog, found in 7564 compares and .0000567 seconds

fgdd, not found in 8654003 searches and .00457 seconds

• Your lab report should summarize the data you found comparing the searches and whether the Big O values talked about in class were shown to accurately characterize these two searches.

The first program uses a linear search to search an unsorted list of words. The input file is words60K.txt.

The second program uses the sorted list of words and uses the binary search. The input file is wordsSorted60K.txt

2. Prepare a lab report/documentation package. All of these items do not need to be in the same file or word document, but the main lab report file must reference each item by name. The lab report must includes the following information:

• Your Name
• Purpose of this program.
• Program psuedocode/flowchart
• Program source code
• Program output
• Data analysis of search compares and times versus Big O estimates
• How was this program tested
• What problems/successes did you have with this program?
• An estimate of how much time you spent working on this lab

3. Code the entire program based upon your pseudocode/flowchart. The program should include extensive comments. Save the program as lab08XXX.cpp. Your program must compile and run properly in the Linux environment (clst.tamucc.edu). Compile and run this program and make sure it provides the proper output.

4. You will be submitting this lab via Blackboard. You will need to zip your files together and then upload your zipped submission to Blackboard. Make sure you include the source code and the rest of the documentation package, but not the executable files. The source code for your programs, called lab08***.cpp. Put your initials where the 3 asterisks appear. This files must be ready to compile using the standard g++ compiler.