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 | |||||
|
||||||
|
OBSERVATIONS:
Basic constructs of algorithms consist of the simple, selective, repetitive, and sequential constructs.
In NSD, they are represented as follows:
Figure 004: NSD for simple statement
Figure 005: NSD for if-else statement
Figure 006: NSD for while statement
Figure 007: NSD for do statement
Figure 008: NSD for for statement
Going back to the example on averaging, we have the following:
Figure 009: NSD Level 1 of the development
Figure 010: NSD Level 2 of the development
Figure 011: NSD Level 3 of the development
Figure 012: NSD for the Calculation of Average
where x ¬ y means assign the value of y to x.
Review Questions on Algorithms
( Check the calendar for the due date )