THE ART OF PROGRAMMIMG METHODOLOGY

ALGORITHM DESIGN

Dear friends,

In Today’s discussion we will talk about very useful

and most frequently used feature of Programming- i.e.,
Algorithm analysis and design. Before solving a problem
using some programming language, first we create a step by
step procedure to solve the problem. I.e., an algorithm. We
can discuss what an algorithm is.

Algorithm

The term algorithm is used in computer science to describe

a finite, deterministic, and effective problem-solving method
suitable for implementation as a computer program.
Algorithms are the stuff of computer science: they are
central objects of study in the field for providing solutions to
programming problems. An algorithm is a well-defined pro-
cedure, consisting of a number of instructions that are exe-
cuted in turn in order to solve the given problem.
Normally, an algorithm will have certain inputs; for
each input, the algorithm should compute an output which is
related to the input by certain input-output relation. Formulat-
ing an algorithm makes problem-solving decidedly harder,
because it is necessary to formulate very clearly and pre-
cisely the procedure for solving the problem. The more gen-
eral the problem, the harder it gets. The advantage, how-
ever, is a much greater understanding of the solution. The
process of formulating an algorithm demands a full under-
standing of why the algorithm is correct.
Algorithm is a sequential solution of any program that
is written in natural language. Algorithm is the first step of
finding solution for a problem. After the analysis of a
problem, we can write the algorithm of that particular
problem.

Qualities of a good algorithm

1. Inputs and outputs should be defined precisely.

2. Each steps in algorithm should be clear and
unambiguous.
3. Algorithm should be most effective among many
different ways to solve a problem.
4. An algorithm shouldn't have a computer code.
Instead, the algorithm should be written in such a
way that, it can be used in similar programming
languages.

Algorithm design

The development of an algorithm or a plan is a key

step in solving a problem. Once we have an algorithm, we
can translate it into a computer program in any programming
language.

Let us start learning how to write an algorithm. For this

consider a simple problem of making coffee. To write an
algorithm we should understand the requirements to solve
an algorithm. Here the requirements include coffee powder,
sugar, water, etc. The algorithm should be designed in such
a way that it indicates the order in which these requirements
(ingredients in this example), are to be presented and mixed
for solving the problem. So the algorithm is as follows:

Algorithm 1:
Making Coffee –
This algorithm will describe how to make coffee

Step 1: Start
Step 2: Get a teapot, whose size depends on, for many
people you are making the coffee for.
Step 3: Pour water into the pot until the pot is almost filled
with water.
Step 4: Put the pot on the stove and turn the stove on.
Step 5: Let the water in the pot boil for five minutes.
Step 6: Get the coffee powder, sugars and milk as you like
and put them into the boiling pot.
Step 7: Now boil for another one minute.
Step 8: Turn off the stove and remove the pot from the
stove.
Step 9: Now the coffee is ready, enjoy it (stop).
Let us consider another example of algorithm to check
whether the given number is even or odd.

Algorithm 2:
Find even or odd - this algorithm will find whether a given
number is even or odd.
num is the input number, rem is the reminder of a given
number.
Step 1: start
Step 2: input num
Step 3: rem=num mod 2
Step 4: if the rem=0 then
“Given num is even"
Other wise
"Given num is odd"
Step 5: stop

Three reasons for using algorithms are efficiency,

abstraction and reusability.
 Efficiency: Certain types of problems, like sorting, occur
often in computing. Efficient algorithms must be used to
solve such problems considering the time and cost factor
involved in each algorithm.
 Abstraction: Algorithms provide a level of abstraction in
solving problems because many seemingly complicated
problems can be distilled into simpler ones for which
well-known algorithms exist.
 Reusability: Algorithms are often reusable in many
different situations.

Algorithmic Problem Solving

1. Understanding the problem:

The problem given should be understood completely. Check

if it is similar to some standard problems & if a Known
algorithm exists. Otherwise a new algorithm has to be
devised.

2. Ascertain the capabilities of the computational

device:
Once a problem is understood we need to know the
capabilities of the computing device this can be done by
knowing the type of the architecture, speed & memory
availability.

3. Exact /approximate solution

Once algorithm is devised, it is necessary to show that it

computes answer for all the possible legal inputs.

4. Decide on the appropriate data structure:

A data type is a well-defined collection of data with a well-

defined set of operations on it. A data structure is an actual
implementation of a particular abstract data type. The
Elementary Data Structures are arrays, records and sets.

