All posts by Johnny

Accelerated C++ Solution to Exercise 3-4

Exercise 3-4

Write a program to report the length of the longest and shortest string in its input.

Solution

I notice that the solution to this problem will be somewhat similar to the Solution to Exercise 3-3 (identify number of distinct elements in a vector). Except this time we are determining the length of the longest and shortest (string) elements. I therefore expect the eventual program to be similar.

Strategy

  • Ask user to provide the list of words so we can append the string elements to a vector, v.
  • Compute the size of vector, N.
  • If vector size is 0, output an error message (as we need at least 1 string). Exit program peacefully with return code 1.
  • If vector size is 1, we compute the size of the string element v[0]. The length of the longest string, SL, will be the same as the length of the shortest string, SS.
  • If vector size is 2 or above, we apply an algorithm to compute SL and SS (to be explained further below).

Algorithm

The algorithm (for the case of vector size of 2 or above) is described as followings:

  • Notice that this time we do not need to sort the vector – the condition checks downstream will be sufficient to update SS and SL.
  • We initialise SL and SS to the size of the first string element v[0]. SL and SS will be updated accordingly during the comparison step.
  • We initialise the index B to 1. This will be used for comparing the length of the v[B] with respect to SS and SL.
  • We perform N-1 number of comparisons between v[B] and the current SL and SS. (e.g. if there are 10 elements, we can only compare 9 sets of adjacent elements).
  • During each comparison step, if v[B].size() is larger than SL, we re-assign SL to v[B].size().
  • If v[B].size() is smaller than SS, we re-assign SS to v[B].size().
  • (If the two element lengths are equal, we do nothing.)
  • We then increment the indices B by 1 for the next comparisons.
  • We display the final value of SS and SL – these are the lengths of the shortest and longest strings elements within the vector v.

The Program

Putting this all together, we have our full program.

#include <iostream>
#include <string>
#include <vector>

using std::cin;             // <iostream>
using std::cout;            // <iostream>
using std::endl;            // <iostream>
using std::string;          // <string>
using std::vector;          // <string>

int main()
{
    // display header message
    cout << "***************************************************************\n"
            "*** This program reports the longest and shortest strings   ***\n"
            "***************************************************************\n";
    cout << endl;

    // ask for a list of numbers and store the list as a vector
    cout << "Enter a list of words one by one: ";
    vector<string> v;
    string x;
    while (cin >> x)
        v.push_back(x);    // append new input to the vector

    cout << endl;

    // define and compute core vector variables
    typedef vector<string>::size_type vecSize;   // define a type for vector size related variables
    vecSize N = v.size();            // number of elements in the vector
    vecSize numLoops = N - 1;        // number of (comparison) operators required

    typedef string::size_type strSize;   // define a type for string size related variables
    strSize SL;              // the length of the longest word
    strSize SS;              // the length of the shortest word

    // Check vector size, action accordingly
    if (N ==0 )
    {
        cout << "You need to enter at least 1 word! " << endl;
        return 1;
    }

    else if (N ==1 )
    {
        SL = v[0].size();
        cout << "Only 1 string supplied. The length of string = " << SL << endl;
        return 0;
    }

    else
    {
        // display some results to console window
        cout << "Vector size (number of words entered): " << N << endl;
        cout << endl;

        // declare new variables
        vecSize A = 0;     // vector index
        vecSize B = 1;     // vector index
        SS = v[0].size();            // the length of the shortest word
        SL = v[0].size();            // the length of the longest word

        // Loop through the vector, compute ND, and compute SS and SL
        for (vecSize i = 0; i != numLoops; ++i)
        {
            if (v[B].size() > SL)
            {
                SL = v[B].size();
            }
            if (v[B].size() < SS)
            {
                SS = v[B].size();
            }
            ++B;
        }
        // Display final results
        cout << endl;
        cout << "Length of shortest word: " << SS << endl;
        cout << "Length of longest word: " << SL << endl;
    }
    return 0;
}

Result

Below shows the results of the 3 sets of test:

  • N = 0
  • N=1
  • N>=2

The results appear to agree well with the algorithm used.

N = 0

***************************************************************
*** This program reports the longest and shortest strings   ***
***************************************************************

Enter a list of words one by one: ^Z

You need to enter at least 1 word!

Process returned 1 (0x1)   execution time : 3.156 s

N = 1

***************************************************************
*** This program reports the longest and shortest strings   ***
***************************************************************

Enter a list of words one by one: a23456789
^Z

Only 1 string supplied. The length of string = 9

N >= 2

***************************************************************
*** This program reports the longest and shortest strings   ***
***************************************************************

Enter a list of words one by one: a23456789
a23456
a2345b
a234
a234567890
^Z

Vector size (number of words entered): 5


Length of shortest word: 4
Length of longest word: 10

Reference

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

Accelerated C++ Solution to Exercise 3-3

Exercise 3-3

Write a program to count how many times each distinct word appears in its output.

Solution


Note: Viktor has kindly pointed out the fact that I have mis-read the question as “How many distinct words are there” (instead of how many times each distinct word appears). The solution below therefore, does not actually under the question above!!! (If I have time I may redo the question – otherwise please just ignore my solution below!!!)


