CSCI 520 Information Structures Fall 2008
Lab SP (Semester Project) Assignment
Comparison of Algorithms to Find the Mode in an Ordered Array
Write a program to compare the execution speed of different versions of an algorithm or different algorithms to find the mode in a list (array). For lists, the mode is the most common (frequent) value. A list can have more than one mode. For histograms, a mode is a relative maximum ("bump"). A data set has no mode when all the numbers appear in the data with the same frequency. A data set has multiple modes when two or more values appear with the same frequency. The data in the array will be ordered and will consist of at least 5 million numbers in the range of signed long. You will continue examining different algorithms or modifications until you are satisfied that you found the fastest method to solve the problem.
Use the following guidelines to complete this assignment:
Write a function and any other code necessary to return the mode in the parameter list if found. You can write as many functions as you need to solve this problem, however, you must have at least one function and any additional functions, if any, must be called from the ‘controlling function’. Return a 1 if a unique mode was found and assign the mode value to the last argument. Return a zero if there is no mode because all the values occurred with the same frequency, or return a 2 if the mode is not unique. The first line of the function definition is as follows:
int mode (long *data, long data_size, long &mode)
You cannot permanently change the contents of the array in which you are checking for duplicates. You can use any algorithm to solve the problem including algorithms from 515. If you create any structures, including additional arrays, or write additional functions, the structure definitions and prototypes must be placed at the beginning of the ‘controlling function’. Any additional memory allocated in the ‘controlling function’ must be deleted before the function terminates.
You must keep a record of each algorithm or modification of an algorithm that you timed. The simplest method may be to number them beginning with 1. You will record in a written document each algorithm or modification to an algorithm that you timed including the actual timing value. You must briefly describe the algorithm besides including the actual code. The timing code is available on the ‘GA’ computer in the 101/102 lab along with 3 data sets of 10 million values each that provide for the 3 values to be returned from the function. Your written report (done in Word 2003) must include your name, class id, campus wide id and the semester in which the project was completed. The report must also include a graph (no pie chart) showing the difference in the time for each algorithm. Do not include the timing code in the written document; just mention which method you used, C++ method or the Windows method.
You will be graded on the completeness of your written document and the fastest time that you were able to achieve.
Assignment is due