5. Algorithm design techniques:

There are some important design techniques like linear, non-

linear, dynamic, integer programming, etc. Using these
existing design strategies we devise new and useful
algorithms

6. Proving an algorithms correctness:

Once algorithm is devised, it is necessary to show that it

computes answer for all the possible legal inputs .We refer
to this process as algorithm validation. The process of
validation is to assure us that this algorithm will work
correctly independent of issues concerning programming
language it will be written in.

7. Analyzing algorithms:

As an algorithm is executed, it uses the computers central

processing unit to perform operation and memory to hold the
program and data. Analysis of algorithms and performance
analysis refers to the task of determining how much
computing time and storage an algorithm requires. This is a
challenging area which requires mathematical skill.

Top down Design

When we use a computer to solve a problem, we can use

many possible approaches. For small problems, it hardly
matters which approach we use, as long as we have one
that correctly solves the problem. For huge problems (or
applications where we need to solve huge numbers of small
problems), however, we quickly become motivated to devise
methods that use time and space efficiently.

The idea behind a top down design is to first divide the prob-
lem into a small number of broad subtasks. We call the initial
level as top level, main module, or level 0. The number of
subtasks at this point should be small, as shown in the fig-
ure. For most programs, we would expect three to seven
subtasks at this level. The subtasks of each level can be
again subdivided into smaller modules by repeating the
process of division. Most often, for each of the subtasks at
level 0, we will start a new module at level 1.

Let us consider an example of top down approach of

problem solving
Problem: Write a program that draws the picture of a
house
Fundamental algorithms

In general algorithms are the major tool for problem solving.

Some of the fundamental algorithms for different type of
searching and sorting are going to be discussed.

Searching algorithms are used for finding specific items

among large collections of items. There are basic and
advanced methods for searching, including binary search
trees, balanced search trees, and hashing. All these
approaches are used to perform searching for the specified
element in a given list. Linear searching starts searching for
the item from the beginning of the list and continues till the
end of the list until the item is found. The Binary Search
Algorithm follows the Divide and Conquer strategy where in,
it finds the item from the sorted list of items.

Let us consider the Linear Search approach as the first and

basic example for searching. Linear search searches an
element or value from an array till the desired element or
value is not found and it searches in a sequence order. It
compares the element with all the other elements given in
the list and if the element is matched it returns the value
index else it return -1. Linear Search is applied on the
unsorted or unordered list when there are fewer elements in
a list.

Algorithm 3:
Linear Search
A linear array DATA with N elements and specific ITEM of
information are given. This algorithms finds the location LOC
Step 1: [initialize] set k=1 and LOC: =0
Step 2: Repeat step 3and 4 while LOC: =k and k<=N
Step 3: IF ITEM=DATA[k], Then: Set LOC: =k
Step4: Set K=k+1[increment counter]
[End of Step 2 Loop]
Step 5: [Successful?]
IF LOC=0, then
Write: ITEM is not in the array DATA
ELSE
Write: LOC is the location of ITEM
[End of if structure]
Step 6: Exit

Let us consider another important searching method,

named binary search.
Binary search searches a particular item by comparing the
middle most item of the collection. If match occurs then
index of item is returned. If middle item is greater than item
then item is searched in sub-array to the right of the middle
item otherwise item is search in sub-array to the left of the
middle item. This process continues on sub-array as well
until the size of sub array reduces to zero.

Algorithm 4:
Binary Search
BINARY (DATA, LB, UB, ITEM, LOC)
Here DATA is a stored array with lower bound
LB and upper bound UB, and ITEM is a given item of
information. The Variables BEG, END and MID denote,
respectively, the beginning, end and middle location of a
segment of elements of DATA. This algorithm find the
location LOC of ITEM in DATA or sets LOC=NULL.
Step 1: [Initialize segment variables.]
Set BEG=LB, END = UB and MID =
INT((BEG+END)/2).
Step 2: Repeat Step 3 and 4 while BEG<= END and
DATA[MID] ≠ ITEM
Step 3: if ITEM < DATA[MID], then:
Set END=MID-1.
 Else:
Set BEG = MID+1.
Step 4: Set MID = INT ((BEG+END)/2)
Step 5: If DATA[MID] = ITEM then:
Set LOC = MID
Else:
Set LOC =NULL
Step 6: Stop.

