 ### 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 means that the order in which the instructions are to be carried out must be very clear means that the algorithm must have a definite number of instructions means that the execution of the instructions must eventually end logically 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:

• Identify the given
• Identify the elements of the problem
• Identify the initial values of the elements of the problem
• Identify the final values of the elements of the problem
• State the problem
• Develop the algorithm

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:

• Use of identifiers SCORE, COUNT, SUM, and AVERAGE
• Initialization of identifiers COUNT and SUM
• Use of repetition or repetitive construct
• Use of selection or selective construct

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

In NSD, they are represented as follows:

• Simple construct in NSD
• Figure 004:   NSD for simple statement

• Selective construct in NSD
• Figure 005:   NSD for if-else statement

• Repetitive construct correspond to three statements:
• while statement
• Figure 006:   NSD for while statement

• do statement
• Figure 007:   NSD for do statement

• for statement
• Figure 008:   NSD for for statement

• Sequential construct: consists of a sequence of combinations of any of the simple, selective, and repetitive constructs.

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

• LEVEL ONE OF THE DEVELOPMENT
• Figure 009:   NSD Level 1 of the development

• LEVEL TWO OF THE DEVELOPMENT
• Figure 010:   NSD Level 2 of the development

• LEVEL THREE OF THE DEVELOPMENT
• Figure 011:   NSD Level 3 of the development

• More symbolically, we have
• Figure 012:   NSD for the Calculation of Average

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 )