- while statement
- do statement
- for statement
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:
| 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: 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 detail 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: Consider the problem of Averaging a set of numbers
| GIVEN: | scores |
| NEED: | formula for calculating an average |
| FIND: | average of the scores |
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.