CSC 180
Notes for Tutorial #8

Wednesday 6 November  
Monday 11  November  

 Examples using arrays of numerical values
==========================================

example:  

In this exercise you are to develop a pseudo-code and then a C code 
implementation of the Sieve of Eratosthenes algorithm for computing
prime numbes.

Here is a description of the algorithm:
  (taken from Eric Roberts, The Art and Science of C)

<TAs: Please demonstrate the algorithm for them >

The Sieve of Eratosthenes

In the third century B.C.,  the Greek astronomer Eratosthenes developed
an algorithm for finding all the prime numbers up to some upper limit n.
To apply the algorithm, you start by writing down a list of integers
between 2 and n.  For example, if n were 20, you would begin by writing
down the following list:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

You then begin by circling the first number in the list, indicating that
you have found a prime.  You then go through the rest of the list and cross
off every multiple of the value that you have just circled, since none of
the multiples can be prime.  Thus, after executing the first step of the
algorithm, you will have circled the number 2 and crossed off every multiple
of two, as follows:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 o   x   x   x   x     x     x     x     x     x

From here, you simply repeat the process by circling the first number
in the list that is neither crossed off nor circled, and then crossing 
off its multiples.  In this example, you would circle 3 as prime and
cross off all multiples of 3 in the rest of the list, which would result
in the following state:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 o o x   x   x x x     x     x  x  x     x     x

Eventually, every number in the list will either be circled or crossed out,
as shown in this diagram:

 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 o o x o x o x x x  o  x  o  x  x  x  o  x  o  x


The circled numbers are the primes; the crossed-out numbers are composites.

This algorithm for generating a list of primes is called the sieve of 
Eratosthenes.

Write a program that uses the sieve of Eratosthenes to generate a list
of primes between 2 and an input value of n that must be no more than 1000.


Algorithm development
=====================

Try to get the students to develop an algorithm along the following lines:

 1. Prompt the user for a value of n that is between 2 and 1000 and read
     the value.

 2. generate a string of 'o's named  xsAndOs  of length 1000+1
     We will start by assuming all integers are prime until shown otherwise.
     That is, start by circling all numbers.
     (To make the program simpler, we will create an array of length
     1000+1, with elements xsAndOs[k] for k = 0,1,2,...,1000.  We will 
     waste the first two elements of storage since 0 and 1 are not prime.  
     But this makes indexing the array easier.)
    set elements [0] and [1] to 'x' since 0 and 1 are not prime
    (we will use o's and x's to represent circles and crosses)
    (There could be a better way too ... like setting a known
     composite number to -1.  But our method will give some exercise 
     accessing char arrays.)

   (It might be easier to start with a string of 1000+1 blanks
     and then insert circles ('o's) when you have determined a prime.
     But starting with all circles will be a little faster in the end.)

 3. while (there are more numbers to test)

     4.  find the leftmost number in the list that has not already
           been circled or crossed out.  This number is prime.

     5.  cross out each multiple of the recently determined prime number

    end while

 6. print out the prime numbers.


Steps 1, 2 and 6 should be easy to translate to C directly.

Lets fill in details for 3, 4 and 5.

  3.  Since we will be examining elements in the xsAndOs array, our loop 
      should count over an index (call it k) into the array.  The index 
      can start at 2, since 2 is the first prime number.  How many times 
      do we have to repeat the loop that finds a prime and eliminates
      its multiples? < Ask them >
      It turns out that we only need to repeat the loop up to k <= sqrt(n)
      Eliminating all multiples of a number <= sqrt(n) will eliminate all
      composites <= n.

      Therefore, we can expand 2. to read:
 
      set k = 0
      set kEnd = sqrt(N)
      while ( k <= kEnd )
       ...
      end while

  3. we need to move forward (using the k index) from the last circled number
     until we find a number that has not been circled yet

     while ( xsAndOs(k) is a cross ('x') )
       increase k by 1
     end while

  4. we need to remove all multiples of k from the list.

     for ( j = 2,3,4,... as long as j*k <= n )
         cross off j*k by setting xsAndOs[j*k] to 'x'
     end for

This looks to be enough to then write the complete C program:

#include <stdio.h>     /* so we can use scanf and printf */
#include <math.h>      /* so we can use sqrt */

#define NMAX 1000      /* The largest value of n that we can work with. */

#define CROSS 'x'
#define OH    'o'

