Stepwise Refinement (Example)

In class last week, we talked about the idea of "top down stepwise refinement" as a problem-solving technique. This can help a person "think through" an algorithm by doing the following:

Start with the initial problem statement
Break it into a few general steps
Take each "step", and break it further into more detailed steps
Keep repeating the process on each "step", until you get a breakdown that is pretty specific, and can be written more or less in pseudocode
Translate the pseudocode into real code

Below is the example we did in lecture class.

Example

Problem Statement: Determine the class average for a set of test grades, input by the user. The number of test grades is not known in advance (so the user will have to enter a special code -- a "sentinel" value -- to indicate that he/she is finished typing in grades).

Initial breakdown into steps

   Declare and initialize variables
   Input grades (prompt user and allow input)
   Compute class average and output result

Now, breaking down the "compute" step further, we got:

  Compute:
    add the grades
    count the grades
    divide the sum by the count

We realized this would be a problem, because to do all input before doing the sum and the count would require us to have enough variables for all the grades (but the number of grades to be entered is not known in advance). So we revised our breakdown of "steps".

Don't be afraid to go back and revise something if the initial plan runs into a snag!

Revised breakdown of steps

   Declare and initialize variables
   Input grades -- count and add them as they are input
   Compute class average

Breaking the steps into smaller steps

So, now we can break down these 3 steps into more detail. The input step can roughly break down this way:

  loop until the user enters the sentinel value (-1 would be good)
     prompt user to enter a grade (give them needed info, like -1 to quit)
     allow user to type in a grade (store in a varaible)
     add the grade into a variable used for storing the sum
     add 1 to a counter (to track how many grades)

We could specifically write this as a while loop or as a do-while loop. So one more refining step would be a good idea, to formulate the pseudo-code more like the actual code we would need to write. For example:

  do
     prompt user to enter a grade (give them needed info, like -1 to quit)
     allow user to type in a grade (store in a varaible)
     add the grade into a variable used for storing the sum
     add 1 to a counter (to track how many grades)
  while user has NOT entered the sentinel value (-1 would be good)

If we look at this format, we realize that the "adding" and "counting" steps should only be done if the user entry is a grade, and NOT when it's the sentinel value. So we can add one more refinement:

  do
     prompt user to enter a grade (give them needed info, like -1 to quit)
     allow user to type in a grade (store in a varaible)
     if the entered value is a GRADE (not the sentinel value)
         add the grade into a variable used for storing the sum
         add 1 to a counter (to track how many grades)
  while user has NOT entered the sentinel value (-1 would be good)

This breakdown helps us see what variables are needed, so the declare and initialize variables step can be now made more specific:

  initialize variables:
    a grade variable (to store user entry)
    a sum variable (initialized to 0)
    a counter (initialized to 0)

And the compute answer and print step becomes:

   divide sum by counter and store result
   print result

Putting it all together

This is approximately where we left it at the end of class:

  initialize variables:
  ---------
    a grade variable (to store user entry)
    a sum variable (initialized to 0)
    a counter (initialized to 0)

  grade entry:
  ---------
    do
      prompt user to enter a grade (give them needed info, like -1 to quit)
      allow user to type in a grade (store in a varaible)
      if the entered value is a GRADE (not the sentinel value)
         add the grade into a variable used for storing the sum
         add 1 to a counter (to track how many grades)
    while user has NOT entered the sentinel value (-1 would be good)

  Compute average:
  ---------
    divide the sum by the counter
    print the answer

What's left to do?

It would be a good idea to refine the last step (compute and print average) more specifically, since it's possible for the user to type the sentinel value without entering any grades. In this case, you don't want to divide by "counter", because that would be 0. This step should account for this possibility. (i.e. if the user has entered no grades, just print a message to that effect. Otherwise, compute and print the average).
Once the steps reach this level of detail, the pseudocode can be translated to real code. This is left as an exercise.