CIS-3050 Homework #1: InsertionSort Performance

Due: Wednesday, August 31, 2016

Read my lesson algorithm performance.

In this class we will be doing our programming with Microsoft's Visual Studio on Windows. Visual Studio is installed on lab machines across campus. If you want to install it on your own machine, start by downloading the community edition of Visual Studio from the Visual Studio home page. The community edition is free for even commercial use provided you are working in a small enough organization (see Microsoft's web site for more information).

When you run the installer be sure to select the custom option. You need to explicitly request installation of "Visual C++" to get the C/C++ compiler we will be using; it is not installed by default.

Visual Studio organizes projects inside of "solutions." You could create a separate solution for each project, but it would be more appropriate to create a single solution for all your work in this class and have different projects in that solution for your various assignments.

Attached to this assignment is a file Samples.zip containing a Visual Studio solution that you can use as a seed for your work this semester. Unpack this file in some suitable location. You will find the file CIS-3050.sln that you can load into Visual Studio.

After loading CIS-3050.sln, verify that you are building the Debug/Win32 configuration (look at the button bar). Then do Build... Rebuild Solution to recompile all the projects. You might see a few warnings but you shouldn't get any errors. Try running the unit tests to verify that they all pass.

At this point you should be all set up for using Visual Studio. You do not need to submit anything for this part of the assignment. Do the following steps:

  1. Modify the InsertionSort demonstration program (in the "Hello" project) so that it uses evenly spaced array sizes from, for example, 10,000 elements to 1,000,000 elements. You don't need to use that exact range, but use a lower bound on the size that is is large enough so the time is not "excessively" short (we want to avoid clock resolution issues). Also use an upper bound that is small enough so the program executes in a "reasonable" amount of time (so you don't have to wait a week for it to finish).

  2. Make a graph of the execution time vs the size of the array. Use a linear scale for both axii of the graph. You should display two lines: one for the specialized version of the algorithm that can only sort integers, and another for the generalized version of the algorithm. Notice that there is an "abstraction penalty" for the more general version.

  3. Assuming your lines follow the function t = cn2 for some constant c, determine the value of c for both the specialized and general algorithms. Does the value of c depend on which data point you use?

  4. Using the previous result, estimate how long the implementation will require to sort 1 billion array elements. Would you like to wait that long?

Submit your graph along with your answers to the other questions (which can just be some text associated with the graph).


Last Revised: 2016-08-11
© Copyright 2016 by Peter C. Chapin <PChapin@vtc.vsc.edu>