BUILDING BLOCKS OF ALGORITHMS

Next, we enumerate the basic actions and corresponding instructions used in a
computer system based on a Von Neuman architecture. We may recall that an
instruction is a notation for an action and a sequence of instructions defines a
program whereas a sequence of actions constitutes a process. An instruction is also
called a statement.



The following three basic actions and corresponding instructions form the basis of
any imperative language. For the purpose of explanations, the notation similar to
that of a high-level programming language is used.

1.6.1 Basic Actions & Instructions

(i) Assignment of a value to a variable is denoted by
                       variable <- expression;
where the expression is composed from variable and constant operands using familiar
operators like +, -, * etc.

Assignment action includes evaluation of the expression on the R.H.S. An example of
assignment instruction/statement is

                            j<-2*i + j - r ;

It is assumed that each of the variables occurring on R.H.S. of the above statement,
has a value associated with it before the execution of the above statement. The
association of a value to a variable, whether occurring on L.H.S or on R.H.S, is made
according to the following rule:

For each variable name, say i, there is a unique location, say loc 1 (i), in the main
memory. Each location loc(i), at any point of time contains a unique value say v(i).
Thus the value v(i) is associated to variable i.

 Using these values, the expression on R.H.S. is evaluated. The value so obtained is
the new value of the variable on L.H.S. This value is then stored as a new value of the
variable (in this case, j) on L.H.S. It may be noted that the variable on L.H.S (in this
case, j) may also occur on R.H.S of the assignment symbol.

In such cases, the value corresponding to the occurrence on R.H.S (of j, in this case)
is finally replaced by a new value obtained by evaluating the expression on R.H.S (in
this case, 2 * i + j ─ r).

The values of the other variables, viz., i and r remain unchanged due to assignment
statement.

(ii) The next basic action is to read values of variables i, j, etc. from some
secondary storage device, the identity of which is (implicitly) assumed here, by a
statement of the form

The values corresponding to variables i, j,… in the read statement, are, due to read statement, stored in the corresponding locations loc(i) , loc(j),…, in the main memory. The values are supplied either, by default, through the keyboard by the user or from some secondary or external storage. In the latter case, the identity of the secondary or external storage is also specified in the read statement.

(iii) The last of the three basic actions, is to deliver/write values of some variables say i, j, etc. to the monitor or to an external secondary storage by a statement of the form

The values in the locations loc(i), loc(j),…, corresponding to the variables i, j …, in the write statement are copied to the monitor or a secondary storage. Generally, values are written to the monitor by default. In case, the values are to be written to a secondary storage, then identity of the secondary storage is also specified in the write statement. Further, if the argument in a write statement is some sequence of characters enclosed within quotes then the sequence of characters as such, but without quotes, is given as output. For example, corresponding to the write statement.

                            Write (‘This equation has no real roots’ )

the algorithm gives the following output:

This equation has no real roots.

In addition to the types of instructions corresponding to the above mentioned actions, there are other non-executable instructions which include the ones that are used to define the structure of the data to be used in an algorithm. These issues shall be discussed latter.
 
                                         1.6.2 Control Mechanisms and Control Structures

In order to understand and to express an algorithm for solving a problem, it is not enough to know just the basic actions viz., assignments, reads and writes. In addition, we must know and understand the control mechanisms. These are the mechanisms by which the human beings and the executing system become aware of the next instruction to be executed after finishing the one currently in execution. The sequence of execution of instructions need not be the same as the sequence in which the instructions occur in program text. First, we consider three basic control mechanisms or structuring rules, before considering more complicated ones.

(i) Direct Sequencing: When the sequence of execution of instructions is to be the same as the sequence in which the instruction are written in program text, the control mechanism is called direct sequencing. Control structure, (i.e., the notation for the control mechanism), for direct sequencing is obtained by writing of the instructions,

* one after the other on successive lines, or even on the some line if there is enough space on a line, and

* separated by some statement separator, say semi-colons, and

* in the order of intended execution.

                           For example, the sequence of the three next lines

                                         A;B;
                                          C;
                                          D;

denotes that the execution of A is to be followed by execution of B, to be followed by execution of C and finally by that of D.

