UMBC CS 202, Fall 00

UMBC CMSC 202 Fall '00

Project 2: Measuring the Performance of an Algorithm Implementation

Due Date:

Midnight Wednesday, 18 October 2000. Note that this means before 23:59:59 on Wednesday evening. The standard project late policy applies.

(Note: Any changes to the project description since the release date will be posted in this color (green).)
This document was last modified on Sunday, 15-Oct-2000 22:41:49 EDT

Objectives

The objectives of this project are:

To learn to make classes in C++
To gain experience in measuring the performance of an implementation of an algorithm
To begin to learn about object-oriented programming

The Problem

In project 2 you will be implementing and measuring three of the sorts discussed in class: selection, merge, and quick sort. Before any of you ask: (a) yes, you may use the version from the notes and (b) yes, you need to document where you obtained the source.

That having been said, your project is really more about instrumenting (that's a fancy word for "modifying") the sorting code to measure some information about its own performance. The big question is: what do we measure?

The most obvious answer is "time". In this case we mean both CPU and "wall" time, so the time() and clock() functions from hw2 will make an appearance in proj2 as well. We can also measure space, but since the running time of a sort is more interesting than the space it takes, we won't concern ourselves with it. Using these library calls we can get a reasonably accurate picture of both the efficiency of our implementation as well as the system load at the time we run the tests. (This is why wall time != CPU time in hw2.)

Once we know how long our implementation takes with respect to the problem size, we can decide confidently that we need to speed it up. The question that comes up next is: "how?"

In addition to measuring time, we're going to be measuring the kinds of operations that sorts perform as well to see which of them is the dominant term in the "big oh" performance of each sort. This will give us some insight into what our implementations are spending their time doing. For sorting algorithms, two major events occur: comparisons between elements and swaps between elements. For each sort we're going to measure these as well.

Requirements

Your program must:

Take command line arguments for a range of elements and the "step size" in between them (see the example below), as well as whether the input array should start out randomized or sorted (using the terms "random" and "sorted" on the command line, respectively).
Implement a class that contains counts for time, cpu usage, swaps, and comparisons and can measure them for any of the three sorts mentioned. Your class must implement the public interface defined in SortMetrics.H but you may make any modifications you like to the private section.
Print a chart of the performance of the three sorts. Your chart should contain 11 columns (see below): n, wall time, cpu usage, number of swaps, number of compares, compares/nlgn, compares/n*n, swaps/nlgn, swaps/n*n, cpu usage/nlgn, and cpu usage/n*n This chart will help illustrate the idea of "big oh" as well as the ideal of the "constant" factor involved in the "big oh" definition.
Use multiple files to separate main(), class methods, and auxilliary functions.
You must properly deallocate all dynamically allocated memory.

Sample Program

A sample executable will be available in the directory /afs/umbc.edu/users/j/k/jkukla1/pub/cs202/fall00/Project2/ on the irix.gl.umbc.edu systems. Please use it to help understand how the program should behave under certain conditions. When in doubt, make it behave like the sample program!

Note: The program is an executable file compiled for irix, so the odds are fairly high that it won't run as is on your home machine.

Sample Output

[irix1] proj2> proj2 1000 21000 2000 random MergeSort(randomzed input): n wall(ms) cpu(ms) swaps compares c/nlgn c/n*n s/nlgn s/n*n cpu/nlgn cpu/n*n ------------------------------------------------------------------------------------------------------------------------- 1000 0 0 19952 8703 0.87329 0.00870 2.00205 0.01995 0.00000 0.00000 3000 0 10 69808 30942 0.89293 0.00344 2.01453 0.00776 0.28858 0.00111 5000 0 20 123616 55233 0.89900 0.00221 2.01203 0.00494 0.32553 0.00080 7000 0 30 179616 80730 0.90290 0.00165 2.00886 0.00367 0.33553 0.00061 9000 0 40 237232 107081 0.90577 0.00132 2.00668 0.00293 0.33835 0.00049 11000 0 50 297232 134173 0.90855 0.00111 2.01271 0.00246 0.33858 0.00041 13000 0 70 357232 161502 0.90905 0.00096 2.01075 0.00211 0.39401 0.00041 15000 0 70 417232 189409 0.91023 0.00084 2.00505 0.00185 0.33639 0.00031 17000 0 80 478464 217657 0.91106 0.00075 2.00274 0.00166 0.33486 0.00028 19000 0 90 542464 246495 0.91274 0.00068 2.00868 0.00150 0.33326 0.00025 21000 0 100 606464 275462 0.91358 0.00062 2.01135 0.00138 0.33165 0.00023 QuickSort(randomzed input): n wall(ms) cpu(ms) swaps compares c/nlgn c/n*n s/nlgn s/n*n cpu/nlgn cpu/n*n ------------------------------------------------------------------------------------------------------------------------- 1000 0 0 2344 15293 1.53455 0.01529 0.23520 0.00234 0.00000 0.00000 3000 0 10 8224 54832 1.58235 0.00609 0.23733 0.00091 0.28858 0.00111 5000 0 10 14742 95743 1.55835 0.00383 0.23995 0.00059 0.16276 0.00040 7000 0 20 21662 140988 1.57684 0.00288 0.24227 0.00044 0.22368 0.00041 9000 0 20 28719 183944 1.55593 0.00227 0.24293 0.00035 0.16917 0.00025 11000 0 30 35821 239720 1.62327 0.00198 0.24256 0.00030 0.20315 0.00025 13000 0 30 43275 293341 1.65113 0.00174 0.24358 0.00026 0.16886 0.00018 15000 0 40 50819 350928 1.68642 0.00156 0.24422 0.00023 0.19222 0.00018 17000 0 40 59623 370686 1.55160 0.00128 0.24957 0.00021 0.16743 0.00014 19000 0 70 67419 431616 1.59822 0.00120 0.24964 0.00019 0.25920 0.00019 21000 0 50 76121 459057 1.52248 0.00104 0.25246 0.00017 0.16583 0.00011 SelectionSort(randomzed input): n wall(ms) cpu(ms) swaps compares c/nlgn c/n*n s/nlgn s/n*n cpu/nlgn cpu/n*n ------------------------------------------------------------------------------------------------------------------------- 1000 0 50 999 499500 50.12149 0.49950 0.10024 0.00100 5.01717 0.05000 3000 0 420 2999 4498500 129.81845 0.49983 0.08655 0.00033 12.12043 0.04667 5000 2000 1200 4999 12497500 203.41459 0.49990 0.08137 0.00020 19.53171 0.04800 7000 2000 2430 6999 24496500 273.97337 0.49993 0.07828 0.00014 27.17757 0.04959 9000 4000 4100 8999 40495500 342.53955 0.49994 0.07612 0.00011 34.68070 0.05062 11000 7000 6220 10999 60494500 409.63959 0.49995 0.07448 0.00009 42.11884 0.05140 13000 9000 8740 12999 84493500 475.58858 0.49996 0.07317 0.00008 49.19484 0.05172 15000 12000 11710 14999 112492500 540.59510 0.49997 0.07208 0.00007 56.27369 0.05204 17000 17000 15060 16999 144491500 604.80684 0.49997 0.07115 0.00006 63.03756 0.05211 19000 25000 18890 18999 180490500 668.33352 0.49997 0.07035 0.00005 69.94728 0.05233 21000 36000 23290 20999 220489500 731.25962 0.49998 0.06964 0.00005 77.24194 0.05281 Note that the resolution from the time() function is in one second increments while the resolution from the clock() function is much higher. To keep the units consistent, all times are printed in milliseconds. Because of this, a wall time of 2000 milliseconds really only says that 2000 <= t < 3000. That is, that 2999 milliseconds wall time will be printed as 2000 milliseconds due to the resolution of the clock.

Coding Standards

For this project you must follow the class coding standards. Remember, you must document your .C and .H files. You need not comment any provided .H files. However, any changes you make to the .H files must be documented according to the class coding standards. All functions must have a header comment as described in the coding standards. Comments inside of functions should be on their own lines and should not share lines with actual code.

For this project, you will be working with C++, possibly for the first time. You may use whatever features of C++ that you like, but you must use at least one class in your project (the SortMetrics class).

Using Code You Didn't Write

Claiming authorship of code that you didn't write is plagiarism and will be dealt with as academic dishonesty. You should not use code that you didn't write; it defeats the learning experience of the project. If you do use outside code on your project, you must cite the source. If a significant portion of the project comes from an outside source, your grade may be reduced.

Testing Your Program

Remember, your program must compile and run using the CC compiler on the IRIX machines (irix.gl.umbc.edu (or irix1 and irix2)). If your program does not compile or does not generate the correct output, you will not receive full credit for this project.

Many systems come with a utility called "make" which helps simplify project compilation. For this class you will be required to use make for each project. The way this is done is by using a "makefile" that tells make what to do when compiling your program.

You may use this sample makefile for this project. You should make sure that you have a makefile named either makefile or Makefile and that when you type make your program compiles to an executable called proj2. Failure to follow these simple directions will result in a reduced grade.

Grading

The grade for this project will be broken down as follows: 50% Correctness This tests that your program behaves the same way that the sample does. 30% Design and Style You should follow the coding standards and make sure your coding style is consistent. 20% Documentation Commenting source code inline as well as header files. A breadown that the graders will receive when they go to grade your project is provided here.

What to Turn In

You should submit your Makefile and any files needed to build your program.

Submitting Your Project

When you have finished and tested your project you can submit it electronically using submit. The project name for this assignment is proj2. As an example, to submit your files, you would type: submit cs202 proj2 Makefile file.1 file.2 ... file.n More complete documentation for submit and related commands can be found here. You should replace all of the file.x's above with your real file names.

Last modified: Sunday, 15-Oct-2000 22:41:49 EDT