6 Programming and Data Structures
easy to solve a given problem. Every step is known as an instruction.
In our daily life we come across numerous algorithms for solving problems. We perform several
routine tasks, for example, riding a bike, lifting a phone, making a telephone call, switching on the
television, and so on.
Let us take an example. To establish a telephonic communication between two subscribers the
following steps are to be followed.
1) Dial the phone number
2) Phone rings at the called party
3) Caller waits for the response
4) Called party picks up the phone
5) Conversation begins between them
6) Release of connection
Another real life example is accessing the Internet through an Internet Service Provider with dial up
facility. To log on to the Internet the following steps are to be followed.
1) Choose the Internet Service Provider for accessing the Internet
2) Obtain from service provider a dial up number
3) Acquire IP address of the service provider
4) Acquire login ID and password
5) Run the Internet browsing software
Analyzing algorithm: When one writes an algorithm, it is essential to know how to analyze the
algorithm. Analyzing an algorithm refers to calculating or guessing resources needed for that
algorithm. Resources means computer memory, processing time, logic gates and so on. In all the
above factors, time is most important because the program developed should be faster in processing.
The analysis can also be made by reading the algorithm for logical accuracy, tracing the algorithm,
implementing it, checking with some data and with some mathematical technique to confirm its
accuracy.
Algorithms can also be expressed in a simple method. It will help the user to put it into operation
easily However, this approach has a few drawbacks. It requires more space and time. It is very
essential to consider factors such as time and space requirements of an algorithm. With minimum
system resources such as CPU time and memory, an efficient algorithm must be developed.
Rate of growth: In practice, it is not possible to act upon a simple analysis of an algorithm to conclude
the execution time of an algorithm. The execution time is dependent upon the machine and the way
of implementation. Timing analysis depends upon the input required. To accurately analyze the
time it is also very essential to know the exact directives executed by the hardware and the execution
time passed for each statement.
Classification of Algorithm s
Algorithm can be classified into three types. The classification of an algorithm is based on repetitive
steps and based on control transfer from one statement to another.
Based on repetitive steps, an algorithm can be classified into two types.
1) Direct algorithm
2) Indirect algorithm
1) Direct algorithm: In this type of algorithm the number of iterations is known in advance.
For example, for displaying numbers from 1 to 10, the loop variable should be initialized from
Program Development Styles and Basics of C 7
1 to 10. The statement would be as follows:
for (j=l/j<=10,j++)
In the above statement, it is predicted that the loop will iterate for ten times.
2) Indirect algorithm: In this type of algorithm repetitive steps are executed a number of times.
Exactly how many repetitions are to be made is unknown.
For example, finding the first five Armstrong numbers from 1 ton, where n is the fifth Armstrong
number and finding the first three palindrome numbers.
Based on control transfer the algorithms are classified into the following three types.
a) Deterministic
b) Non-deterministic
c) Random
a) Deterministic: A deterministic algorithm is based on either following a 'yes' path or a 'no' path
based on the condition. In this type of algorithm when control logic comes across a decision symbol,
two paths 'yes' and 'no' are shown. Program control follows one of the routes depending upon the
condition.
The examples include testing whether a number is even or odd or positive or negative.
b) Non-deterministic: In this type of algorithm, we have one of the multiple paths to reach to the
solution.
Example Finding a day of a week.
c) Random: After executing a few steps, the control of the program transfers to another step randomly
in a random algorithm.
Example Random search.
Many a time, we have to follow one more algorithm in which the exagt number of iterations is not
known. Best estimation has to be done in order to get better results. More iterations are expected in
this case.
3) Infinite algorithm: This algorithm is based on better estimates of results. The number of steps is
unknown. The process will be continued until best results are achieved.
Example, finding shortest paths from a given source to all destinations in the network.
Fig. 1.4 Classifications of algorithms
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.