My solution is a result of combining the knowledge gained from Solution to Exercise 2-8 (on recursive operations between element v[i] and v[i+1]) and Solution to Exercise 3-2 (on manipulating vector).

The solution strategy:

  • Ask user to provide the list of words so we can append the string elements to a vector, v.
  • Compute the size of vector, N.
  • If vector size is 0, the number of distinct words is also 0.
  • If vector size is 1, the number of distinct words is also 1.
  • If vector size is 2 or above, we apply an algorithm to identify and count the distinct words. (To be explained further below).

The algorithm (for the case of vector size of 2 or above) is described as followings:

  1. We sort the vector v in non-descending order.
  2. We initialise the index A to 0, and index B to 1. These indices will be used for comparing adjacent elements within the vector (to check for distinctive elements).
  3. We also initialise the distinct element count figure ND to 1 – we know that we have at least 1 distinct word.
  4. We perform N-1 number of comparisons between the adjacent elements v[A] and v[B]. (e.g. if there are 10 elements, we can only compare 9 sets of adjacent elements).
  5. During each comparison step, if v[B] is not the same as v[A], it implies that v[B] is a newly discovered distinct word. We increment ND.
  6. Note: if v[B] is the same as v[A], it implies v[B] is a repeated word. We do nothing in that case, as we are only interested in discovering new distinct words.
  7. We then increment the indices A and B by 1 for the next comparisons. i.e. we first compare v[0] and v[1], then v[1] and v[2], then v[2] and v[3], etc…
  8. We display the final value of ND – this is the number of distinct words computed.

Putting this all together, we have our full program.

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

using std::cin;             // <iostream>
using std::cout;            // <iostream>
using std::endl;            // <iostream>
using std::sort;            // <algorithm>
using std::string;          // <string>
using std::vector;          // <string>

int main()
{
    // display header message
    cout << "***************************************************************\n"
            "*** This program computes number of unique words            ***\n"
            "***************************************************************\n";
    cout << endl;

    // ask for a list of numbers and store the list as a vector
    cout << "Enter a list of words one by one: ";
    vector<string> v;
    string x;
    while (cin >> x)
        v.push_back(x);    // append new input to the vector

    cout << endl;

    // define and compute core vector variables
    typedef vector<string>::size_type vecSize;   // define a type for vector size related variables
    vecSize N = v.size();            // number of elements in the vector
    vecSize numLoops = N - 1;        // number of (comparison) operators required
    vecSize ND;                      // number of distinct words

    // Check vector size, action accordingly
    if (N ==0 )
    {
        ND = 0;
        cout << "Number of distinct words = " << ND << endl;
        return 0;
    }

    else if (N ==1 )
    {
        ND = 1;
        cout << "Number of distinct words = " << ND << endl;
        return 0;
    }

    else
    {
        // sort the vector;
        sort(v.begin(),v.end());

        // display some results to console window
        cout << "Vector size (number of words entered): " << N << endl;
        cout << endl;
        cout << "Display the sorted (non-descending) distinct words below." << endl;
        cout << v[0] << endl;

        // declare new variables
        vecSize A = 0;     // vector index
        vecSize B = 1;     // vector index
        ND = 1;            // number of distinct words

        // Loop through the vector, compute ND, and identify the distinct words
        for (vecSize i = 0; i != numLoops; ++i)
        {
            if (v[B] != v[A])
            {
                ++ND;
                cout << v[B] << endl;  // display any newly discovered distinct words
            }
            ++A;
            ++B;
        }
        // Display final distinct word count
        cout << endl;
        cout << "Number of distinct elements (words): " << ND << endl;
    }
    return 0;

}

Result

Below shows the results of the 3 sets of test:

  • N = 0
  • N=1
  • N>=2

The results also reveal that fact that the sorting elements of a vector is case-sensitive. e.g. the string John (beginning with upper case) is different to john (all lower case).

N = 0

***************************************************************
*** This program computes number of unique words            ***
***************************************************************

Enter a list of words one by one: ^Z

Number of distinct words = 0

N = 1

***************************************************************
*** This program computes number of unique words            ***
***************************************************************

Enter a list of words one by one: Johnny
^Z

Number of distinct words = 1

N >= 2

*** This program computes number of unique words            ***
***************************************************************

Enter a list of words one by one: john
peter
pete
johnny
john
John
^Z

Vector size (number of words entered): 6

Display the sorted (non-descending) distinct words below.
John
john
johnny
pete
peter

Number of distinct elements (words): 5

Reference

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

Accelerated C++ Solution to Exercise 3-2

Exercise 3-2

Write a program to compute and print the quartiles (that is, the quarter of the numbers with the largest values, the next highest quarter, and so on) of a set of integers.

Solution

According to this Wikipedia page, for discrete distributions, there is no universal agreement on selecting the quartiles values – there are 3 major computing methods.

I will apply Method 1 in my solution which has the following definitions:

  1. Use the median to divide the ordered data set into two halves. Do not include the median in either half.
  2. The lower quartile value is the median of the lower half of the data. The upper quartile value is the median of the upper half of the data.

This rule is employed by the TI-83 calculator boxplot and “1-Var Stats” functions (according to Wikipedia)

It is also very important to note that there are two types of medians:

  • Datum median – the middle data point of an ordered vector.
  • Non-datum median – the mean of the middle two data points of an ordered dataset.