When the composite action consisting of actions denoted by A, B, C and D, in this order, is to be treated as a single component of some larger structure, brackets such as ‘begin….end’ may be introduced, i.e., in this case we may use the structure

                                              Begin A;B;C;D end.

Then the above is also called a (composite/compound) statement consisting of four (component) statement viz A, B, C and D.

(ii) Selection: In many situations, we intend to carry out some action A if condition Q is satisfied and some other action B if condition Q is not satisfied. This intention can be denoted by:

                                               If Q then do A else do B,

Where A and B are instructions, which may be even composite instructions obtained by applying these structuring rules recursively to the other instructions.

Further, in some situations the action B is null, i.e., if Q is false, then no action is stated.

This new situation may be denoted by

If Q then do A

In this case, if Q is true, A is executed. If Q is not true, then the remaining part of the instruction is ignored, and the next instruction, if any, in the program is considered for execution.

Also, there are situations when Q is not just a Boolean variable i.e., a variable which can assume either a true or a false value only. Rather Q is some variable capable of assuming some finite number of values say a, b, c, d, e, f. Further, suppose depending upon the value of Q, the corresponding intended action is as given by the following table:

Value                        Action

                                                                   

                                                              a                               A

                                                               b                               A

                                                               c                                B

                                                               d                              NO ACTION

                                                               e                               d

                                                                f                             NO ACTION

The above intention can be expressed through the following notation:

..

Example 1.6.2.1: We are to write a program segment that converts % of marks to grades as follows:

..

..

(iii) Repetition: Iterative or repetitive execution of a sequence of actions, is the
basis of expressing long processes by comparatively small number of
instructions. As we deal with only finite processes, therefore, the repeated
execution of the sequence of actions, has to be terminated. The termination
may be achieved either through some condition Q or by stating in advance the
number of times the sequence is intended to be executed.

(a) When we intend to execute a sequence S of actions repeatedly, while
condition Q holds, the following notation may be used for the purpose:

                                    While (Q) do begin S end;

Example 1.6.2.2: We are required to find out the sum (SUM) of first n natural
numbers. Let a variable x be used to store an integer less than or equal to n, then the
algorithm for the purpose may be of the form:

..

Explanation of the algorithm Sum_First_N_1:

Initially, an integer value of the variable n is read. Just to simplify the argument, we
assume that the integer n <_ 1. The next two statements assign value 1 to each of the
variables x and SUM. Next, we come the execution of the while-loop. The while-loop
extends from the statement (a1) to (B1) both inclusive. Whenever we enter the loop,
the condition x<n is (always) tested. If the condition x<n is true then the whole of the
remaining portion upto B (inclusive) is executed. However, if the condition is false
then all the remaining statement of the while-loop, i.e., all statements upto and
including (B1) are skipped.

Suppose we read 3 as the value of n, and (initially) x equals 1, because of x1. Elementary Algorithmics
Therefore, as 1<3, therefore the condition x<n is true. Hence the following portion of
the while loop is executed:

begin

               ...

end

and as a consequence of execution of this composite statement

the value of x becomes 1 and
and the value of SUM becomes 3

As soon as the word end is encountered by the meaning of the while-loop, the whole
of the while-loop between (a1) and (B1) , (including (a1) and a1B1)) is again
executed.

By our assumption n = 3 and it did not change since the initial assumption about n;
however, x has become 2. Therefore, x<n is again satisfied. Again the rest of the
while loop is executed. Because of the execution of the rest of the loop, x becomes 3
and SUM becomes the algorithm comes to the execution of first statement of whileloop,
i.e., while (x<n) do, which tests whether x<n. At this stage x=3 and n=3.
Therefore, x<n is false. Therefore, all statement upto and including (1) are x<n
skipped.

Then the algorithm executes the next statement, viz., write (‘The sum of the first’, n,
‘natural numbers is’, sum). As, at this stage, the value of SUM is 6, the following
statement is prompted, on the monitor:

The sum of the first 3 natural numbers is 6.

It may be noticed that in the statement write (‘ ‘, n, ‘ ’, SUM) the variables n and
SUM are not within the quotes and hence, the values of n and SUM viz 3 and 6 just
before the write statement are given as output,