Remark: Whenever ITEM does not appear in DATA, the

algorithm eventually arrives at the stage that
BEG=END=MID. Then the next step yield END<BEG, and
control transfers to step 5 of the algorithm.

Sorting algorithms are used for rearranging arrays in order

are of fundamental importance. There are a variety of
algorithms in considerable depth, including insertion sort,
selection sort, shellsort, quicksort, mergesort, and heapsort.

Let us discuss some basic sorting methods. Ie, the process

of sorting given elements in a particular order. Number of dif-
ferent sorting methods are available like Bubble Sort, Selec-
tion Sort, Merge Sort and Quick Sort etc.
Bubble Sort repeatedly sorts the adjacent elements if
they are in wrong order. The Selection Sort finds the
smallest element in the array and exchanges it with the
element in the first position, it then finds the second smallest
element and exchanges it with the element in the second
position and continues this process until the entire list is
sorted. The Merge Sort follows the Divide and Conquer rule
where in it divides the input array into two halves, sorts the
two halves and merges the two sorted halves. The Quick
Sort selects an element as a pivot and partitions the given
array around the pivot.
In the following section we are going to discuss the
algorithm of Bubble sort in detail.

Bubble sort or sinking sort is one of the simplest

forms of sorting that compares each item with every other
item in some list. The bubble sort makes multiple passes
through a list. It compares adjacent items and exchanges
those that are out of order. Each pass through the list places
the next largest value in its proper place. In essence, each
item “bubbles” up to the location where it belongs.

Let A be a list of n Numbers. Sorting A refers to the

operation of rearranging the elements of A so that they are in
increasing order ie, A[1]<A[2]<A[3]<…<A[N]
For example, suppose the original list A is,
4,5,1,8,20,15,90
After sorting A, the list is
1,4,5,8,15,20,90
Suppose the list of numbers A[1], A[2], … ,A[N] is in memory.
The bubble sort algorithm works as follows:
Algorithm 5:
Bubble sort
A[1], A[2], … ,A[N] is the list of numbers

Step 1: Compare A[1] and A[2] an arrange them in the

desired order, so that A[1]<A[2].
Then Compare A[2] and A[3] arrange them so that
A[2]<A[3].
Then Compare A[3] and A[4] and arrange them so
that A[3]<A[4].
Continue this until we compare A[N-1] with A[N] and
arrange them so that
A[N-1]<A[N].
[step 1 involves n-1 comparison and when Step 1 is
completed, A[N] will contain the largest element]
Step 2: Repeat step 1 with one less comparison; that is now
we stop after we compare and possibly arrange
A[N-2] and A[N-1].
[Step 2 involves N-2 comparisons and, when step 2 is
completed, the second largest element will occupy A[N-1] ]
Step 3: Repeat Step 1 with fewer comparisons; that is, we
stop after we compare and possibly rearrange A[N-3]
and A[N-2].
.

……………………………………………………………………
……………………..
 .

……………………………………………………………………
……………………..
.

……………………………………………………………………
……………………..
Step N-1: Compare A[1] with A[2] and arrange them so that
A[1]<A[2].
[After n-1 steps, the list will be stored in increasing order.]

Summary
Algorithm is a sequential solution for any program
and which is written in human language or natural language.
Algorithm is the basic way or approach to easily handle a
given problem. After implementing algorithm for a given
problem it can be easily converted into computer programs
on any programming language. The next section describes
the top down approach of problem solving. The idea behind
a top down design is to first divide the problem into a small
number of broad subtasks. At the end of this module we
discussed some basic algorithms for searching and sorting,
and specifically we studied the algorithms for linear search,
binary search and the bubble sort.

Assignments

 Explain the algorithm.

 Write an algorithm to find the greater of two numbers.
 Illustrate the top down approach of an algorithm
 What are the steps for writing an algorithm?
 Write an algorithm for searching an element.

Reference

 B. W. Kernighan and D. M. Ritchie, The C

Programming Language, Prentice-Hall, Englewood
Cliffs, New Jersey, 1978.
 Greg Perry, Absolute Beginners' guide to C 2nd
 Edition, SAMS publishing, A division of Prentice Hall
Computer Publishing, 201 West 103rd Street ,
Indianapolis, Indiana 46290. April 1994.
 Yashavant Kanetkar; Let us C, BPB Publications,
New Delhi.
 Data structures with c,Seymour Lipchitz