Datum vs Non-datum

The computation of the lower quartile, median, and upper quartile can be either a datum or non-datum. It depends on the dataset dataset pattern which I shall expand on more shortly.

The 6 distinctive dataset patterns

After  3 hours of sketching and iterations, I am pleased to say that I have found “the dataset pattern” which I believe is consistent for all types of input datasets, and robust to implement. I summarise this pattern in the following table:

ID Pattern Condition  Quartiles (Q1, Q2, Q3)
1 NULL dataset N = 0 (Cannot compute)
2 1 Number only N = 1 Quartiles all resolve to that 1 number provided.
3 Datum Profile [0 0 0] N % 4 == 0 Datum Profile 000
4 Datum Profile [0 1 0] N % 4 == 1 Datum Profile 010
5 Datum Profile [1 0 1] N % 4 == 2   Datum Profile 101
6 Datum Profile [1 1 1] N % 4 == 3  Datum Profile 111

Note

  • I use Q1, Q2, and Q3 to denote Quartile 1, 2, and 3. (i.e. end of quarter 1, 2, and 3)
  • If the dataset is empty (Null), it is not possible to compute the quartiles for that dataset.
  • If the dataset contains only 1 number, it is quite natural to assume that there is no variation (or no range). i.e. all quartiles correspond to that number.
  • If there are at least 2 numbers provided, the pattern is determined by the Datum Profile [Q1 Q2 Q3]. There are four possible types of Datum Profiles: [0 0 0], [0 1 0], [1 0 1], and [1 1 1].
  • For example, a datum profile of [1 0 1] means: lower quartile is a datum, median is a non-datum, upper quartile is a datum. i.e. 1 represents datum. 0 represents non-datum.
  • N is the total number of elements within the dataset.
  • The % (percent) sign is used to compute remainder. e.g. N % 4 gives the remainder of N divided by 4.

Nomenclature

I use the following short-form letters to make the formula easier to understand, and program easier to code.

Symbol Meaning
v Represents the vector. e.g. v[M] resolves the value of the element locating at index M of the vector v.
N Number of elements of the vector (i.e. the input dataset)
ML An index value for computing the lower quartile. (Think Median of the Lower-halve).
M An index value for computing the median.
MU An index value for computing the upper quartile. (Think Median of the Upper-halve).
ml The computed value of lower quartile.
m The computed value of median
mu The computed value of upper quartile.

Solution Strategy

At a high level, this is what the program should do:

  • Read the list of numbers from the user and store in a vector.
  • Pattern 1: If vector contains no elements (i.e. NULL), output an error message (mentioning the program requires at least 1 number to compute quartiles), then exit the program peacefully.
  • Pattern 2: If vector contains just 1 number, output a message saying that all quartiles values are the same as that number provided, then exit the program peacefully.
  • Sort the vector so it become non-descending – this is required for the median computation.
  • Determine whether the dataset belongs to pattern 3, 4, 5, or 6, execute the corresponding algorithms, display the quartile summary at the end.

Before walking through this solution strategy I think it is worth expand a bit more on how I derive the algorithms for pattern 3, 4, 5, and 6 in the first place.

Derivation of Algorithms

Pattern 1 (null dataset) and patter 2 (1 number only) are very straight forward and have already been explained above. So I’m not going to expand further on these first two patterns.

Pattern 3, 4, 5 and 6, however, are much more interesting in comparison. These patterns require a bit more intelligence to solve – so I will focus on these one-by-one and summarise this at the end.

 The Repeating Cycles

The first thing that I did in terms of trying to spot a pattern was to sketch out around a number vectors with sizes ranging from N=2 to N=11 (could have been more but the patter had become quite obvious at that point!), circle out the datum profile, and hope to see some sort of pattern. Through the exercise I observed that the datum profile changes every time I increase N by 1. I also observed the profile change follows a cycle of 4 increments. e.g. the profile is the same at N=2, N=6, N=10, etc…. The following table is that “sketch” that I produced which led me to the discovery of algorithms.

N N % 4  Profile Sketch
2  2  [101] Acpp3p2N2
3 3  [111] Acpp3p2N3
4  0  [000] Acpp3p2N4
5 1  [010] Acpp3p2N5
6 2  [101] Acpp3p2N6
7 3  [111] Acpp3p2N7
8 0  [000] Acpp3p2N8
9 1  [010]  Acpp3p2N9
 10 2  [101]  Acpp3p2N10
11 3  [111]  Acpp3p2N11

The pattern can therefore be summarised as follows:

Pattern ID Datum Profile N % 4
3 [000] 0
4 [010] 1
5 [101] 2
6 [111] 3

We now have this core table, let’s derive the equations.

Equations and Examples

These diagrams summarise the equations, examples, and code implementations for each of the four datum patterns.

Profile [000] – Equations and Examples

Profile 000 Equations

Profile 000 Equations

Profile 000 Equations

Profile [010] – Equations and Examples

Profile 010 Equations

Profile 010 Equations

Acpp3p2Pic5b

Profile [101] – Equations and Examples

Acpp3p2Pic6

Acpp3p2Pic7

Acpp3p2Pic8a

Acpp3p2Pic8b

Profile [111] – Equations and Examples

