1. Explain briefly the differences in output of the various versions of the algorithms, and why they are different. Are they all correct?
2. Use the "time" option on linux to capture the experimental run-time of the various versions of your algorithms, on various sizes of inputs. The sizes to report are 50 elements, 50 commands; 50 elements 1000 commands; 1000 elements 1000 commands; and 1000 elements 10000.
3. Give estimates of the big-O running times that are suggested by these results.Here is an example of an input file, called in.11.8 11
u 5 7
f 7 5
f 5 3
u 9 10 f 2 4
u 1 10
u 2 8
f 1 6
d
To time an execution of testappQU on input and put the output to a file called out.11.8, use the command "time testappQU > out.11.8" The first number is the number of elements. "u 5 7" means execute a
"merge(5,7)" operation. "f 7 5" means execute a "find(7,5)" operation. The following little perl script will help you generate input files for testing.gen
You can copy/paste it into a file. To make it executable, change the permissions using the following command:
chmod a+rx gen
To invoke the perl script, use the command
./gen
and to direct the output to a file, use ./gen > filenameHere You can read the file gen (and edit it) to see what it does. It does not prompt for input (for easyoutputting to a file) but it does require two inputs, the first is the number of elements, the second is the number of operations. Note that all the files end in"d", for debugprint.