The goal of this assignment is to design and implement a class and program that can store and process an array of integers. The first task is to create a C++ class that can read and store the values and perform basic operations. The second task is to use recursion to implement binary search to look up selected values. These requirements are described in more detail below:
You will be given two ascii files unsorted.txt and sorted.txt that contain the numbers you will be working with.
You must create a class called "Numbers" that has the following methods. You are welcome to add return types and parameters as needed.
readFile -- read an ascii file to initialize array of numbers getCount -- return the number of values currently stored in the array getValue -- return the value of the number at position "index" findMin -- scan array and return the value of the smallest number findMax -- scan array and return the value of the largest number findMean -- scan the array and return the mean value of all numbers
Write a simple main program to test your Numbers class by calling each of these methods on both of the input files above. Have your program print enough information to verify that the code is working properly.
Now extend your class to add two more methods to your Numbers class. You are welcome to add return types and parameters as needed.
countValue -- scan the array and return the number of time "value" occurs lookupValue -- search the array of numbers for the specified "value"
The countValue method should scan the array of integers looking for a specified value, and count up how many times that value occurs in the array. If the value is not found, your method should return 0.
The lookupValue method should use recursion to implement binary search to quickly locate the specified value in the array. If the value is found, your method should return the index where it was found. If it is not found, your method should return -1. If the value occurs more than once in the array, your method can return any of the indices where the value occurs. You do not need to return multiple results or a range of indices.
To keep things simple, you should use an array to store the integers in the Numbers class. You will also need an additional variable to keep track of how many values are currently in use in this array. This way, if the array size is 100, and you read in 42 numbers, you can loop over 42 values in subsequent methods.
The first part of this assignment is relatively straightforward. You just need to design, implement, and test each of the methods listed above in a sensible order. You should look at your hw1 code to read and process the ascii input files.
Hint: You need to use "din.open( filename.c_str() )" to open an ascii file when filename is a C++ string. You will get an error message if you use "din.open( filename )".
The second part of the assignment is not long, but it is tricky. You may want to implement and test a recursive look up function in a small stand alone program with a global number array, and then adapt your solution to the Numbers class above.
Test your program to check that it operates correctly for all of the requirements listed above. Also check for the error handling capabilities of the code. For example, what happens if you search for a value that is larger or smaller than all of the values in the array? What happen if you execute your lookupValue method on an unsorted input? Save your testing output in text files for submission on the program due date.
When you have completed your C++ program, write a short report (less than one page long) describing what the objectives were, what you did, and the status of the program. Does it work properly for all test cases? Are there any known problems? Save this report in a separate text file to be submitted electronically.
In this class, we will be using electronic project submission to make sure that all students hand their programming projects and labs on time, and to perform automatic analysis of all programs that are submitted. When you have completed the tasks above go to the class web site to "submit" your documentation, C++ program, and testing files.
The dates on your electronic submission will be used to verify that you met the due date above. All late projects will receive reduced credit (50% off if less than 24 hours late, no credit if more than 24 hours late), so hand in your best effort on the due date.
You should also PRINT a copy of these files and hand them into your teaching assistant in your next lab. Include a title page which has your name and uaid, and attach your hand written design notes from above.