Lab 4 Goals:

• To understand and use C pointer variables, dynamic heap memory allocation (malloc/free) and C style "pass by reference"
• To use gdb and valgrind to debug C programs, particularly for memory access errors.

Contents:

• Getting Starting Point Code
• Assignment Overview
• Sample Output
• Requirements
• Hints, Tips, and Resources
• Extra Challenge
• Submitting

Here are the new partnerships. The course webpage has a section on expectations for working with partners.

Both you and your partner should:

1. On the CS system, cd into your cs31/labs subdirectory

   cd ~/cs31/labs
   

2. Get your Lab04 ssh-URL from the GitHub server for our class: CS31-s18
3. Clone a local copy of your shared repo in your private cs31/labs subdirectory:

   git clone [your_Lab04_URL]
   

You should see the following files in your repo:

Makefile       grades.c     grades1.txt  readfile.c
QUESTIONNAIRE  grades0.txt  grades2.txt  readfile.h

For more detailed instructions see the the Using git guide.

Educators sometimes want a statistical analysis of a set of exam scores. These analyses could be done for an exam from a single class or an exam from an entire school district. A useful tool would be a program that computes statistical results for any size data set (i.e. it would work for ten values or for thousands, without re-compilation).

We will implement such a program this week. The program should take as a command-line argument the name of a file that contains a bunch of floats, one per line. The program then stores these values, computes a bunch of statistics about them, and prints the result to the user.

The starting point code comes with three input files that you can use to test your solution.

This program needs the readfile library and the math library. We have given you a Makefile that links in these libraries, so you should use the Makefile to compile. By reading the Makefile, you can see how the executable is built from a .c file and a .o file. The -lm flag tells gcc to link in the math library.

grades.c has the starting point code for your program. It contains a prototype for the get_values function that you need to implement, and it has some code in main that copies the file name given at the command line into a string local variable.

Your program should do the following:

1. Make a call to get_values, passing in the name of the file containing the values, and passing in two values by reference: the address of an int variable to store the size of the array (number of values read in); and the address of an int variable to store the total capacity of the array (number of values allocated).

   get_values returns an array of float values initialized to the values read in from the file, or returns NULL on error (like if malloc fails or if the file cannot be opened). It dynamically allocates the array it returns and uses a doubling re-allocation algorithm if it runs out of space (see the requirements section for details about this algorithm).

2. Compute the maximum, minimum, mean, median, and standard deviation of the set of grade values. Print out the total number of grades and each of these measures.

3. Print out a histogram from the set of grade values.

   Each histogram bucket counts the number of exam scores in a particular range: 0-9, 10-19, 20-29, etc. Exam grades that have a fractional component (e.g. 89.75) should be counted as being in a histogram bucket range based on their whole number part only (e.g. 89.75 is a grade in the 80's not a grade in the 90's).

4. Print the amount of unused capacity in the array storing the grade values.

The statistics you need to compute are:

1. mean: the average of the set of values. For example, if the set is: 5, 6, 4, 2, 7, the mean is 4.8 (24.0/5).
2. median: the middle value in the set of values. For example, if the set is: 5, 6, 4, 2, 7, the median value is 5 (2 and 4 are smaller and 6 and 7 are larger).
3. stddev: is given by the following formula:

   $s=\sqrt{\frac{1}{N-1}\underset{i=1}{\overset{\mathrm{N}}{\sum \; <!--\; n-ary\; summation\; -->}}{\left(x_i-\stackrel{-}{x}\right)}^2}$
   Where $N$ is the number of values, $x_i$ is the $i^{\text{th}}$ value, and $\stackrel{-}{x}$ is the mean (average) value.

Here is sample output from a working program run on the three input files that were included with the starting point code. You should also test your program on other input files that you create.

• The array of values should be dynamically allocated on the heap by calling malloc. You should start by allocating an array of 20 float values. If you run out of capacity as you are reading in values:
  
  
  1. Call malloc to allocate space for a new array that is twice the size of the current full one.
  2. Copy values from the old full array to the new array (and make the new array the current one).
  3. Free the space allocated by the old array by calling free.
  
  When all of the values have been read in from the file, the function should return the filled or partially filled array to the caller (the function's return type is float *). The size and capacity of the array should be "passed" back to the caller via the pointer parameters that are used for pass-by-reference values.

  There are other ways to do this type of alloc and re-alloc in C. However, you should use this method.

  
  
• Your program should have at least four functions, be well commented, and use meaningful variable names. The functions should each be doing a non-trivial task.

• All TODO comments in the starting point code should be removed in the code your submit (these are our comments to you, not your comments describing what the code does).

• You may assume that all grade values are between 0.0 and 100.0. Grade values such as 67.5 or 70.25 are valid (don't assume whole number grades only).

• The histogram counts the number of grades within each range. You may assume range widths of 10 values: 0-9, 10-19, etc. This means you'll need a separate histogram bucket for grades of 100.

• You may use a statically declared array for the histogram, or you can dynamically allocate it if you'd like. If you use a statically declared array, you should #define a constant for its length.

• Your program should be free of valgrind errors.

• If a function returns a value, the calling code should get the return value and do something with it. For example, if a function returns an "error or success" return value, the calling code should check for and handle error return values.

• Your program should use good design, be well commented, and have no lines longer than 80 characters.

• Write get_values to work without the re-allocation and copying part first (for fewer than 20 values). Once that works, then go back and get it to work for larger input files.

• You may have written code for lab 2 that would be useful, or useful as a reference, for this lab assignment.

• Use double variables to store and compute the mean and the square root.

• The C math library (in math.h), has a function to compute the square root:

  double sqrt(double val);

• We haven't given you the full algorithm for finding the median. Devise your own algorithm on paper before attempting to implement it.

• See lab 2 and the readfile.h comments for information about using the readfile library.

• Take a look at the weekly lab code and in-class exercises to remind yourself about malloc, free, pass-by-reference, pointer variables, dereferencing pointer variables, and dynamically allocated arrays.

• Printing out the histogram does not require using C string variables, nor does it require using the C string library functions to manipulate C strings. Think about what you need to do for each bucket in the histogram: print out the range it represents and then print out a star some number of times corresponding to the value stored in that bucket. Remember printf won't print a newline character unless you explicitly include a (\n) in the format string.

• Make use of valgrind and gdb in debugging your program. Also, look at the Wednesday in-lab exercises for some examples of how to use these tools.

This is not required, so don't attempt this challenge until you have finished all other parts of this lab.

Extra challenge

There is a QUESTIONNAIRE file for you to fill out and submit with your lab solution. Your answers to the questionnaire will not affect your grade.

Only one member of your partnership needs to git push your solution before the deadline.