ALGORITHMS

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material.

Algorithm is a corruption of the original term ALGORISM from the book Kitab al jabr w'al-muquabala ( Rules of Restoration and Reduction ) written in the 9th century by a Persian (then) or Iranian (today) mathematician and astronomer Abu Ja'far Mohammed ibn Musa Al-Khowarizmi.   Algorithm is a step by step sequence of instructions for solving a problem.

Are all sequence of instructions algorithms?  If not, what makes them an algorithm?  The criteria for algorithm are as follows:

effective means that each instruction must be executable
precise means that the order in which the instructions are to be carried out must be very clear
finite means that the algorithm must have a definite number of instructions
terminates means that the execution of the instructions must eventually end logically
general means that the algorithm must be applicable for any set of similar data

EXAMPLE 006: Is the following an algorithm?   Why or why not?
Step 1:   Let COUNT be equal to 0
Step 2:   Add 1 to COUNT
Step 3:   Go to STEP 2

Algorithms may be expressed in various forms such as:

Given a problem, its solution may not readily occur to you.  Good organization is vital to good programming and so is problem analysis.

Problem analysis consists of the following:

Top–down design or stepwise refinement is an approach to designing an algorithm consisting of the following:

Step 1 Understand the problem by thoroughly analyzing it.
Step 2 Formulate the algorithm by determining and writing the main tasks
to be carried out as a sequence of general steps.
Step 3 Fill in more details by determining the sub–tasks, if any, for each main task.
Step 4 Repeat step 3 until you arrive at a precise algorithm
expressed in terms of basic executable instructions.

Validation is the analysis of an algorithm for correctness at each stage of the design process.   It is an important aspect of top–down design.

EXAMPLE 007: Consider the problem of Averaging a set of numbers
GIVEN: scores
NEED: formula for calculating an average
FIND: average of the scores
  • LEVEL ONE OF DEVELOPMENT
    • Input the SCOREs
    • Calculate AVERAGE
    • Output AVERAGE

  • LEVEL TWO OF DEVELOPMENT
    • As each SCORE is entered, COUNT and SUM the SCOREs
    • Calculate AVERAGE using SUM and COUNT
    • Output AVERAGE

  • LEVEL THREE OF DEVELOPMENT
    • Initialize COUNT and SUM to be equal to 0
    • Input SCORE
    • If SCORE is valid
      • Increment COUNT by 1
      • Add the value of SCORE to SUM
      • Input SCORE
    • If COUNT is not 0, then AVERAGE is equal to SUM divided by COUNT
      otherwise AVERAGE is equal to 0
    • Output AVERAGE

OBSERVATIONS:

Basic constructs of algorithms consist of the simple, selective, repetitive, and sequential constructs.

In NSD, they are represented as follows:

Going back to the example on averaging, we have the following:

where x ¬ y means assign the value of y to x.



Algorithm

Basic Constructs
Basic Executable Instructions

Do Statement

Effective

Finite
For Statement

General
General Steps
Good Organization

Main Tasks

Nassi-Schneiderman Diagram NSD

Precise
Problem Analysis

Repetitive Construct

Selective Construct
Sequential Construct
Simple Construct
Stepwise Refinement
Sub-tasks

Terminates
Top-down Design

Validation

While Statement

Review Questions on Algorithms
( Check the calendar for the due date )


© 1994-07-23 cpsm ; last update 2012-01-09 13:46