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: Even if you do know how to convert the solution into Java, 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.

The Perfect Number Problem

A perfect number is one where the sum of all its divisors, except itself, is equal to the number itself. For example 6 is perfect since the sum of its divisors 1, 2 and 3 is 6. Design and implement a program which takes a value from the user and reports whether it is perfect or not.

Main algorithm

1.  Ask for & get number to check
2.  Compute sum of divisors for the number to check
3.  if sum of divisors equals number to check then
3T      report number to check is perfect
    else
3F      report number to check is not perfect

Data requirements

L number to check - integer variable
L sum of divisors - integer variable

Expand 1. { Ask for & get number to check }

1.1 Prompt user to enter number to check
1.2 Read number to check from keyboard

Data requirements

O number to check - integer variable

Expand 2. { Compute sum of divisors for the number to check }

2.1  Initialise sum so far to 0
2.2  for each value i starting from 1 up to but not including the number to check in unit steps
       if i is a divisor of number to check then
          add i to sum so far
2.3  sum of divisors is sum so far

Data requirements

I number to check - integer variable
L sum so far - integer variable
L i - integer variable
O sum of divisors - integer variable

Note: The above solution is very simple and inefficient! We can improve on it by only checking values for i up to half of the number to check. We might go even further and only check up to the square root of the number to check, but then, if i is a divisor, add both i and the number to check divided by i (except if it is 1 or the two values are equal!) You may like to try rewriting the algorithm for this solution. It would be an interesting exercise to actually implement all of these solutions and then perform experiments to compare their performance.

Expand 3. { if sum of divisors equals number to check then report number to check is perfect else not }

...not necessary…

Data requirements

I number to check - integer variable
I sum of divisors - integer 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 separate method.

Java Program

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

// constants…

// variables…

int numberToCheck,
    sumOfDivisors,
    sumSoFar,
    i;

// program code

Scanner scan = new Scanner( System.in);

// 1. Ask for & get number to check
System.out.print( "Enter the number to check");
numberToCheck = scan.nextInt();

// 2. Compute sum of divisors for the number to check
sumSoFar = 0;
for ( i = 1; i < numberToCheck; i = i + 1 ) {
   if ( numberToCheck % i == 0)
      sumSoFar = sumSoFar + i; 
}
sumOfDivisors = sumSoFar;

// 3. if sum of divisors equals number to check then
//       report number to check is perfect else not
if ( numberToCheck == sumOfDivisors ) 
   System.out.println( "The value " + numberToCheck + " is PERFECT" );
else
   System.out.println( "The value " + numberToCheck + " is NOT PERFECT" );