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:
Topdown 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 subtasks, if any, for each main task.|
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 topdown design.
|EXAMPLE 007:||Consider the problem of Averaging a set of numbers|
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.
Basic Executable Instructions
Nassi-Schneiderman Diagram NSD
Review Questions on Algorithms
( Check the calendar for the due date )