CSE 321 Closed Lab 8 Instructions

Objectives: To time various implementations of Sorting_Machine and compare their performance.

Set Up: This assignment has two parts. During the closed lab you will complete the data collection steps. The data analysis steps may be done outside of closed lab. To get credit for the closed lab, you must turn in your lab report at class time on Wednesday.

Data Collection:

Set Up: Each team should work together at one workstation.
1. Copy the closed lab #8 course catalog to your group project directory (/project/c321axnn, where "x" is your section letter and "nn" is your team number); type the following command all on one line:
2. Make sure that the new catalog will be accessible to your partner. Perform this action now and as your last act whenever you finish a working session. Note that 'l' in the chmod command is the letter 'l' ("el"), as in "lock":
```
cd /project/c321axnn/closed-lab8

chmod -R g-l,g+rwX .

set-group-ID .
```
Overview: In an emacs window open the file Timing_1.cpp from the closed-lab8 catalog. Read this program and understand it. The only thing that may be unfamiliar is concrete_instance class Timer_1. An object of this type is like a stopwatch except that it doesn't stop; the watch is running exactly when your program is running. The mathematical model of an object of this type is a non-negative integer. The Restart procedure resets the object's value to zero. The Reading function returns its object's current value, which is the number of milliseconds (thousands of a second) of execution time of your program since the last call to Restart. Notice that the implementation of Sorting_Machine timed by Timing_1.cpp is Sorting_Machine_Kernel_1 from the RESOLVE catalog which is the procrastinating implementation (i.e., selection sort).
Compile and Time 1: Do a Build Project for Timing_1.cpp. Then execute the Timing_1 program in a terminal window with the command nice Timing_1 < 10.txt. (Using nice reduces the priority of Timing_1's process so that users who are not sorting large numbers of objects using slow algorithms aren't too much disturbed by our use of the processor; causing such disturbances can interfere with our ability to remain logged in to the system.) In the provided table, record the timing results for input of length N=10. Repeat this process for inputs of lengths 20, 50, 100, 200, 500, 1000, and 2000; the names of the files involved should be obvious. Since selection sort is pretty slow for large inputs, you may want to move on to the next step while you are running Timing_1 on the larger inputs.
Compile and Time 2: Create Timing_2.cpp by copying* Timing_1.cpp and changing it so it times Sorting_Machine_Kernel_2 from the RESOLVE_Catalog which is a heapsort implementation. Do a Build Project for Timing_2.cpp and execute Timing_2 for the same data files you used for Timing_1 above. Record the results in the appropriate table.
Compile and Time 3: Create Timing_3.cpp by copying* Timing_1.cpp and changing it so it times Sorting_Machine_Kernel_3 from the RESOLVE_Catalog which is an implementation of Sorting Machine using quicksort. Do a Build Project for Timing_3.cpp and execute Timing_3 for the same data files you used for Timing_1 and Timing_2 above. Record the results in the appropriate table.

* In the emacs window, use Save As from the File menu to copy a file and give it a different name.

Data Analysis:

Plotting the Results: On the sheets provided in the handout, plot the execution times vs. the number of items being sorted. On the first sheet, you should plot the Insert times for the three implementations. On the second, plot the Change Phase times for the three implementations. On the third, plot the Extract times for the three implementations. And on the fourth, plot the Total times for the three implementations. Be careful and precise in plotting the results. Make sure you label the y axis with appropriate values to show the vertical scale. If you prefer, you can enter the data in an Excel spreadsheet and use that to produce the plots.
Analyzing the Results: Given the plots comparing the performance of three implementations of Sorting_Machine and your knowledge of the algorithms employed, discuss the results and what you can conclude about the trade-offs among the various implementations.

Lab Report: When you have completed all the timings and all the plots, write a short report (one or two typed pages at most) describing your observations and conclusions, and turn it in together with the table with your timings and all the sheets with the plots. The report is due on Wednesday, March 7 at the start of class. One submission per group is enough, but feel free to submit separately if you prefer. In either case, make sure that the name(s) of the submitter is on what you turn in.