CSCI 2610 Lecture 3 Notes

Remark

I am covering the basics fairly swiftly here so that you can begin writing programs in the right way. We will slow down and look at this material in more detail shortly. This lecture hits the high points.

The main program

When your program starts, it runs the function called main. Note that the case of letters matters. All letters must be lower case. Don't call it Main.

The main function returns an integer. The integer returned is a status value that is sent back to the operating system. Status 0 means that all went well. A nonzero status indicates that an error occurred.

Typically, the main program looks like this. 

    int main()
    {
      Your main program body
      return 0;
    }

Here is an example of a main program. It reads a number n from the user and prints a table of the squares from 1 to n. It uses manipulator setw to set the number of characters to use for each number. To use them, you must include <iomanip.h>. 

    int main()
    {
      int n,k;
      cin >> n;
      k = 1;
      while(k <= n) {
        cout << setw(4) << k << setw(9) << k*k << endl;
      }
      return 0;
    }

Basics of functions

A function can be thought of as a box that is given some inputs and receives some outputs. The inputs are given to it not by the user sitting at the keyboard but by another part of the program. Inputs are called parameters. For example, the sqrt function takes in a number, and produces out the square root of that number.

You write a simple function like this. 

    return-type name (parameters)
    {
      computational instructions
      return return-value;
    }
The return-type is the type of the result. For example, the return-type of the sqrt function is double. The name is the name of the function. Each parameter in the parameter list consists of a type and a name for the parameter, in that order. If there are two or more parameters, they are separated by commas.

For example, here is a function that takes in a real number (type double) and returns the square of that real number. If it is given 5.0, it returns 25.0. 

    double sqr(double x)
    {
      return x*x;
    }

Here is a function that returns the maximum of two integers. 

    int max(int a, int b)
    {
      int result;
      if(a > b) {
        result = a;
      }
      else {
        result = b;
      }
      return result;
    }

The maximum finding function can be written in a shorter form. Here it is. 

    int max(int a, int b)
    {
      if(a > b) return a;
      else return b;
    }

Loop design

The while loop is the most basic looping construct in C++. It is used to do repetitive actions. To master the use of while loops, you need to understand how to think about what a loop is doing. There are two common ways to do that.

  1. Action-oriented loop design has the programmer concentrate on the actions that the loop performs.

  2. Data-oriented loop design has the programmer concentrate on the values that the loop computes.
Here is an example of a problem that can be solved by a loop, with two solutions, one based on action-oriented design and the other based on data-oriented design.

An action-oriented design example

The problem is to compute 1 + 2 + 3 + ... + n, where n is given to you by somebody else. Think about the process as follows. To compute s = 1 + 2 + ... + n, we can start with s = 0. Then successively add 1 to s, add 2 to s, ..., add n to s. The actions to be performed in the loop are

Add 1 to s
Add 2 to s
Add 3 to s
...
Add n to s

There is a problem with this. A while loop will do one thing over and over. But the lines that we have so far keep changing; no two of them are exactly the same. There first says to add 1 to s, the second says to add 2 to s, etc. We need a variable to hold the value to be added. Let's call that variable k. We will set k = 1 initially. Then the actions to be performed are

Add k to s
Add 1 to k
Add k to s
Add 1 to k
Add k to s
Add 1 to k
...
Add k to s (where k is n at this line)
Add 1 to k

Now we see exactly the same thing over and over. We just repeat

Add k to s
Add 1 to k
over and over. As long as k <= n, we want to do this. Here is a completed function addup(n) that computes 1 + 2 + ... + n. 
    int addup(int n)
    {
      int k,s;
      s = 0;
      k = 1;
      while(k <= n) {
        s = s + k;
        k = k + 1;
      }
      return s;
    }

A data-oriented design example

Now let's solve the same problem in a different way. Instead of thinking primarily about the actions to be performed, we think about the values to be computed. When we compute 0 + 1 + 2 + 3 + ... + n, we compute more and more of the sum. We can start with 0, then 0 + 1, then 0 + 1 + 2, then 0 + 1 + 2 + 3, and so on, until we have the entire value 0 + 1 + 2 + ... + n.

To see what is going on, we make a table showing two variables. One variable holds the partial sum, and the other tells how much of the sum we have.

k    s
0    0
1    1   (= 0 + 1)
2    3   (= 0 + 1 + 2)
3    6   (= 0 + 1 + 2 + 3)
4    10   (= 0 + 1 + 2 + 3 + 4)
...
n    0 + 1 + 2 + 3 + ... + n

Now we are ready to think about writing the loop. Clearly, we need two variables, k and s. Each should have initial value 0 (given by the first line of the table). The loop should stop when k == n, so it should only keep going as long as k != n.

What about updating the values of k and n, going from one line to the next? To get from

k    s
2    3   (= 0 + 1 + 2)
to
k    s
3    6   (= 0 + 1 + 2 + 3)
we clearly add 1 to k (making it 3) and then add the updated value (3) of k to s. This will work to get from any line to the next line. The function definition looks like this. 
    int addup(int n)
    {
      int k,s;
      k = 0;
      s = 0;
      while(k != n) {
        k = k + 1;
        s = s + k;
      }
    }

Loop invariants

Notice that, for every line in the table for computing 1 + 2 + ... + n, the following assertion is true.
s = 1 + 2 + ... + k
For example, when s = 3 and k = 2, the assertion is true. When s = 10 and k = 4 the assertion is true. No matter what line of the table you choose, the assertion is true. Since this assertion is true at every line, it is invariantly true. It is therefore called a loop invariant.

A loop invariant is a kind of assertion. We will use a special, technical definition of the word assertion. An assertion is a statement that is true or false, and is based solely on the current values of variables. Think of taking a snapshot of the variables at a certain point in the program. An assertion can only talk about what is seen in the snapshot. It cannot talk about what happened before or after the snapshot. For example, if i and j are variables, then

i > j
is an assertion, since whether it is true or false depends only on the current values of i and j. On the other hand,
1 has been added to i
is not an assertion, since this statement is trying to relate the current value of i to a former value of i.

When you try to write a loop invariant, make sure that your loop invariant is an assertion.

Synopsis

The two loop design methods yielded slightly different definitions of function addup. Both work. We just used a different way of thinking to get them.

In some situations, action-oriented loop design is simple and natural. If you see how to solve a problem using action-oriented design, use that. In more complex situations, you can find it difficult to think of the actions to perform. In those cases, switch to data-oriented loop design. It will often lead you in the right direction.

Experience by professional programmers has shown that data-oriented loop design combined with loop invariants is more reliable, and tends to lead to correct programs more often than action-oriented design.