int main()
{

    char xsAndOs[NMAX+1];

    int i, k, kEnd, n;

    printf("This program finds all of the prime numbers less than n.\n"
           "Please enter a value of n >= 2 and <= %d : ", NMAX );
    scanf("%d", &n );
    while ( (n < 2) || (n > NMAX) ){
        printf("Please enter a value of n >= 2 and <= %d : ", NMAX );
        scanf("%d", &n );
    }

    printf("The sieve of Eratosthenes will find all primes <= %d.\n", n);
    /* initialize the xsAndOs array */
    for ( i = 0; i <= n; i++ ) {
        xsAndOs[i] = OH; /* everthing assumed prime until proven otherwise */
    }
    xsAndOs[0] = xsAndOs[1] = CROSS;  /* except for 0 and 1 */

    k = 2;
    kEnd = (int) sqrt(n);
    while ( k <= kEnd ) {
        /* find the next prime number */
        while ( xsAndOs[k] == CROSS ) {
            k++;
        }

        /* at this point, we know that k is a prime number */

        /* remove multiples of the prime number from the list */
        for ( i=2; i*k <= n; i++ ) {
            xsAndOs[i*k] = CROSS;
        }

        /* prepare to find the next prime number */
        k++;
    }

    /* print out the prime numbers less than n */
    printf("The prime numbers less than %d are: \n", n);
    for ( i = 2; i <= n; i++ ) {
        if ( xsAndOs[i] == OH ) {
            printf(" %d \n", i );
        }
    }

    return 0;
}


Testing this program
=====================

Ask them:

What values of n would you test the program with?
  o negative n  e.g. -1
  o 0, 1
  o 2,3,4  since small borderline cases
  o and then large values of n  
       e.g.  48 49 and 50
    to make sure that the sqrt(n) loop exit-condition is correct

You could use the isPrime function developed at the start of term
to verify that all of the numbers really are prime!

 Examples using characters and  strings
 ======================================

example 1
=========

Write a function called isVowel() that returns true or false
depending on whether or not a given character is a vowel.

What do we need to tell the function?
   The given char
What do we need to get back from the function?
   Whether or not the  char is a vowel.

This suggests that the prototype should be 
   int isVowel( char c )

The body of the function may be completed by realizing that we
simply need to test to see whether or not c is one of 'a', 'e',
'i', 'o' or 'u'.

But what about case?

It turns out that there is a library of functions for performing
simple operations on characters.  The prototypes for these functions
are in the ctype.h include file.

The function  "char tolower( char ch )" returns ch if ch is a lower
case letter and returns the lowercase equivalent of ch if ch is uppercase.

(Look at the manual page, "man tolower", or the text, for more details.)

Our is isVowel function is then:

  #include <ctype.h>
  int isVowel( char c )
  {
      c = tolower(c);
      return (c == 'a') || (c == 'e') || (c == 'i') || (c == 'o') || (c == 'u');
  }
      

How would you write a isConsonant() function?
=============================================

You could write a function like the above, but with the vowels
replaced by all of the consonants. This would require a lot
of comparisons.  A better way would be to write:

int isConsonant( char c )
  {
      return !isVowel(c);
  }

example 2
=========

Write a function that removes all of the tab characters from a line of 
text and replaces them with an appropriate number of blank spaces.

Tabs move the cursor over so that it is in a position  that is a 
multiple of 8.

For example: 
the string
  "abc\tdefg\tijk"
   0123 45678 901
would look like
  "abc     defg    ijk"
   0123456789012345678
when the tabs are replaced by blanks.

Here is a solution that assumes that the given line string is long enough
to hold the string with tabs replaced by blanks.  See if you can work
them towards this solution.

#define TAB '\t'
#define BLANK ' '

#include <string.h>   /* so we can use strlen function */

void replaceTabs( char line[] ) {

    int lineLength;
    int i, j, shift;

    lineLength = strlen(line);

    for ( i = 0; i < lineLength ; i++ ) {
        if ( line[i] == TAB ) {
           shift = 7 - (i % 8);   /* the number of characters to shift to */
           if ( shift == 0 ) {    /* the right                            */
               shift = 8;
           }

           /* shift the characters to the right of the tab */
           for ( j = lineLength; j > i; j-- ){
               line[j+shift] = line[j];
           }

           /* fill in the required blanks */
           for ( j = 0; j <= shift; j++ ){
               line[i+j] = BLANK;
           }
           lineLength += shift;
        }
    }
}