In this practical you will learn how to compile a C++ program using the unix g++ command, how to test programs for performance using the unix time command, and how to plot the results on a graph for comparison. You will need to know how to do this for completing your assignments and compulsory practical exercises. Please refer to the notes on the practical page.

There is also a selection of revision exercises, and practice with unix.

1. Open the file testingSearches. You will find two (hopefully familiar!) implementations of a search strategy. In this exercise you will write a short test procedure, compile and run the program, and collect some statistics related to performance.
   1. Inside testingSearches, in the "main" section, write a for-loop which calls one of the two searches (say search) 2000 times. Compile the program, and now run it using the time feature. (See the notes for how to do that.) This tests your program with the chosen input for arrays of size N. Searching for key=N-1 will test the "worst-case". Write down the "real" time it took.
   2. Repeat the exercise now for N=100, 1000, 10000, 100000, 1000000. Each time write down the time it took. Now plot your results on a graph. (Refer to the notes for how to do this in Excel.)
   3. Now repeat the previous two steps, but use binarySearch instead.
   Compare the two results. What do you conclude about the relative performance of the two searching techniques? Does this support the theoretical performance?

2. Practise using unix by following the unix tutorial (see practical page).

3. This exercise is designed to give you practice in debugging. Find and fix the bugs in the following program. Copy the text below into a program file and compile it. Read the compiler output, fo practice in identifying bugs.

         int binarySearch {char A[], first, last, char key}
           {  if (first+1 >= last) return first;
              else{
              int mid= (first+last)/2;
              if (A[mid] <= key) return binarySearch(A, mid, last, key);
              else   return binarySearch(A, first, mid, key);
              }
           }
    

There is no work to submit this week.

All enquiries to Scott M.