CS101 - Algorithm Development Example

Below is an example of how to develop an algorithm in a top-down fashion. The most important thing to note is that the problem is solved in stages. The first stage, the main algorithm, should contain all the information necessary to solve the problem. In essence it is simply a rewording of the original problem, just in a slightly more structured form (pseudo-code). Each step (sub-piece of the original problem) should be explicit enough to form a problem in its own right. In other words, if you could take any step in your algorithm, give it to a friend and they could solve it without knowing anything about the original problem or requiring any additional information, then you have probably got about the right level of detail. Before starting to think about the details of each step, be sure that the proposed solution really will work, otherwise subsequent work may be wasted! Check all preconditions are satisfied and look for any unusual conditions that could potentially cause the solution to fail.

You can extract the data requirements of each stage of the algorithm based on the preconditions of each of its steps. Any information that must be "remembered" from one step to another requires a memory location to store it in. Mark each such memory/data element as being I (input to this stage), O (output from -result of- this stage) or L (only used locally within this stage). Determine the type of each element and whether the element is a variable or constant. If it is a constant, specify its value.

Note: You may not yet know how to convert the solution into Java, however, you should be able to do such a design yourself. You should also be able to understand the actual Java program corresponding to the design.

Exam Average Problem

Compute average of a set of exam scores. The program should ask for the number of exam sheets and then read in that many scores. Finally it should report the average of the scores.

Main algorithm

1. Ask for and get number of exam sheets from user
2. For the given number of exam sheets, read each score and use to calculate sum of scores
3. Compute average as sum of scores divided by number of exam sheets
4. Report average

Data requirements

L number of exam sheets - integer variable
L sum of scores - integer variable
L average - integer variable

Expand 1. { 1. Ask for and get number of exam sheets from user }

1.1 Prompt user to enter number of exam sheets
1.2 Read number of exam sheets from keyboard

Data requirements

O number of exam sheets - integer variable

Expand 2. { For the given number of exam sheets, read each score and use to calculate sum of scores }

2.1    Initialise sum of scores so far to 0
2.2    for each sheet from 1 to number of exam sheets 
2.2.1       prompt user for exam score
2.2.2       get the exam score for the current sheet
2.2.3       add exam score to sum of scores so far
2.3    sum of scores is sum of scores so far

Data requirements

I number of exam sheets - integer variable
L sum of scores so far - integer variable
O sum of scores - integer variable
L sheet - integer variable
L exam score - integer variable

Expand 3. { Compute average as sum of scores divided by number of exam sheets }

...not necessary…

Data requirements

O average - double variable
I sum of scores - integer variable
I number of exam sheets - integer variable

Expand 4. { Report average }

...not necessary…

Data requirements

I average - double variable

Implementation

Begin implementation by starting a new project with the CS101 Simple Console Template in JCreator. Into it type first the constants, then the variables, then your main algorithm as comments. Next fill in the corresponding algorithm and/or code for each sub-section. Remember to save frequently. It is also an idea to compile & even possibly execute every so often to ensure that no silly mistakes are being made. The earlier you catch errors, the easier they are to fix!

Notes

Pay particular attention to the layout (style) of your code. Use white space -indentation, blank lines & spaces- to make the code easier to read. Also, don't forget to include the header comments!
This example places all the code together in the main method. Normally, each sub-problem (of any size) would be implemented in a seperate method.

Java Program

The following implementation assumes the use of the CS101 Console template & the Scanner class.

// constants…

// variables…

int      numberOfExamSheets,
         sumOfScores,
         sumOfScoresSoFar,
         sheet,
         examScore;

double   average;

// program code

Scanner scan = new Scanner( System.in);

// 1. Ask for & get numberOfExamSheets from user
System.out.print( "Enter the number of exam sheets to process ");
numberOfExamSheets = scan.nextInt();

// 2. For the given number of exam sheets, read each score and use to calculate sum of scores
sumOfScoresSoFar = 0;
for ( sheet = 1; sheet <= numberOfExamSheets; sheet = sheet + 1) {
     System.out.print( "Enter exam score ");
     examScore = scan.nextInt();
     sumOfScoresSoFar = sumOfScoresSoFar + examScore;
}
sumOfScores = sumOfScoresSoFar;

// 3. Compute average as sum of scores divided by number of exam sheets
average = sumOfScores / numberOfExamSheets;

// 4. Report average
System.out.println( "The average for the exam is " + average);