Some variations of the ‘while…do’ notation, are used in different programming
languages. For example, if S is to be executed at least once, then the programming
language C uses the following statement:

Do S while (Q)

Here S is called the body of the ‘do. while’ loop. It may be noted that here S is not
surrounded by the brackets, viz., begin and end. It is because of the fact do and while
enclose S.

Again consider the example given above, of finding out the sum of first n natural
numbers. The using ‘do … while’ statement, may be of the form:

The above instruction is denoted in the programming language Pascal by

                        Repeat S until (not Q)

Example 1.6.2.3: Algorithm Sum_First_N_2

Begin {of algorithm}
read (n);

..

If number n of the times S is to be executed is known in advance, the
following notation may be used:

for v varying from i to (i+n–1) do begin S end;

                       Or

for v <- i to (i + ─ 1) do
begin S end;

where v is some integer variable assuming initial value i and increasing by 1 after
each execution of S and final execution of S takes place after v assumes the value
i+n–1.

Then the execution of the for-loop is terminated. Again begin S do is called the body
of the for-loop. The variable x is called index variable of the for-loop.

Example 1.6.2.4: Again, consider the problem of finding the sum of first n natural
numbers, algorithm using ‘for …’ may be of the form:

algorithm Sum_First_N_3
begin
read (n);
SUM<- 0
for x <- 1 to n do (a3)
begin
SUM <- SUM + x (B 3)
end;
write (‘The sum of the first first’, n, natural numbers numbers’, SUM)
end. {of the algorithm}

In the algorithm Sum_First_N_3 there is only one statement in the body of the
for-loop. Therefore, the bracket words begin and end may not be used in the for-loop.
In this algorithm, also, it may be noted that only the variable SUM is initialized. The
variable x is not initialized explicitly. The variable x is implicitly initialised to 1
through the construct ‘for x varying from 1 to n do’. And, after each execution of the
body of the for-loop, x is implicitly incremented by 1.

A noticeable feature of the constructs (structuring rules) viz., sequencing, selection
and iteration, is that each defines a control structure with a single entry point and
single exit point. It is this property that makes them simple but powerful building
blocks for more complex control structures, and ensures that the resultant structure
remains comprehensible to us.

Structured Programming, a programming style, allows only those structuring rules
which follow ‘single entry, single exit’ rule.

Ex.4) Write an algorithm that finds the real roots, if any, of a quadratic equation
ax2 + bx + c = 0 with a # 0, b, c as real numbers.

Ex.5) Extend your algorithm of Ex. 4 above to find roots of equations of the form ax2 + bx +c = 0, in which a, b, c may be arbitrary real numbers, including 0.

Ex.6) (i) Explain how the algorithm Sum_First_N_2 finds the sum of the first 3 natural numbers.

         (ii) Explain how the algorithm Sum_First_N_3 finds the sum of the first 3 natural numbers.

1.6.3 Procedure and Recursion

Though the above-mentioned three control structures, viz., direct sequencing, selection and repetition, are sufficient to express any algorithm, yet the following two advanced control structures have proved to be quite useful in facilitating the expression of complex algorithms viz.

(i) Procedure
(ii) Recursion

Let us first take the advanced control structure Procedure

1.6.3.1 Procedure

Among a number of terms that are used, in stead of procedure, are subprogram and even function. These terms may have shades of differences in their usage in different programming languages. However, the basic idea behind these terms is the same, and is explained next.

It may happen that a sequence frequently occurs either in the same algorithm repeatedly in different parts of the algorithm or may occur in different algorithms. In such cases, writing repeatedly of the same sequence, is a wasteful activity. Procedure is a mechanism that provides a method of checking this wastage.

Under this mechanism, the sequence of instructions expected to be repeatedly used in one or more algorithms, is written only once and outside and independent of the algorithms of which the sequence could have been a part otherwise. There may be many such sequences and hence, there is need for an identification of each of such sequences. For this purpose, each sequence is prefaced by statements in the following format:

..

