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

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

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: