Homework 7
Document last modified: 

Overview

The text presents algorithms and analysis of an Insertion and Quick sort. The assignment seeks to verify empirically the accuracy of those analysis's by profiling the execution of each algorithm under specific conditions.

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

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

Purpose of Assignment

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

Assignment Software

• Use any profiler that provides function execution times and calls. Two are listed below for Windows:

  If you cannot get a profiler to work (e.g. Visual Studio) use the elapsed times printed by program execution, though these times are not as accurate as a profiler. Using the printed times, for data sorted in ascending order, all times will likely be 0.0000 because the clock interval is too large to measure the execution times. In that case you will not be able to analyze ascending data in the following questions but should get sufficiently accurate results for random and descending data.

  1. MicroProfiler installation

  Integrates with Visual Studio, simple to use and works. You should be able to install on IUS computers without administrative rights. Homepage at: http://code.google.com/p/micro-profiler/

  Install Visual Studio, any version should work but has only been tested with 2008. Available at: Visual Studio 2008

  Download latest MicroProfiler Deployment Package and unzip.

  Follow installation and use instructions at: http://code.google.com/p/micro-profiler/wiki/UsageGuidelinesAutomatic

  Remove the extraneous ; on the end of line 3: Perform the registration: regsvr32 micro-profiler.dll;

  Visual Studio Project

  Copy the two files: driver.cpp, QuickSort.h and InsertionSort.h   Follow instructions to build a project: How to Create a Visual Studio Project Watch this screen capture repeatedly until you get all the details.   Project - Increase stack size for deep recursion. Open the Solution Explorer | Click on the project name, then Project | Properties | Configuration Properties | Linker | System | Stack Reserve Size | 100000000

   

  2. Visual Studio 2008 installation

  Copy the two DVD's in LF111A in the drawer marked C455 DVD's

  or download

   and install in the following order:

  1. Visual Studio 2008
  2. Visual Studio Team System 2008 Team Suite (90-day Trial)

  • Visual Studio Project

    Copy the two files: driver.cpp, QuickSort.h and InsertionSort.h   Follow instructions to build a project: How to Create a Visual Studio Project Watch this screen capture repeatedly until you get all the details.   Project - Increase stack size for deep recursion. Open the Solution Explorer | Click on the project name, then Project | Properties | Configuration Properties | Linker | System | Stack Reserve Size | 100000000

Profiling using Visual Studio

• After creating the project, run one time the Performance Wizard
• Here's how to Make a Profile Run using the Performance Analyzer

Assignment

1. Complete implementation of the Quick sort algorithm from Cormen, Chapter 7.1

   In driver.cpp, comment out the #include to select between Insertion and Quick sorts.
    

2. Create an Excel table:
    

   1	2	3	4	5	6	7	8	9
   Sorting Algorithm	Random, Ascending or Descending	# Items Sorted	Number of Calls	Elapsed Exclusive Time	Elapsed Inclusive Time	Time Spent per item	Math Function	Ratio Col #6/#8

    

3. For each run, record a row in the Excel table the following information:
   • Sorting Algorithm: Insertion or QuickSort
   • How integers were generated: Random, Ascending or Descending
   • Number of items sorted
   • "Number of Calls" to operation (InsertionSort or QuickSort)
     • InsertionSort gets called 1 time only
     • QuickSort, since it is recursive, it gets called more than 1 time
   • "Elapsed Exclusive Time" - the time spent in the function (msec)
   • "Elapsed Inclusive Time" - the time spent in the function and its children (msec)
      
4. Executions 
   1. run Insertion sort on 5 different sets of integers ascending order, the set sizes are: 
      7500, 15000, 30000, 60000, 120000
   2. run Insertion sort on 5 different sets of integers in random order, the set sizes are: 
      7500, 15000, 30000, 60000, 120000
   3. run Insertion sort on 5 different sets of integers descending order, the set sizes are: 
      7500, 15000, 30000, 60000, 120000
   4. run Quick sort on 5 different sets of integers in ascending order, the set sizes are: 
      7500, 15000, 30000, 60000, 120000
   5. run Quick sort on 5 different sets of integers in random order, the set sizes are: 
      7500, 15000, 30000, 60000, 120000
   6. run Quick sort on 5 different sets of integers in descending order, the set sizes are: 
      7500, 15000, 30000, 60000, 120000
       
5. Compute the following in Excel using the collected data:

1. Time spent per item.
2. Math functions constructed by you that takes the number of items sorted as its only parameter and produces as a result an approximation to the "Elapsed Inclusive Time" spent in the operation. These functions should correspond to the behavior elicited by the different data orderings. The Excel math function, where cell C11 contains the number of items sorted, could be similar to: =0.123*C11*C11. Note that exactly the same function should be used for each group of five sets, 7500 to 120000.
3. The ratio of the recorded "Elapsed Inclusive Time" to result of the math function.  Repeatedly rework the function in 2. above in an attempt to drive the ratio to 1.0, meaning they agree. Note that, due to variations in inclusive execution times of the five sets, the ratio will not be exactly 1.0; 0.95 to 1.05 is certainly acceptable.

Analysis of results

1. In an Excel spreadsheet, a table containing:
   • 30 rows (from collected runs above)
   • Each row must contain columns with all the collected data and all the computed data.
   • Make the printout of the table fit on one page.
   • Create five graphs comparing:

   1. the 3 Insertion sort results.
   2. the 3 Quick sort results.
   3. Insertion and Quick sort on descending data results.
   4. Insertion and Quick sort on random data results.
   5. Insertion and Quick sort on ascending data results.
       
      • x axis = size of the data (Column #3)
      • y axis = total time spent (Column #6)

2. In a Word document, make observations and explanations of:

   Note: a significant portion of the grade for this project depends on what you write in response to these questions.

   • For each graph, discuss and explain why you see what you see in the graphs. 
     • Your explanation must include discussion of the algorithm used.
        
   • For Insertion and Quick sort, there is a noticeable difference between "Elapsed Exclusive Time" and "Elapsed Inclusive Time".  Why is there this difference?  Where is the additional time being spent?  How do you explain why is it being spent there?
      
   • Describe the math function at which you arrived and how you arrived at it.  What is the theoretical math function for the two different sorting algorithms being used?  Does each of your math functions mimic the theoretical math function for the given algorithm?  (This question is not asking how it mimics the output of the function, but the actual function itself.)
      
   • Describe what you did in an attempt to drive the ratio to 1.0
      
3. In the Word document, answers to these questions:
   • Explain why Insertion sort did not perform the same when presented sorted data versus unsorted data.  Base your explanation on the algorithm being used.
      
   • Explain why Quick sort did not perform the same when presented sorted data versus unsorted data.  Base your explanation on the algorithm being used.
      
   • Would the performance of Quick sort be significantly different if it were presented data sorted in decreasing order as opposed to increasing data?  Why or why not?
      
   • What surprised you the most about this project?

What to Turn In:

• In a Zip file:
  • Word document with your written answers
    • Be sure to answer all questions asked above.
    • Be sure to make your answers easier to read, and not harder to read.
  • Excel spreadsheet (described above)
  • Visual Studio project.
• Upload the Zip file to the Drop Box on C455 Oncourse
  • Note: if it is not in the Zip file, I can't grade it, and your grade will suffer.