1 Basics of Algorithm Writing, Iterative and recursive Algorithms
S. Sridhar
Module – 3
Basics of Algorithm Writing
This module focuses on the basics of the algorithm writing. The learning objectives of this module are as follows:
- To introduce pseudo-code notations for writing algorithms
- To practice writing elementary algorithms
- To introduce iterative and recursive algorithms
Algorithms as discussed earlier are step by step procedure for solving a given problem. As said earlier, algorithms can be written using natural language or pseudocode. There is no standard way of writing algorithms in pseudocode. So there is a need for basic guidelines for writing algorithms. The problem solving starts with step wise refinement. The idea of step wise refinement is to take a problem and try to divide it into many sub problems. The sub problems can further be divided more sub-problems. The subdivision will be carried out till the problem can’t further be divided. Hence, the idea of step wise refinement is to evolve structures that can be directly implemented in a programming language.
The kinds of structures thus evolved are sequence, decision and Iteration. These are called control structures and are described below:
1. Sequence
Sequence is a structure whereby the computer system executes tasks one by one. This is given as follows:
Task P
Task Q
Task R
Here, the task P is executed first, followed by tasks Q and R.
2. Decision or Conditional Branching
This is a control structure where the condition is evaluated first and based on its condition the course of action is decided. The control structure for decision is given as follows:
IF (Condition C) Then
Perform Task A
Else
Perform Task B
It can be observed that the condition C is evaluated first. Then based on the results of the condition, task P is performed if the condition is true or task Q is performed if the condition is false.
3. Repetition
Computers are known for their effectiveness in solving repetitive tasks. Repetition control structure is given as follows:
While (condition C) do
R
For example, informally we say often in English language “Perform the task 100 times”. This is a kind of repetition.
There are two types of iteration. Iteration like saying “Perform task A exactly 500 times” is called a bounded iteration. Programming languages do provide a ‘For – Statement” that implements a bounded iteration. On the other hand, statements like performing a task for a specific condition are called unbound iteration. Good examples of unbounded iteration are statements like “While…End while” and “repeat …. until”.
Once the control structures are evolved, then it has to be written as an algorithm. There are only three ways of writing algorithms:
1. Using a natural language like English.
2. Using a programming languages, say C++ or Java.
3. Pseudocode
English, or any natural language, is obvious choice for writing algorithms. But the problem is most of the natural languages are ambiguous as a wrong interpretation of a word may lead to imprecise implementation. Hence, natural languages are not considered suitable for algorithm writing. Similarly, the usage of a programming language makes algorithm dependent on a particular language. Hence, pseudocode is preferable for writing algorithms. One can recollect from module 1 that pseudocode is a mix of natural language like English and mathematical constructs.
Let us evolve a pseudocode conventions so that the algorithm can be written. The pseudocode conventions of the algorithms are specified below:
1. Assignment Statement
Assignment statement is a statement for assigning a value or expression to a variable. For example, the following assignment statements are valid.
x = 20
z = r + k
2. Input/output Statements
Input statement is used by the user to give values to the variables of the algorithm. For example, the following statement is right.
Input x, y
Similarly, the print or write statement is used to print the values of the variables. For example, the following statement is used to print the value of the variable x and y.
Print x,y or Write x,y
3. Conditional Statements
Algorithm can have conditional statement. The syntax of the conditional statement can be shown as:
If (condition) then
Statement (s)
End if
Here, the condition (True or false type) is evaluated first. If the condition is true, then statement(s) are executed. “If- Endif” serves as brackets for the conditional statement. Conditional statement can have else part also as shown below:
If (condition) then
Statement A ;
else
Statement B
End if
Here, If the condition is true, then statement A (This can be a set of statements also) are executed. Otherwise, if the condition is false, then statement B (This also can be a single or multiple statements) is executed.
4. Repetition Statement
Algorithms can have repetitive statements. Three repetitive statements are supported by most of the programming languages.Unconditional repetitive statement is ‘For’ statement. This is an example of bounded iteration. The syntax of this statement is given as follows
For variable = value1 to value2 do
Statement(s)
End for
Computer system executes this statement like this: First the variable is to value1. Value1 and value2 can be a value or an expression. Then the statement(s) is executed till the variable values reaches value2.
Conditional Loop:
One useful repetitive statement is “While” statement that provides a conditional loop. The syntax of the statement is given below:
While (Condition) do begin
Statement(s);
End while.
Repeat…Until also provides repetition control structure. The difference between this statement and While statement is that “repeat – until” statement first executes the task and then checks condition of the statement. The syntax of repeat statement is given below:
repeat
Statement(s)
until (condition)
Using these statements, some elementary algorithms can be designed.
let us practice some elementary algorithms and let us consider the problem of converting Fahrenheit to Celsius. The problem can be directly solved using a simple formula. The formula for conversion is given as
celsius = 95 ´ ( Farenheit – 32)
The algorithm can be written informally as follows:
1. Input Fahrenheit temperature
2. Apply the formula for temperature conversion
3. Display the results.
The algorithm can be given formally as follows:
Algorithm FtoC(F)
Input : Fahrenheit F
Output: Celsius
Begin
Celsius = (5/9)* (F-32)
Return Celsius;
End.
Let us practice one more algorithm for finding the count and sum of even/odd numbers of an array. The algorithm can be given informally as follows;
1. Initialize oddcount, evencount, oddsum and evensum
2. Read the sumber
3. If it is odd or even, then increment the appropriate counters
4. Display the results
The algorithm is formally given as follows:
Algorithm sumoddeven (A[1..n])
Input: An array A[1..n]
Output: sum on odd and even number count
oddcount = 0
evencount = 0
oddsum = 0
evensum = 0
for i = 1 to n
reminder = A[i] mod 2
if (reminder = 0) then
evensum = evensum + A[i]
evencount = evencount + 1
else
oddsum = oddsum + A[i]
oddcount = oddcount + 1
End if
End for
Return evensum, evencount, oddsum, oddcount
End
Another popular algorithm is linear search. Here, a target is given and the objective of the linear search is to display whether the target is present in the given array, if so where? And failure message is the target is not present in the array. The informal algorithm is given as follows:
- Read the value of the target and array A
- Index = 1, found = false
- Repeat until found = true of index > n if the value at index = target then return the index and set found = true else index = index + 1
- If (not found) then output message that target is not found
- Exit
It can be seen that initially index and flag found is initialized to 1 and „false‟ respectively. Every value guided by index pointer is checked and if the target is found, then the flag is set true and the corresponding index is sent. Otherwise, the failure message to find target is printed.
Formally this can be written as follows:
Algorithm Search(list, n , target)
Begin
index = 1
found = false
repeat until found = true of index > n
if (listindex = target ) then
print “target found at”, index
found = true
else index = index + 1
if (not found) then print „Target is not found‟
End
Thus one can conclude that after stepwise refinement, the control structures are evolved and can be written suitable as a pseudocode. Now let us discuss about recursive algorithms.
Basics of Recursion
Recursion is a way of defining an object using the concept of self-reference. The statements like “A length of the linked list of size N is 1 plus the length of the remaining linked list of size N-1” are examples of recursive definition.
Let us start with recursive definitions. The basic components of a recursive algorithm definition are given as follows:
- Base case – This is also known as initial values. This is the non-recursive part.
- Recursive step – It is the recursive part of the algorithm. Often this is a rule used for calculating a function in terms of the previous values of the function.
- Step for progress towards base case: This is a condition that ensures the algorithm eventually converges by bringing the recursive step towards the base case.
Let us discuss some recursive algorithms now. Let us consider the problem of finding summation
n
problem given as ån . The recursive definition of summation can be given compactly as
i =1
follows
0
if n = 0
Sigma(n) =
n+ Sigma(n-1)
if n > 1
A simple recursive algorithm for implementing the above recursive formula is given as follows:
Algorithm Sigma (N)
Program: Compute sum recursively
Input: N
Output: Sum of N numbers
Begin
if (N == 0)
return 0;
else
return N + Sigma(N – 1);
End if
End
The above algorithm can also be written as an iterative algorithm. The iterative algorithm is given as follows:
Algorithm iterative-sigma(N)
Program: Compute sum recursively
Input: N
Output: Sum of N numbers
Begin
sum = 0;
for i = 1 to N do
sum = sum + I
end for
End
It can be observed that both versions give identical answers. It can be observed that recursive algorithms are compact and it is easier to formulate the algorithms. But , the disadvantage is that recursive algorithms take extra space and require more memory.
Let us discuss about one more recursive algorithm for finding factorial of a number. The recursive function for finding the factorial of a number is given as follows:
1
if n = 0
Factorial(n)
=
n ´
factorial(n-1) if
n ³1
The pseudocode for finding factorial of a number is given as follows:
Algorithm MFactorial(m)
Begin
If m < 0 then
print “factorial for negative numbers is not possible” End if
If ((m=0) OR (m = 1) then
Return 1;
Else
Return m * MFactorial(m-1);
End If
End.
Another important problem is towers of Hanoi. There are three pegs – source, intermediate and destination. The objective of this problem is to move the disks from source peg to the destination peg using the intermediate peg with the following rules:
1. At any point of time, only one disk should be moved
2. A larger disk cannot be placed on the smaller disk at any point of time
The logic for solving this problem is that, for N disks, N-1 disks are moved to the intermediate tower and then the larger disk is moved to the destination. Then the disks are moved from the intermediate tower to the destination.
The formal algorithm is given as follows:
Algorithm towersofhanoi(A,B,C,n)
Input: Source Peg A, intermediate Peg B and Destination Peg C, n disks
Output: All the disks in the tower C
Begin
if n = 1 the move disk from A to C
lse
towersofhanoi (A,C,B,n-1);
move disk from A to C
towersofhanoi (B,A,C,n-1);
End if
End.
Thus, one can conclude this module as follows:
1. Stepwise refinement leads to a better algorithm
2. Control structures are sequence, Decision or conditional branching and repetition
3. Pseudocode is better way of writing algorithms.
References
- S.Sridhar – Design and Analysis of Algorithms, Oxford University Press, 2014.
- Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.