Daily Archives: July 15, 2014

C++, Maths, Programming

Accelerated C++ Solution to Exercise 3-1

3 Comments

Exercise 3-1

Suppose we wish to find the median of a collection of values. Assume that the we have read some values so far, and that we have no idea how many values remain to be read. Prove that we cannot afford to discard any of the values that we have read. Hint: One proof strategy is to assume that we can discard a value, and then find values for the unread–and therefore unknown–part of our collection that would cause the median to be the value that we discarded.

Solution

I must admit that I find this question very difficult to understand. When I first read it I wasn’t sure whether it is meant to be a very simple and straight forward question, or some kind of trick question which has a definite answer.

I decided to google this and found this very interesting forum on this topic (including some comments from the original author A.Koenig!). After spending an hour going through the thread I decided the question and answer might get a bit too mathematical / theatrical, which I am not prepared to spend my next hours or days researching it. For this reason, I will stick to my motto KISS – Keep It Simple and Stupid. i.e. I will just give a couple of examples showing that, the true median value of a full set “without discarding” may be different to the (distorted) median of the same full set “with discarding“. Hence demonstrating why we cannot afford to discard any numbers.

Example 1

Assume we have read the numbers 1, 2, 3, 4 so far, and imagine that the next number is 5.

Scenario The eventual “full set” The Median Observation
No Discarding 1, 2, 3, 4, 5 3 True median
We discard 1  2, 3, 4, 5 3.5 Larger than true median
We discard 2 1, 3, 4, 5 3.5 Larger than true median
We discard 3 1, 2, 4, 5 3 Identical to true median
We discard 4 1, 2, 3, 5 2.5 Smaller than true median

Example 2

Assume we have read the numbers 1, 2, 3, 4 so far, and imagine that the next number is 5, 6.

Scenario The eventual “full set” The Median Observation
No Discarding 1, 2, 3, 4, 5, 6 3.5 True median
We discard 1 2, 3, 4, 5, 6 4 Larger than true median
We discard 2 1, 3, 4, 5, 6 4 Larger than true median
We discard 3 1, 2, 4, 5, 6 4 Larger than true median
We discard 4 1, 2, 3, 5, 6 3 Smaller than true median

Conclusion

The two examples above have demonstrated that we cannot afford to discard any numbers from the number set, should we wish to identify the true median. By discarding any numbers from the (read) set, we essentially distort the median.

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000
C++, Programming

Accelerated C++ Solution to Exercise 3-0

Exercise 3-0

Compile, execute, and test the programs in this chapter.

Solution

There are two programs in this chapter. Both computes the overall student’s grade. The only difference resides on the algorithm used – one uses average homework grades, and the other one uses median homework grades.

Program 1 algorithm uses average homework grades

OverallGrade = (0.2 * midterm) + (0.4 * final) + (0.4 * sum / count)

Program 2 algorithm uses median homework grades.

OverallGrade = (0.2 * midterm) + (0.4 * final) + (0.4 * median)

The two programs are fully documented in chapter 3 of the book. The aim of this post is purely to test run these programs to ensure that they run as expected.

These are the two programs:

Program 1 (uses average homework grades)

#include <iomanip>
#include <ios>
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::string;
using std::streamsize;

int main()
{
    // ask for and read the student's name
    cout << "Please enter your first name: ";
    string name;
    cin >> name;
    cout << "Hello, " << name << "!" << endl;

    // ask for and read the midterm and final grades
    cout << "Please enter your midterm and final exam grades: ";
    double midterm, final;
    cin >> midterm >> final;

    // ask for the homework grades
    cout << "Enter all your homework grades, "
            "followed by end-of-file: ";

    // the number and sum of grades read so far
    int count = 0 ;
    double sum = 0.0;

    // a variable into which to read
    double x;

    // invariant:
    //    we have read count grades so far, and
    //    sum is the sum of the first count grades
    //    after entering the last value, hit the F6 button, then enter (to indicate end of file)
    //    or hit Ctrl+z, then enter.
    while (cin >> x)
    {
        ++count;
        sum += x;
    }

    double dummy = count; // for some reason the code fails unless I add this line.

    // write the result
    streamsize prec = cout.precision();

     cout << "Your final grade is " << setprecision(3)
         << 0.2 * midterm + 0.4 * final + 0.4 * sum / count
         << setprecision(prec) << endl;

    return 0;
}

