CS21 Spring 2005
Homework 9
Due Sunday, March 27, before 11:30pm

• Chapter 13 Review Questions 1-5, 10-13, 16, 19, 22-27 (pages 483-485)

Turn in the following 2 programs:

1. Version 2 of the ASCII Histogram program (using dynamic memory allocation)

   Use your hw6 ascii histogram solution (part of the stats program in hw6) as a starting point for this assignment (similar to problem 11.7 in the book). You may need to modify some of your histogramming function from your hw6 solution to work with this version of the assignment. In addition you will add some new functions.

   Write a histogram program that gets from the user the number of data values, followed by the set of data values, and then gets the histogram bucket size. Your program should then determine how many histogram buckets are needed based on the min and max data values read in, and on the bucket size, create a histogram from the data values array, and then displays the ASCII histogram of that data. The difference between this and the previous histogram program you wrote is that you don't know the range of the input data, nor the number of input values, nor the histogram bucket size in advance. Your histogram's start range should start at the minimum data value read in, and its end range should end at the maximum data value read in (the last histogram bucket may represent less than bucketwidth different values).

   Specifically, your program should:

   1. ask the user for the total number of data values
   2. dynamically allocate space for that much data
   3. ask the user to input the data
   4. ask the user for the histogram bucket size
   5. then dynamically allocate space for the histogram array, based on the highest and lowest data values read in and the histogram bucket size
   6. fill in the histogram array by processing the data values array
   7. display the ASCII histogram (similar to the previous histogram program)
   8. display the high and low data values

   You should use good Top-Down design in your solution (main should contain just a few function calls to the functions implementing the big steps of your program, these in turn, should make calls to other functions, and so on). Make sure that your functions are as generic as possible and are well commented, and that you have good error detection and do not use global variables.

   Specific functions I would like you to include (this is by no means an complete list of the functions in your solution):

   1. GetRange: given an array and its effective size, "returns" both the highest and lowest values in the array.
   2. CreateAndFillArray: takes a size value as input, allocates an array of that size, fills the array with data values entered by the user, and returns the filled array to the caller.

   Make sure that your program takes in the input values in exactly the order specified below (do not change the order of input (e.g. do not read in bucket width before data values), nor add extra input values, nor remove some input from your solution). For example, on the set of input values I'm using in my example run below (15, 44, 55, 66, 77, 88, 99, 34, 35, 36, 23, 21, 77, 76, 75, 44, 8), your program should do exactly the same thing as mine; if it doesn't, then your solution is not correct.

   Again, you can re-direct input from a file to make testing faster:

   	% a.out < testinput
   

   Here is a sample run (click here to see more sample output):

   % ./a.out 
   
   This program will histogram your data. Please enter the
   number of data values, the data values (one per line), and
   the size of the histogram buckets below.
   
   Enter the number of data values: 15
   enter 0th value: 44
   enter 1th value: 55
   enter 2th value: 66
   enter 3th value: 77
   enter 4th value: 88
   enter 5th value: 99 
   enter 6th value: 34
   enter 7th value: 35
   enter 8th value: 36
   enter 9th value: 23
   enter 10th value: 21
   enter 11th value: 77
   enter 12th value: 76
   enter 13th value: 75
   enter 14th value: 44
   Enter the histogram bucket width: 8
   
   21 - 28 | **
   29 - 36 | ***
   37 - 44 | **
   45 - 52 | 
   53 - 60 | *
   61 - 68 | *
   69 - 76 | **
   77 - 84 | **
   85 - 92 | *
   93 - 99 | *
   
   high value = 99
   low value = 21
   

2. The Stats Grade Report Program Revisited (using dynamic memory allocation) For this program, you can use your solution to problem 1 from homework#6 (like problems 11.3 and 11.4 from the book) as a starting point. You will write a program that reads in a set of grade values from the user, until the user enters -1, and then prints out statistics about the set of values (number of grades, min, max, mean, and stddev of the grades). You will store the values in a dynamically allocated array of ints.

   One strategy for reading in a list of data values of unknown size is to start with some initial allocation of space, and if more space is needed, allocate a new space that is twice as large as the first, copy the data over to the new space, free the old space, and set the old pointer to the new one and continue reading in data values (possibly doubling more times as more space is needed). If your solution to the Grade Report problem from hw6 was not correct, you will need to fix it (you do NOT need to include the ascii histogram part of hw6, just the other stats parts). In addition, you will add at least one new function, GetData, that will allocate, fill in and return the array of values (doubling the space as needed).

   Specifically, your GetData function should:

   • dynamically allocate space for the start size array ints (pass in an initial size of 5 for the start size)
   • read in scores from the user until they enter the sentinel value
   • if the array is full, and another score is entered, allocate space for twice as the current size of the array, copy values from old full array to new array and follow the above strategy
   • each time your GetData function doubles the size of the array, it should print out a message saying the array is being doubled and print out how many buckets the new array has
   • use pass-by-reference to "return" the effective size of the array back to main
   • return a pointer to the space allocated for the data

   Use good modular design and have good error detection in your code. Also, run your a.out file with valgrind to make sure you have no memory access errors:

   	% valgrind --leak-check=yes --show-reachable=yes ./a.out
   

   Sample output (again, your program should do exactly the same thing as mine on this set of input):

   %./a.out
   
   This program prints out statistics of a set of grade values 
   entered by the user (enter -1 to stop list of values):
   
   enter next value: 55
   enter next value: 66
   enter next value: 77
   enter next value: 88
   enter next value: 99
   enter next value: 33
   doubling array to 10 buckets
   enter next value: 44
   enter next value: 55
   enter next value: 66
   enter next value: 77
   enter next value: 88
   doubling array to 20 buckets
   enter next value: 99
   enter next value: 77
   enter next value: 77
   enter next value: 88
   enter next value: 66
   enter next value: 67
   enter next value: 67
   enter next value: 67
   enter next value: 60
   enter next value: 55
   doubling array to 40 buckets
   enter next value: 44
   enter next value: -1
   
   ************ Grade Report *************
   number of grades: 22  
   min grade:        33   
   max grade:        99   
   mean grade:       68.86
   standard dev:     17.05
   ****************************************