Acpp3p2Pic9

Acpp3p2Pic10

Acpp3p2Pic11a

Acpp3p2Pic11b

 The Program

Now that we have our algorithms, let’s put everything together into a final program. I am purely using the skeleton program from chapter 3 of the book (which has an in-depth explanation of the various components). I merely implement the algorithms into this skeleton program, with some extra enhancements for user-friendly output.

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

using std::cin;             // <iostream>
using std::cout;            // <iostream>
using std::endl;            // <iostream>
using std::setprecision;    // <iomanip>
using std::sort;            // <algorithm>
using std::streamsize;      // <ios>
using std::string;          // <string>
using std::vector;          // <string>

int main()
{
    // display header message
    cout << "***************************************************************\n"
            "*** This program computes quartiles given a list of numbers ***\n"
            "***************************************************************\n";
    cout << endl;

    // ask for a list of numbers and store the list as a vector
    cout << "Enter all a list of numbers: ";
    vector<double> v;
    double x;
    while (cin >> x)
        v.push_back(x);

    // check vector size and action accordingly
    cout << endl;
    typedef vector<double>::size_type vecSize;
    vecSize N = v.size();
    if (N ==0 )
    {
        cout << "You must enter some numbers! " << endl;
        return 1;
    }

    else if (N ==1 )
    {
        cout << " Only 1 number supplied. Q1, Q2, and Q3 all equate to " << v[0] << endl;
        return 0;
    }

    else
    {
        // sort the homework grades;
        sort(v.begin(),v.end());
    }

    // declare new variables
    vecSize NMod4 = (N % 4);  // identification of 1 of the 4 known datum distribution profiles
    string datumDistr = "";   // datum distribution profile
    vecSize M, ML, MU;        // core vector indices for quartile computation
    double m, ml, mu;         // quartile values are store here

    // compute quartiles for the 4 known patterns
    if ( NMod4 == 0 )
    {
        // Q1-Q3 datum distribution: [0 0 0]
        datumDistr = "[0 0 0]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML;

        // grab quartile values
        ml= (v[ML] + v[ML-1]) / 2;     // datum: 0
        m = (v[M] + v[M-1]) / 2;       // datum: 0
        mu = (v[MU] + v[MU-1]) / 2;    // datum: 0
    }

    else if ( NMod4 == 1 )
    {
        // Q1-Q3 datum distribution: [0 1 0]
        datumDistr = "[0 1 0]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML + 1;

        // grab quartile values
        datumDistr = "[0 0 0]";
        ml= (v[ML] + v[ML-1]) / 2;      // datum: 0
        m = v[M];                       // datum: 1
        mu = (v[MU] + v[MU-1]) / 2;     // datum: 0
    }

    else if ( NMod4 == 2 )
    {
        // Q1-Q3 datum distribution: [1 0 1]
        datumDistr = "[1 0 1]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML;

        // grab quartile values
        ml= v[ML];                    // datum: 1
        m = (v[M] + v[M-1]) / 2;     // datum: 0
        mu = v[MU];                   // datum: 1
    }

    else if ( NMod4 == 3 )
    {
        // Q1-Q3 datum distribution: [1 1 1]
        datumDistr = "[1 1 1]";
        M = N / 2;
        ML = M / 2;
        MU = M + ML + 1;

        // grab quartile values
        ml= v[ML];                    // datum: 1
        m = v[M];                     // datum: 0
        mu = v[MU];                   // datum: 1
    }

    else
    {
        cout << "Unknown pattern discovered - new algorithm may be required.";
    }

    // Display results
    streamsize prec = cout.precision();
    cout << "Display the sorted (non-descending) vector below." << endl;
    cout << "Index: Number" << endl;
    for (vecSize i = 0; i !=  N; ++i)
    {
        cout << i << ": " << v[i] << endl;
    }
    cout << endl;
    cout << "Vector size: " << N << endl;
    cout << "Datum Distribution: " << datumDistr << endl;
    cout << setprecision(3) << endl
         << " Q1: " << ml << endl
         << " Q2: " << m << endl
         << " Q3: " << mu << endl
         << setprecision(prec);
}

Result

i’m going to run the program a number of times – each with different input dataset. (e.g. incrementing N by 1, try out the Wikipedia example and compare, etc.)

N = 0

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: ^Z

You must enter some numbers!

Process returned 1 (0x1)   execution time : 9.804 s

N = 1

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 5
^Z

 Only 1 number supplied. Q1, Q2, and Q3 all equate to 5

Process returned 0 (0x0)   execution time : 8.430 s

N = 2

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 10
20
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 10
1: 20

Vector size: 2
Datum Distribution: [1 0 1]

 Q1: 10
 Q2: 15
 Q3: 20

N = 3

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 10
20
30
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 10
1: 20
2: 30

Vector size: 3
Datum Distribution: [1 1 1]

 Q1: 10
 Q2: 20
 Q3: 30

N = 4

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 6
2
4
9
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 2
1: 4
2: 6
3: 9

Vector size: 4
Datum Distribution: [0 0 0]

 Q1: 3
 Q2: 5
 Q3: 7.5

N = 5

Enter all a list of numbers: 9
4
20
39
44
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 4
1: 9
2: 20
3: 39
4: 44