where <name>, <parameter-list> and other expressions with in the angular brackets as first and last symbols, are place-holders for suitable values that are to be substituted in their places. For example, suppose finding the sum of squares of two variables is a frequently required activity, then we may write the code for this activity independent of the algorithm of which it would otherwise have formed a part. And then, in (1.6.3.1), <name> may be replaced by ‘sum-square’ and <parameter-list> by the two-element sequence x, y. The variables like x when used in the definition of an algorithm, are called formal parameters or simply parameters. Further, whenever the code which now forms a part of a procedure, say sum-square is required at any

is written, where values of a and b are defined before the location of the statement under (1.6.3.2) within the algorithm.

Further, the pair of brackets in [: < type >] indicates that ‘: < type >’ is optional. If the procedure passes some value computed by it to the calling program, then ‘: < type >’ is used and then <type> in (1.6.3.1) is replaced by the type of the value to be passed, in this case integer.

In cases of procedures which pass a value to the calling program another basic construct (in addition to assignment, read and write) viz., return (x) is used, where x is a variable used for the value to be passed by the procedure.

There are various mechanisms by which values of a and b are respectively associated with or transferred to x and y. The variables like a and b, defined in the calling algorithm to pass data to the procedure (i.e., the called algorithm), which the procedure may use in solving the particular instance of the problem, are called actual parameters or arguments.

Also, there are different mechanisms by which statement of the form
sum-square (a, b) of an algorithm is associated with the code of the procedure for which the statement is used. However, all these mechanisms are named as ‘calling the procedure’. The main algorithm may be called as the ‘calling algorithm’ and the procedure may be called ‘the called algorithm’. The discussion of these mechanisms may be found in any book on concepts of programming languages*.

In order to explain the involved ideas, let us consider the following simple examples of a procedure and a program that calls the procedure. In order to simplify the discussion, in the following, we assume that the inputs etc., are always of the required types only, and make other simplifying assumptions.

Example 1.6.3.1.1

Procedure sum-square (a, b : integer) : integer;

..

Program Diagonal-Length

{the program finds lengths of diagonals of the sides of right-angled triangles whose lengths are given as integers. The program terminates when the length of any side is not positive integer}

L1, L2: integer; {given side lengths} 

D: real;

{to store diagonal length}

 read (L1, L2)

 while (L1 > 0 and L2 > 0) do

begin

D<- square─root (sum-square (L1, L2)) write (‘For sides of given lengths’, L1, L2, ‘the required diagonal length is’ D); read (L1, L2); end.

* For the purpose Ravi Sethi (1996) may be consulted.

In order to explain, how diagonal length of a right-angled triangle is computed by the Elementary Algorithmics
program Diagonal-Length using the procedure sum-square, let us consider the side
lengths being given as 4 and 5.

First Step: In program Diagonal-Length through the statement read (L1, L2), we read
L1 as 4 and L2 as 5. As L1 > 0 and L2 > 0. Therefore, the program enters the
while-loop. Next the program, in order to compute the value of the diagonal calls the
procedure sum-square by associating with a the value of L1 as 4 and with b the value
of L2 as 5. After these associations, the procedure sum-square takes control of the
computations. The procedure computes S as 41 = 16 + 25. The procedure returns 41
to the program. At this point, the program again takes control of further execution.
The program uses the value 41 in place of sum-square (L1, L2). The program calls the
procedure square-root, which is supposed to be built in the computer system, which
temporarily takes control of execution. The procedure square-root returns value and also returns control of execution to the program Diagonal-Length which in turn assigns this value to D and prints the statement:

For sides of given lengths 4 and 5, the required diagonal length is root2 .

The program under while-loop again expects values of L1 and L2 from the user. If the
values supplied by the user are positive integers, whole process is repeated after
entering the while-loop. However, if either L1 <_ 0 (say ─ 34) or L2 <_ 0, then whileloop
is not entered and the program terminates.

We summarise the above discussion about procedure as follows:

A procedure is a self-contained algorithm which is written for the purpose of plugging
into another algorithm, but is written independent of the algorithm into which it may
be plugged.

1.6.3.2 Recursion

Next, we consider another important control structure namely recursion. In order to
facilitate the discussion, we recall from Mathematics, one of the ways in which the
factorial of a natural number n is defined:

