Homework 2: Stats Solution

Description

Educational Objectives: After successfully completing this = assignment,=20 the student should be able to accomplish the following:

• Use a loop structure to read user input of unknown size through=20 std::cin and store it in an array.=20

• Use conditional branching to selectively perform computational = tasks.=20

• Declare (prototype) and define (implement) functions.=20

• Declare and define functions with arguments of various types, = including=20 pointers, references, const pointers, and const references.=20

• Call functions, making appropriate use of the function arguments = and their=20 types.=20

• Make decisions as to appropriate function call parameter type, = from among:=20 value, reference, const reference, pointer, and const pointer.=20

• Compile and run a C++ program in the Unix/Linux environment using=20 g++.

Operational Objectives: Create a single file named=20 stats.cpp that computes the mean and median of a sequence of = integers=20 received via standard input.

Deliverables: One file stats.cpp.

​Background

Given a finite collection of n numbers:

1. The mean is the sum of the numbers divided by n, = and=20

2. The median is the middle value (in case n is odd) = or the=20 average of the two middle values (in case n is even). =

Note that to find the median of a collection of data, it is = convenient to=20 first sort the data, that is, put the data in increasing (or=20 non-decreasing) order. Then the median is just the middle datum in the = sorted=20 sequence (or the average of the two middle data, if there are an even = number).=20

One of the simplest sort algorithms is called Selection = Sort, which=20 operates on an array of elements and has a computation which can be = described in=20 one sentence: For each element of the array, find the smallest = element with=20 equal or higher index in the array and swap these two elements. Here = is a=20 “pseudocode” description of the algorithm:

for i in [0...n)       // for each element of array A
  k =3D i                // find the smallest element following it
  for j in [i+1...n)
    if A[j] < A[k]
      k =3D j
    endif
  endfor               // now A[k] is the smallest element following =
A[i]
  swap the values in A[i] and A[k]
endfor

(You could test whether A[k] < A[i] before the swap, but = it is=20 not clear this would speed up the process – swapping may be faster than=20 testing.)

​Procedural Requirements:

1. Create and work within a separate subdirectory = cop3330/hw2. Review=20 the COP 3330 rules found in Introduction/Work Rules.

2. Turn in one file stats.cpp using the hw2submit.sh = submit=20 script.

Warning: Submit scripts do not work on the = program and=20 linprog servers. Use shell.cs.fsu.edu to submit = projects. If=20 you do not receive the second confirmation with the contents of your = project,=20 there has been a malfunction.

​Technical Requirements and Specifications

1. The project should compile error- and warning-free on = linprog with=20 the command g++ -ostats.x -Wall -Wextra stats.cpp.

2. The number of integers input by the user is not known in advance, = except=20 that it will not exceed 100. Numbers are input through standard input, = either=20 from keyboard or file re-direct. The program should read numbers until = a=20 non-digit or end-of-file is encountered or 100 numbers have been read. =

3. Once the input numbers have been read, the program should calculate = the=20 mean and median and then report these values to standard output.

4. The source code should be structured and organized as follows:=20

   1. Implement separate functions with the following prototypes: =

float Mean   (const int* a, size_t size); // calculates mean of =
data in a
float Median (int* a, size_t size);       // calculates median of data =
in a
void  Swap   (int& x, int& y);            // interchanges values =
of x and y
void  Sort   (int* a, size_t size);       // sorts the data in a

1. 2. I/O is handled by function main(); no other functions = should do=20 any I/O=20

   3. Function main() calls Mean() and = Median()=20

   4. Function Median() calls Sort()=20

   5. Function Sort() calls Swap()

2. The Sort() function should implement the Selection Sort = algorithm.=20

3. When in doubt, your program should behave like the distributed = executable=20 examples in stats_i.x and stats_s.x in = area51.=20 Identical behavior is not required, but the general I/O behavior = should be the=20 same. In particular, the data input loop should not be interupted by = prompts=20 for a next datum – this will make file redirect cumbersome. Just ask = for the=20 data one time, then read until a non-digit or end of file is = encountered.=20

​Hints

• Sample executables are distributed in [LIB]/area51. These = are=20 named stats_i.x and stats_s.x. The suffixes indicate = which=20 of the two architectures the executable is compiled on: *_i.x = runs on=20 Intel/Linux and *_s.x runs on Sun/Unix.=20

• To run a sample executable, follow these steps: (1) Decide which=20 architecture you want to use. The program machines are 32-bit = Sun=20 architecture running Sun’s version of Unix, and the linprog = machines=20 are Intel 64-bit architecture running Linux. (2) Copy the appropriate=20 executable into your space where you want to run it. For example, if = you are=20 logged in to program enter the command “cp = [LIB]/area51/stats_s.x=20 .“. (3) Change permissions to executable: “chmod 700 = stats_s.x“.=20 (4) Execute by entering the name of the executable. If you want to run = it on a=20 data file “data1“, use input redirect as in: “stats_s.x = <=20 data1“. If you want the output to go to another file, use output=20 redirect: “stats_s.x < data1 > data1.out“.=20

• Two test files are distributed in [LIB]/hw2. To run the = sample=20 executable on a file, say data1, first make sure you have an=20 executable copy of the program and the data file, then enter the=20 command:
  stats.x < = data1
  This=20 is a Unix/Linux operation that redirects the contents of = data1 into=20 standard input for stats.x. Using > redirects program = output. For=20 example, the command:
  stats.x = < data1=20 > data1.out
  sends the contents of data1 to = standard input=20 and then sends the program output into the file data1.out. = These are=20 very handy operations for testing programs.=20

• Note that the array in which input is stored is passed to the = functions as=20 a pointer. In the case of Mean(), this pointer is = const,=20 indicating that the elements of the array may not be changed by the = call.=20 However in the case of Median(), the array element values are = allowed=20 to change. These values are in fact changed by the call to = Sort().=20

• The function Sort() operates on the array input as a = pointer.=20 When the function returns, the values of the array should be in = increasing=20 order.=20

• The selection sort algorithm requires a nested pair of = for loops=20 (one inside the other).=20

• The function Swap() encapsulates the chore of swapping = two=20 values. Your sort implementation should call Swap whever two = values=20 need to be swapped. Note that the two parameters for Swap are = passed=20 by reference, so that the function acts on the values in the = calling=20 routine.=20

• Sorting the data is essential to calculate the median: when in an = array=20 that is sorted, the middle (two) values are those contained in the = middle=20 (two) indices of the array.=20

• The middle index of an array of n elements, when = n is=20 odd, is [(n-1)/2]. The middle two indices, when n is = even,=20 are [n/2 - 1] and [n/2].=20

• Be careful when subtracting 1 from an unsigned integer type such = as=20 size_t.=20

• Look at the code examples in