Vector size: 5
Datum Distribution: [0 0 0]

 Q1: 6.5
 Q2: 20
 Q3: 41.5

Wikipedia example (even size vector)

The results match!

**************************************************************
*** This program computes quartiles given a list of numbers **
**************************************************************

Enter all a list of numbers: 41
39
15
7
36
40
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 7
1: 15
2: 36
3: 39
4: 40
5: 41

Vector size: 6
Datum Distribution: [1 0 1]

 Q1: 15
 Q2: 37.5
 Q3: 40

Wikipedia example (odd size vector)

The results match!

***************************************************************
*** This program computes quartiles given a list of numbers ***
***************************************************************

Enter all a list of numbers: 49
43
41
39
15
6
7
36
40
42
47
^Z

Display the sorted (non-descending) vector below.
Index: Number
0: 6
1: 7
2: 15
3: 36
4: 39
5: 40
6: 41
7: 42
8: 43
9: 47
10: 49

Vector size: 11
Datum Distribution: [1 1 1]

 Q1: 15
 Q2: 40
 Q3: 43

Reference

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

Accelerated C++ Solution to Exercise 3-1

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

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

Accelerated C++ Solution to Exercise 2-10

Exercise 2-10

Explain each of the uses of std:: in the following program:

int main ()
{
    int k = 0;
    while (k != 10)   // invariant: we have written k asterisks so far
    {
        using std::cout;
        cout << "*";
        ++k;
    }
    std::cout << std::endl;   // std:: is required here
    return 0;
}

Solution

Back to basics – what are namespace, names within a namespace, standard library, and iostream header? (refer to page 3 / chapter 0.5 of the book).

  • std:: corresponds to a namespace called std.
  • A namespace (e.g. std) is a collection of related names (e.g. cout, cin, endl). The standard library uses std to contain all the names that it defines.
  • The iostream standard header defines the names (e.g. coutcinendl)

i.e. the iostream standard header defines the names coutcinendl, and we refer to these names as std::cout, std::cin, std::endl.

Now, let’s explain the uses of std:: in the program.

Within the while loop, we have using std::cout statement to declare that the name cout (residing in namespace std) is made available to the program. i.e. within the while loop scope whenever we have cout, the program “knows” that we are referring to std::cout – the cout of namespace std. The usage of std::cout statement has the life span of only within the while loop scope, as defined by the two curly braces { }. The while loop uses the std::cout to write asterisks on the console window.

Immediately after the while loop scope, we have std::cout – i.e. we need to explicitly specify that we are referring to the cout of the namespace std (and not other namespaces). std::cout is used here to write to the console window.

Lastly, we have the std::endl. Again, we need to explicitly specify that we are referring to the endl of the namespace std (and not other namespaces). std::endl is used for ending the currently line (and start a new line).

Putting this all together, the program does this:

  • Write 10 asterisks to the console output window.
  • End the current line and start a new line.

To run the program however, we must add the iostream header at the top which defines what the like of std::cout, std::endl, etc.

#include <iostream>

Result

**********

Reference

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

Accelerated C++ Solution to Exercise 2-9

Exercise 2-9

Write a program that asks the user to enter two numbers and tells the user which number is larger than the other.

Solution

Here is my solution strategy:

  • Obtain the two numbers from user. i.e. a and b.
  • Perform a condition check. There are 3 possible cases.
  • Case 1: a == b
  • Case 2: a > b
  • Case 3: a < b
  • Prepare the outcome of each case. e.g. each case can have its own output message.

Putting this together, we have our full program.

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int main()
{
    cout << "***********************************************************************\n"
         << "*** This program compare 2 numbers and tell you which one is larger ***\n"
         << "***********************************************************************\n";
    cout << endl;
    cout << "Enter the first number (a): ";
    int a;
    cin >> a;
    cout << "Enter the second number (b): ";
    int b;
    cin >> b;
    cout << "a = " << a << ", b = " << b << endl;
    if (a == b)
        {cout << "a == b";}
    else if (a > b)
        {cout << "a > b";}
    else
        {cout << "a < b";}
    return 0;
}

Result

Let’s supply 3 sets of input (representing the 3 cases) and confirm the condition check works.

Case 1: a == b

***********************************************************************
*** This program compare 2 numbers and tell you which one is larger ***
***********************************************************************

Enter the first number (a): 5
Enter the second number (b): 5
a = 5, b = 5
a == b

Case 2: a > b

***********************************************************************
*** This program compare 2 numbers and tell you which one is larger ***
***********************************************************************

Enter the first number (a): 10
Enter the second number (b): 5
a = 10, b = 5
a > b

Case 3: a < b

***********************************************************************
*** This program compare 2 numbers and tell you which one is larger ***
***********************************************************************

Enter the first number (a): 5
Enter the second number (b): 10
a = 5, b = 10
a < b

The condition check for all 3 cases work as expected.

Reference

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

Accelerated C++ Solution to Exercise 2-8

Exercise 2-8

Write a program to generate the product of the numbers in the range [1,10).

Solution

The question asks as to compute the product of the numbers within the asymmetric range [1,10). In other words, the product of numbers within the range of 1 to 10, excluding 10. i.e.

1 x 2 x 3 ... x 7 x 8 x 9