Note that I added this line after the while loop:

    double dummy = count; // for some reason the code fails unless I add this line.

For some unknown reason, by not including this line here, the code generate this toxic error following compilation:

Process returned 1968961623 (0x755BF857)

After I have added that “dummy” line to the code it then runs fine. I have no idea why though! (I run this via the Code::Block IDE on a Window Vista machine)

I will publish the test result at the Result section at the bottom of the post.

Program 2 (uses median homework grades)

#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::sort;
using std::streamsize;
using std::string;
using std::vector;

int main()
{
    // ask for and read the student's name
    cout << "Please enter your first name: ";
    string name;
    cin >> name;
    cout << "Hello, " << name << "!" << endl;

    // ask for and read the midterm and final grades
    cout << "Please enter your midterm and final exam grades: ";
    double midterm, final;
    cin >> midterm >> final;

    // ask for the homework grades
    cout << "Enter all your homework grades, "
            "followed by end-of-file: ";

    vector<double> homework;
    double x;

    // invariant: homework contains all the homework grades read so far
    while (cin >> x)
        homework.push_back(x);

    // check that the student entered some homework grades
    typedef vector<double>::size_type vec_sz;
    vec_sz size = homework.size();
    if (size == 0)
    {
        cout << endl << "You must enter your grades. "
                        "Please try again." << endl;
        return 1;
    }

    // sort the grades
    sort(homework.begin(), homework.end());

    // compute the median homework grade
    vec_sz mid = size/2;
    double median;
    median = size % 2 == 0 ? (homework[mid] + homework[mid-1]) / 2
                           : homework[mid];

    // compute write the final grade
    streamsize prec = cout.precision();
    cout << "Your final grade is " << setprecision(3)
         << 0.2 * midterm + 0.4 * final + 0.4 * median
         << setprecision(prec) << endl;

    return 0;
}

This program compile and execute ok.

Note that the end-of-file key is Ctrl-Z (or F6) for windows, and Ctrl-D for Linux / Unix. (or google for the answer!).

i.e. after typing the last number and hit enter, hit the end-of-file key followed by another enter – that will indicate end-of-file.

Result

I will now run 4 tests and compare results with Excel.

Even number of homework grades Odd number of homework grades
Program 1 (uses average homework grades) Test 1-even Test 1-odd
Program 2 (uses median homework grades) Test 2-even Test 2-odd

These are the test values I will be using, along with the average and median figures computed in Excel.

Even number of homework grades Odd number of homework grades
Midterm Grade 70 70
Final Grade 80 80
Homework Grades 2.00 2.00
  5.00 5.00
  30.00 30.20
  40.66 45.50
  50.00 66.66
  60.00
Average Homework Grade 58.51 (Compare with Test 1-even) 57.97 (Compare with Test 1-odd)
Median Homework Grade 60.13 (Compare with Test 2-even 58.20 (Compare with Test 2-odd)

Test 1-even Result

Please enter your first name: Johnny
Hello, Johnny!
Please enter your midterm and final exam grades: 70.00
80.00
Enter all your homework grades, followed by end-of-file: 2.00
5.00
30.00
40.66
50.00
60.00
^Z
Your final grade is 58.5

The result agrees with Excel (58.51) up to 3 significant figure.

Test 1-odd Result

Please enter your first name: Johnny
Hello, Johnny!
Please enter your midterm and final exam grades: 70.00
80.00
Enter all your homework grades, followed by end-of-file: 2.00
5.00
30.50
45.50
66.66
^Z
Your final grade is 58

The result agrees with Excel (57.97) up to 3 significant figure.

Test 2-even Result

Please enter your first name: Johnny
Hello, Johnny!
Please enter your midterm and final exam grades: 70.00
80.00
Enter all your homework grades, followed by end-of-file: 2.00
5.00
30.00
40.66
50.00
60.00
^Z
Your final grade is 60.1

The result agrees with Excel (60.13) up to 3 significant figure.

Test 2-odd Result

Please enter your first name: Johnny
Hello, Johnny!
Please enter your midterm and final exam grades: 70.00
80.00
Enter all your homework grades, followed by end-of-file: 2.00
5.00
30.50
45.50
66.66
^Z
Your final grade is 58.2

The result agrees with Excel (58.20) up to 3 significant figure.

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000