factorial (1) = 1
factorial (n) = n* factorial (n─1).

For those who are familiar with recursive definitions like the one given above for
factorial, it is easy to understand how the value of (n!) is obtained from the above
definition of factorial of a natural number. However, for those who are not familiar
with recursive definitions, let us compute factorial (4) using the above definition.
By definition

factorial (4) = 4 * factorial (3).
Again by the definition
factorial (3) = 3 * factorial (2)
Similarly
factorial (2) = 2* factorial (1)
And by definition
factorial (1) = 1
Substituting back values of factorial (1), factorial (2) etc., we get
factorial (4) = 4.3.2.1=24, as desired.

This definition suggests the following procedure/algorithm for computing the factorial
of a natural number n:

In the following procedure factorial (n), let fact be the variable which is used to pass
the value by the procedure factorial to a calling program. The variable fact is initially
assigned value 1, which is the value of factorial (1).

                                  Procedure factorial (n)

fact: integer;
begin
fact <- 1
if n equals 1 then return fact
else begin
fact <- n * factorial (n ─ 1)
return (fact)
end;
end;

In order to compute factorial (n ─ 1), procedure factorial is called by itself, but this
time with (simpler) argument (n ─1). The repeated calls with simpler arguments
continue until factorial is called with argument 1. Successive multiplications of
partial results with 2,3, ….. upto n finally deliver the desired result.

Though, it is already mentioned, yet in view of the significance of the matter, it is
repeated below. Each procedure call defines a variables fact, however, the
various variables fact defined by different calls are different from each other. In
our discussions, we may use the names fact1, fact2, fact3 etc. However, if there is
no possibility of confusion then we may use the name fact only throughout.

Let us consider how the procedure executes for n = 4 compute the value of
factorial (4).

Initially, 1 is assigned to the variable fact. Next the procedure checks whether the
argument n equals 1. This is not true (as n is assumed to be 4). Therefore, the next
line with n = 4 is executed i.e.,

                    fact is to be assigned the value of 4* factorial (3).

Now n, the parameter in the heading of procedure factorial (n) is replaced by 3. Again
as n # 1, therefore the next line with n = 3 is executed i.e.,

fact = 3 * factorial (2)

On the similar grounds, we get fact as 2* factorial (1) and at this stage n = 1. The
value 1 of fact is returned by the last call of the procedure factorial. And here lies the
difficulty in understanding how the desired value 24 is returned. After this stage, the
recursive procedure under consideration executes as follows. When factorial
procedure is called with n = 1, the value 1 is assigned to fact and this value is
returned. However, this value of factorial (1) is passed to the statement fact <-2 *
factorial (1) which on execution assigns the value 2 to the variable fact. This value is
passed to the statement fact <-3 * factorial (2) which on execution, gives a value of 6
to fact. And finally this value of fact is passed to the statement fact<- 4 * factorial (3)
which in turn gives a value 24 to fact. And, finally, this value 24 is returned as value
of factorial (4).

Coming back from the definition and procedure for computing factorial (n), let us
come to general discussion.

Summarizing, a recursive mathematical definition of a function suggests the definition
of a procedure to compute the function. The suggested procedure calls itself
recursively with simpler arguments and terminates for some simple argument the
required value for which, is directly given within the algorithm or procedure.

Definition: A procedure, which can call itself, is said to be recursive procedure/algorithm. For successful implementation of the concept of recursive procedure, the following conditions should be satisfied.

(i) There must be in-built mechanism in the computer system that supports the calling of a procedure by itself, e.g, there may be in-built stack operations on a set of stack registers.
(ii) There must be conditions within the definition of a recursive procedure under which, after finite number of calls, the procedure is terminated.
(iii) The arguments in successive calls should be simpler in the sense that each succeeding argument takes us towards the conditions mentioned in (ii).

In view of the significance of the concept of procedure, and specially of the concept of recursive procedure, in solving some complex problems, we discuss another recursive algorithm for the problem of finding the sum of first n natural numbers, discussed earlier. For the discussion, we assume n is a non-negative integer

..

Ex.7) Explain how SUM (5) computes sum of first five natural numbers.