Homework 7
Document last modified: 

Overview

Profiling program execution provides detailed empirical data on algorithm performance at different levels of granularity and measures.

The project uses a profiling system to acquire runtimes of three different sorting algorithms under varying problem sizes and initial orderings (sorted or random).

You do not need to program for the project but will need to make minor edits to one file and rerun under different test conditions.

Purpose of Project

• Provide exposure to program profiling.
• Compare the actual running times of three different sorting algorithms
• Use algorithm analysis to predict actual running time

Project Software

• Following software only works with Visual Studio .NET 2003.
• Download and install in the following order (about 600mb):
  1. Visual Studio .NET 2003 Academic Prerequisites
  2. Visual Studio .NET 2003 Academic
  3. DevPartner Community Edition Profiler for .NET 2003
  4. BigDev from C343
  5. Project 1

Visual Studio Project

Follow these instructions for creating a project: When you have added all the files to the project, the Solution Explorer should look like the screen shot to the right. Change A completed driver program is in driver.cpp.  You will be required to make some minor modifications in driver.cpp in order to switch between Sorting_Machine_1, Sorting_Machine_2 and Sorting_Machine_3.  driver.cpp contains a comment describing how this is to be done. Build Compile in Release configuration (so debugging code won't be inserted in your program, and therefore slow it down more). Run Run the program from Visual Studio using the Start Without Debugging command (on the Debug menu).

DevPartner Profiler

After installing it, you can read Help on it by clicking on Help | Contents ... while in Visual Studio .Net Read about: "Native C/C++ Instrumentation Manager" By following the profiler instructions, when the sorting programs are executed, profiling data used in the assignment below will be generated.

Assignment

1. Make 36 runs of the driver
   • run exchange sort 1 time on 6 different sets of integers already sorted in non-increasing order, the set sizes are: 
     500, 1000, 2000, 4000, 8000, 16000
   • run exchange sort 1 time on 6 different sets of randomly generated integers, the set sizes are: 
     500, 1000, 2000, 4000, 8000, 16000
   • run quick sort 1 time on 6 different sets of randomly generated integers, the set sizes are: 
     500, 1000, 2000, 4000, 8000, 16000
   • run quick sort 1 time on 6 different sets of integers already sorted in non-increasing order, the set sizes are: 
     500, 1000, 2000, 4000, 8000, 16000
   • run merge sort 1 time on 6 different sets of randomly generated integers, the set sizes are: 
     500, 1000, 2000, 4000, 8000, 16000
   • run merge sort 1 time on 6 different sets of integers already sorted in non-increasing order, the set sizes are: 
     500, 1000, 2000, 4000, 8000, 16000
   • Note:
     • the driver has been constructed so that it takes command line arguments
       • you can supply the size of the problem as 1st argument, e.g., 2000
       • if you supply any 2nd argument, the driver will load sorted data instead of random data
     • From Visual Studio, you can set the command line arguments by bringing up the project's property page dialog and selecting:
       • Configuration Properties | Debugging
       • then typing in the arguments you want in the 'Command Arguments' edit box. 
       • Rerun the program to execute the new command line arguments.
2. For each run record in an Excel table the following information:
   • Operation called: Exchange_Sort, Quick_Sort, or Merge_Sort
   • How integers were generated: Randomly or sorted non-increasing
   • Number of times operation (Exchange_Sort, Quick_Sort, or Merge_Sort) was called
   • Average running time of the called operation (Exchange_Sort, Quick_Sort, or Merge_Sort).  The average running time appears in a column labeled "Average".
   • Number of items sorted
3. Compute the following for each run using the collected data:
   1. Total time spent in operation
   2. Time spent per item
   3. A math function constructed by you that takes the number of items sorted as its only parameter and outputs an approximation to the actual total time (see Task C, Item #1) spent in the operation
   4. The ratio of Item #3 to Item #1.  Rework Item #3 in an attempt to drive the ratio to 1.0

The resulting table should have following columns:

1	2	3	4	5	6	7	8	9
Sorting Algorithm	Random or Sorted	# Items Sorted	Times Sort Op Called	Average Run Time	Total Time Spent	Time Spent per item	Math Function	Ratio Col #6/#8

 

Turn In

1. Cover sheet with your name, C455, date, and Homework 7.
2. Table containing:
   1. 36 rows (from Task A above)
   2. Each row must contain columns with all the collected data (from Task B) and all the computed data (from Task C).
   3. Make the printout of the table fit on one page.
   4. Use Excel to create some line graphs as follows:
      • x axis = size of the data (Column #3)
      • y axis = total time spent (Column #6)
   5. Create the following graphs:
      • A graph with each algorithm (Exchange, Quick, Merge) on randomly generated data.
      • A graph with each algorithm on already sorted data.
      • A graph with just Merge and Quick sort on randomly generated data.
3. Observations and explanations of:
   1. Make an observation about Column 6 for each sorting algorithm and explain those observations. Use the task manager to monitor system resources.
   2. Describe the math function (not simply a constant) that you arrived at (and how you arrived at it) in Task C, Item #3. The same function should be applied to each group of 6 sorts.
   3. Describe what you did in Task C, Item #4 in an attempt to drive the ratio to 1.0
4. Answers to these questions:
   1. Explain why Exchange Sort didn't perform the same when presented sorted data versus unsorted data.
   2. Explain why Quick Sort didn't perform the same when presented sorted data versus unsorted data.
   3. Would the performance of Quick Sort be significantly different if it were presented data sorted in non-decreasing order as opposed to non-increasing data?  Why or why not?
   4. What would happen to the performance of Quick Sort if the list were passed to it using value semantics versus reference semantics? Consider the overall complexity of Quick Sort.
   5. What surprised you the most about this project?

No hand written answers accepted