1.2 Characteristics of an algorithm
Let us try to present the scenario of a man brushing his own teeth(natural denture) as an algorithm as follows.
Step 1. Take the brush
Step 2. Apply the paste
Step 3. Start brushing
Step 4. Rinse
Step 5. Wash
Step 6. Stop
If one goes through these 6 steps without being aware of the statement
of the problem, he could possibly feel that this is the algorithm for
cleaning a toilet. This is because of several ambiguities while
comprehending every step. The step 1 may imply tooth brush, paint
brush, toilet brush etc. Such an ambiguity doesn’t an instruction an
algorithmic step. Thus every step should be made unambiguous. An
unambiguous step is called definite instruction. Even if the step 2 is
rewritten as apply the tooth paste, to eliminate ambiguities yet the
conflicts such as, where to apply the tooth paste and where is the
source of the tooth paste, need to be resolved. Hence, the act of
applying the toothpaste is not mentioned. Although unambiguous, such
unrealizable steps can’t be included as algorithmic instruction as they
are not effective.
The definiteness and effectiveness of an instruction implies the
successful termination of that instruction. However the above two may
not be sufficient to guarantee the termination of the algorithm.
Therefore, while designing an algorithm care should be taken to provide
a proper termination for algorithm.
Thus, every algorithm should have the following five characteristic feature
1. Input
2. Output
3. Definiteness
4. Effectiveness
5. Termination
Therefore, an algorithm can be defined as a sequence of definite and
effective instructions, which terminates with the production of correct
output from the given input.
In other words, viewed little more formally, an algorithm is a step by
step formalization of a mapping function to map input set onto an
output set.
The problem of writing down the correct algorithm for the above problem of brushing the teeth is left to the reader.
For the purpose of clarity in understanding, let us consider the following examples.
Example 1:
Problem : finding the largest value among n>=1 numbers.
Input : the value of n and n numbers
Output : the largest value
Steps :
1. Let the value of the first be the largest value denoted by BIG
2. Let R denote the number of remaining numbers. R=n-1
3. If R != 0 then it
is implied that the list is still not exhausted. Therefore look the
next number called NEW.
4. Now R becomes R-1
5. If NEW is greater than BIG then replace BIG by the value of NEW
6. Repeat steps 3 to 5 until R becomes zero.
7. Print BIG
8. Stop
End of algorithm
Example 2: quadratic equation
Example 3: listing all prime numbers between two limits n1 and n2.
1.2.1 Algorithmic Notations
In this section we present the pseudocode that we use through out the
book to describe algorithms. The pseudo code used resembles PASCAL and
C language control structures. Hence, it is expected that the reader be
aware of PASCAL/C. Even otherwise atleast now it is required that the
reader should know preferably C to practically test the algorithm in
this course work.
However, for the sake of completion we present the commonly employed control constructs present in the algorithms.
1. A conditional statement has the following form
If < condition> then
Block 1
Else
Block 2
If end.
This pseudocode executes block1 if the condition is true otherwise block2 is executed.
2. The two types of loop structures are counter based and conditional based and they are as follows
o For variable = value1 to value2 do
Block
For end
Here the block is executed for all the values of the variable from value 1 to value 2.
o There are two types of conditional looping, while type and repeat type.
While (condition) do
Block
While end.
Here block gets executed as long as the condition is true.
o Repeat
Block
Until<condition>
Here block is executed as long as condition is false. It may be observed that the block is executed atleast once in repeat type.
Exercise 1;
Devise the algorithm for the following and verify whether they satisfy all the features.
1. An algorithm that inputs three numbers and outputs them in ascending order.
2. To test whether the three numbers represent the sides of a right angle triangle.
3. To test whether a given point p(x,y) lies on x-axis or y-axis or in I/II/III/IV quadrant.
4. To compute the area of a circle of a given circumference
5. To locate a specific word in a dictionary.
for more details click here:
http://%20%20www.vyomworld.com/gate/cs/ada/1.2.asp - http://www.vyomworld.com/gate/cs/ada/1.2.asp
|