Observation: this is the same as 9 factorial (9!). This is the same logic as computing n factorial.

Here outlines my solution strategy at the top level.

Solution Strategy

Descriptions:

  • Fact: the product of 3 x 4 x 5 (ascending syntax) is the same as 5 x 4 x 3 (descending syntax). So for simplicity, we restrict ourself by only writing in an ascending syntax. i.e. use [3,6), and avoid [5,1) . This is the same as making the assumption of n >= m.
  • Fact: Case 1, if (n-m)=0, e.g. the asymmetric range is [3,3), this is equivalent of saying the range is between 3 and 3 (excluding 3). Because this range is null, the product is also null (zero). No loops required.
  • Fact: Case 2, if (n-m)=1, e.g. the asymmetric range is [3,4), this is equivalent of saying the range is between 3 and 4 (excluding 4). The range is therefore just the number 3 (i.e. m). Likewise, the product is also 3 (i.e. m). No loops required.
  • Fact: Case 3, if (n-m)>=1, e.g. the asymmetric range is [3,7), this is equivalent of saying the range is between 3 and 7 (excluding 7). i.e. we are looking for the product of 3 x 4 x 5 x 6. To compute this we must use loops. The main focus of this post is case 3.

Case 3 Solution Strategy

After spending an entire Sunday afternoon on this question, I eventually spotted a pattern which I believe is consistent and can be leveraged in the forming of our algorithm. To demonstrate this pattern, I have put together some diagrams in PowerPoint and presented as snapshot images below. For clarity, we are going to focus on this particular (arbitrary) asymmetric range as our core example: [3, 7).

Solution Strategy

 

Observations:

  • The number of elements is always (n-m). there are 4 elements in this case.
  • The number of loops required is always (n-m-1). We need 3 loops in this case. (numLoops = 3).
  • The number of loops required also equals to the number of (multiplication) operator.
  • Knowing the number of loops required enable us to form the loop invariant i [0,numLoops).

Now, let’s try and observe more patterns – what happens at each loop? (See diagram below)

Solution Strategy

Observations:

  • 4 major variables are required.
  • The integer invariant i that controls whether the loop is to go ahead or terminate.
  • The integer variable a – the lower number of the product (a x b).
  • The integer variable b – the higher number of the product (a x b).
  • The integer variable c – the product of (a x b).
  • At the beginning of the very first loop, initialise values of a and b.
  • At the end of each loop, the re-initialise values of a and b.

The final product of [m,n) is the value of c at the end of the very last loop.

For completeness, let’s do a drill down into the loops in greater depth. Bear in mind that for [3,7), the numLoops is n-m-1=3. We need 3 loops. The loop go ahead if the invariant i has not reached numLoops – it starts at 0 (zero), and get increment by 1 at end of each loop.

Invariant i = 0 (Loop)

Solution Strategy

Invariant i = 1 (Loop)

Solution Strategy

Invariant i = 2 (Loop)

Solution Strategy

Invariant i = 3 (No Loop)

Solution Strategy

At the end of the loop, output the final result. The product of the numbers within the asymmetric range [m,n) is the value of c at the end of the very last loop. The following table summarises this looping process.

Invariant i a b c
0 3 4 12
1 12 5 60
2 60 6 360

Full Program

We should now have all the fundamentals in the making of our program. This is my version of the program. (There are many ways to do this however!)

#include <iostream>
using namespace std;
int main()
{
    cout << "***********************************************************\n"
         << "*** This program computes the product of the numbers    ***\n"
         << "*** in the asymmetric range [m,n).                      ***\n"
         << "*** (Limitation: please ensure m is not larger than n)  ***\n"
         << "*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***\n"
         << "***********************************************************";
    cout << endl;

    // Ask user to supply the startNumber
    cout << "Enter m: ";
    int m;
    cin >> m;

    // Ask user to supply the endNumber
    cout << "Enter n: ";
    int n;
    cin >> n;

    // Algorithm to compute the product of numbers within the asymmetric range [m,n)
    const int startNumber = m ;
    const int endNumber = n;
    const int numElements = endNumber - startNumber;
    const int numLoops = numElements - 1;
    int c;
    if (numElements == 0)
        {c = 0;}
    else if (numElements == 1)
        {c = startNumber;}
    else
    {
        int a = startNumber;
        int b = startNumber + 1;

        cout << " i, a, b, c " << endl;
        for (int i = 0; i != numLoops; ++i)
        {
            c = a * b;
            cout << i << ", " << a << ", " << b << ", " << c << endl;
            a = c;
            ++b;
        }
    }
    cout << "Asymmetric range: [" << startNumber << "," << endNumber << ")" << endl;
    cout << "Number of elements: " << numElements << endl;
    cout << "Number of loops required: " << numLoops << endl;
    cout << "Product of numbers within the asymmetric range = " << c << endl;
    return 0;
}

Result

The program is meant to be robust and be able to deal with any asymmetric range [m,n) as long as (n>=m). Case 1-3 are mainly for prove of concepts. Case 4 is the solution to the question (find product of numbers within the range [1,10).

  • Case 1 – when (n-m)=0. e.g. [3,3)
  • Case 2 – when (n-m)=1. e.g. [3,4)
  • Case 3 – when (n-m)>1. e.g. [3,7)
  • Case 4 – when (n-m)>1. e.g. [1,10)

Case 1 – Asymmetric Range [3,3)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 3
Asymmetric range: [3,3)
Number of elements: 0
Number of loops required: 0
Product of numbers within the asymmetric range = 0

Case 2 – Asymmetric Range [3,4)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 4
Asymmetric range: [3,4)
Number of elements: 1
Number of loops required: 0
Product of numbers within the asymmetric range = 3

Case 3 – Asymmetric Range [3,7)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 7
 i, a, b, c
0, 3, 4, 12
1, 12, 5, 60
2, 60, 6, 360
Asymmetric range: [3,7)
Number of elements: 4
Number of loops required: 3
Product of numbers within the asymmetric range = 360

Case 4- Asymmetric Range [1,10)

***********************************************************
*** This program computes the product of the numbers    ***
*** in the asymmetric range [m,n).                      ***
*** (Limitation: please ensure m is not larger than n)  ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 1
Enter n: 10
 i, a, b, c
0, 1, 2, 2
1, 2, 3, 6
2, 6, 4, 24
3, 24, 5, 120
4, 120, 6, 720
5, 720, 7, 5040
6, 5040, 8, 40320
7, 40320, 9, 362880
Asymmetric range: [1,10)
Number of elements: 9
Number of loops required: 8
Product of numbers within the asymmetric range = 362880

Compute the N factorial

Note that this program may also be used as a skeleton program for computing factorial. e.g. 5! = 1 x 2 x 3 x 4 x 5. In other words, to compute n! this is effectively the same as computing the internal product of the numbers within the asymmetric range (0, n+1).

Conclusion

The product of the numbers within the asymmetric range [0,10) is 362880, as computed by the program (and verified by calculators). This program might also be used as a skeleton program for computing factorial.

Reference

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

Accelerated C++ Solution to Exercise 2-7

Exercise 2-7

Write a program that count down from 10 to -5

Solution

Though it is tempting to just create a for loop (or a while loop) with an invariant that start from 10, output the invariant, increment the invariant by -1, and exit the loop when the invariant becomes smaller than -5, I have decided to write the program in a way that is consistent with the asymmetric range method that the author has taught us. i.e. make use of the asymmetric invariant range denotation i[0,End) – meaning creating an invariant i that start with the value of zero (and always zero!), with an end number representing the number of loops that we wish the invariant to go through.

So how do we find out how many loops we need?

  • If we are to only output 10 we need 1 loop (to display 1 number). 10 – 10 + 1 = 1. i.e. we need the asymmetric range of [0,1)
  • If we need to output 10 and 9, we need 2 loops (to display 2 numbers). 10 – 9 +1 = 2. i.e. we need the asymmetric range of [0,2)
  • If we need to output 10, 9, 8, we need 3 loops (to display 3 number). 10 – 8 + 1 = 3. i.e. we need the asymmetric range of [0,3)

See the pattern?

If we need to display N numbers (counting down), we need N loops, as calculated as:

N = (( EndNumber - StartNumber ) * (-1 ) ) + 1

So if we are to display 10, 9, 8 …. -3, -4, -5, we have:

  • StartNumber = 10
  • EndNumber = -5
  • NumLoops = (( EndNumber – StartNumber ) * (-1 ) ) + 1 = ( (-5 -10) * (-1) ) + 1 = 15 + 1 = 16 loops.

Our asymmetric invariant range therefore takes this denotation: i [0, 16)

Understanding these relationships will allow us to be consistent in the way we program. This knowledge will enable us to be robust in solving a problem like this: write a program that count down from 999 to – 777. i.e. we can simply repeat the above methodology (or algorithm) without scratching our heads and get stuck!

One more question before we move on, what happen if we are counting up instead of counting down?

e.g. if we are to display -5, -4, -3, … 8, 9, 10, we have:

  • StartNumber = -5
  • EndNumber = 10
  • NumLoops = ( ( EndNumber – StartNumber ) * 1 ) + 1 = ( ( 10 – (-5) ) * 1 ) + 1 = 15 + 1 =16 loops.

If we need to display N numbers (counting up), we need N loops, as calculated as:

N = (( EndNumber - StartNumber ) * (+1 ) ) + 1

Our asymmetric invariant range still take the same denotation: i [0, 16)

The general equation for NumLoops is therefore:

NumLoops = ( (EndNumber - StartNumber) * directionFlag ) + 1
  • If counting up (i.e. EndNumber > StartNumber), the directionFlag is 1.
  • Otherwise, the directionFlag is -1.

Quite initiative really as we have a positive flag for counting up, and a negative flag for counting down.

Also note that if EndNumber == StartNumber, directionFlag becomes irrelevant because in that case the numLoops will be (0 * directionFlag) + 1, which is always 1.

The directionFlag also provides us a mean to determine whether we wish to increment the output value by +1 or -1.

The last bit is the actual counting and displaying the numbers. This is how I’d do it. (Note: there are many ways to do this!)

// Do the counting and display result row by row
for (int i = 0, iOut = startNumber; i != numLoops; ++i)
{
    std::cout << "Loop " << i << "| iOut = " << iOut << std::endl;
    iOut += directionFlag;
}

This is a for loop with i [0,numLoops) denotation. i.e. we are certain that there will be numLoops number of loops in total.

The first loop output the start value. At the end of the loop we increment the invariant by either +1 (counting up), or -1 (counting down). If the condition (i != numLoops) is true, loop again. Otherwise, the loop terminates.

The above snippet essentially isolate the invariant i component from the computed iOut component – for flexibility. In other words, the function of the invariant is to purely count the number of completed loops. We leave the computed component as free as it can be.

Putting everything together, we now have our full program:

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main()
{
    // Display greeting message
    cout << "*****************************n"
         << "*** The Counting Program ****n"
         << "*****************************n";

    // Obtain startNumber and endNumber from the user
    cout << endl;
    cout << " Enter Start Number: ";
    int inputStartNumber;
    cin  >> inputStartNumber;
    cout << " Enter End Number: ";
    int inputEndNumber;
    cin  >> inputEndNumber;

    const int startNumber = inputStartNumber;
    const int endNumber = inputEndNumber;

    // Compute the directionFlag and numLoops
    int directionFlag, numLoops;
    if (endNumber > startNumber) {directionFlag = 1;}
    else {directionFlag = -1;}

    numLoops = ( (endNumber - startNumber) * directionFlag ) + 1;

    // Display the directionFlag and numLoops
    cout << " directionFlag = " << directionFlag
         << " | numLoops = " << numLoops << endl;

    // Do the counting and display result row by row
    for (int i = 0, iOut = startNumber; i != numLoops; ++i)
    {
        std::cout << "Loop " << i << "| iOut = " << iOut << std::endl;
        iOut += directionFlag;
    }
    return 0;
}

Result

The code compile okay. Let’s run it and see what we get!

Case 1: count from 10 to -5

*****************************
*** The Counting Program ****
*****************************

 Enter Start Number: 10
 Enter End Number: -5
 directionFlag = -1 | numLoops = 16
Loop 0| iOut = 10
Loop 1| iOut = 9
Loop 2| iOut = 8
Loop 3| iOut = 7
Loop 4| iOut = 6
Loop 5| iOut = 5
Loop 6| iOut = 4
Loop 7| iOut = 3
Loop 8| iOut = 2
Loop 9| iOut = 1
Loop 10| iOut = 0
Loop 11| iOut = -1
Loop 12| iOut = -2
Loop 13| iOut = -3
Loop 14| iOut = -4
Loop 15| iOut = -5

Case 2: count from -5 to 10

*****************************
*** The Counting Program ****
*****************************

 Enter Start Number: -5
 Enter End Number: 10
 directionFlag = 1 | numLoops = 16
Loop 0| iOut = -5
Loop 1| iOut = -4
Loop 2| iOut = -3
Loop 3| iOut = -2
Loop 4| iOut = -1
Loop 5| iOut = 0
Loop 6| iOut = 1
Loop 7| iOut = 2
Loop 8| iOut = 3
Loop 9| iOut = 4
Loop 10| iOut = 5
Loop 11| iOut = 6
Loop 12| iOut = 7
Loop 13| iOut = 8
Loop 14| iOut = 9
Loop 15| iOut = 10

Case 3: count from 10 to 10

*****************************
*** The Counting Program ****
*****************************

 Enter Start Number: 10
 Enter End Number: 10
 directionFlag = -1 | numLoops = 1
Loop 0| iOut = 10

 Reference

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

Accelerated C++ Solution to Exercise 2-6

Exercise 2-6

What does the following code do?

int i = 0;
while (i < 3)
{
    i += 1;
    std::cout << i <<std::endl;
}

Solution

This is very a classic usage of while loop with the following properties:

Invariant i, with the initial integer value of zero.

int i = 0;

And asymmetric range [0,3). i.e. invariant i is incremented at a specified interval (in this case 1) from the initial value of 0 to the ending value of 3 (but excluding 3). Note the mixed use of square and round brackets (in the sense of writing in the post rather than the actual code.). We use square brackets [ ] to imply inclusiveness, and round bracket ( ) to imply exclusiveness.

while (i < 3)    // asymmetric range of [0,3)
{
    i += 1;     // invariant increment interval is 1
    std::cout << i <<std::endl;   // display the invariant to the standard output console
}

I denote this while loop as i [0,3)

Using logic, I’d expect the code to do this:

Invariant i (at top of loop) while ( i < 3) i += 1 Console Output
0 true 1 1
1 true 2 2
2 true 3 3
3 false

To confirm this let’s run the following code and output result.

#include <iostream>

int main()
{
     int i = 0;
     while (i < 3)
     {
         i += 1;
         std::cout << i <<std::endl;
         //i += 1;
     }
     return 0;
}

Result

1
2
3

The nice thing about using asymmetric range [0,N) is the ease of understanding. i.e. The invariant is true for N number of loops.

Extras

Say now if we modify the code so that the invariant increment happens at the bottom. i.e.

int i = 0;
while (i < 3) {
    std::cout << i <<std::endl;
    i += 1;
}

Our result should now look like this:

Invariant i (at top of loop) while ( i < 3) Console Output i +=1
0 true 0 1
1 true 1 2
2 true 2 3
3 false

We run the modified code and it confirms our expectation:

0
1
2

Reference

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