Steps in Designing an Algorithm

1. Understanding the Problem

The problem given should be understood completely.

Check if it is similar to some standard problems & check

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. Deciding Data Structures

Data Structures play a vital role in designing & analyzing

the algorithms.

Some of the algorithm design techniques also depend on

the structuring data specifying a problem’s instance.
 Ex. : Array, Stack, Queue, Linked List, Tree, Graph, etc.

5. Algorithm Design Techniques

By mastering these design strategies, it will become

easier for you to devise new & useful algorithms.

Ex. : Greedy technique, Divide & Conquer approach,

Dynamic Programming.

6. Prove Correctness

Correctness has to be proved for every algorithm.

For some algorithms, a proof of correctness is quite easy;

for others it can be quite complex.

A technique used for proving correctness by

mathematical induction because an algorithm’s iterations
provide a natural sequence of steps needed for such
proofs.

But we need one instance of its input for which the

algorithm fails.

If it is incorrect, redesign the algorithm, with the same

decisions of data structures, design techniques, etc.

7. Analyze the Algorithm

 There are 2 kinds of Algorithm efficiency : Time and
Space efficiency.
Time efficiency indicates how fast the algorithm runs.

Space efficiency indicates how much extra memory the

algorithm needs.

8. Coding

Programming the algorithm by using some programming

language. Formal verification is done for small
programs.

Validity is done by testing & debugging.

Inputs should fall within a range & hence require no

verification.

Some compilers allow code optimization which can

speed up a program by a constant factor whereas a better
algorithm can make a difference in their running time.

Example : Algorithm for Binary Search

Step 1 : Initialize variables low, high & target.
Step 2 : Obtain the input values.
Step 3 : Calculate Midpoint
Find the Midpoint of the array using the formula :
Mid = (low + high) / 2.
Step 4 : Compare Mid to Target.
If array[Mid] == Target, the Target element is found, so,
return the index of the Mid.
If array[Mid] < Target, the Target element must be in the right
half of the array. Set low = Mid + 1.
If array[Mid] > Target, the Target element must be in the left
side of the array, set high = Mid – 1.
Step 5 : Repeat steps 3 – 4 until either the Target element is
found (or) low > high.
Step 6 : Return the result.
If the Target element was found, return the index Mid.
If the Target element was not found, return -1, to indicate that
the element is not present in the array.
Problem : Given this problem, that is the problem of finding
Binary Search.
1. Understand the problem.
2. Find the capabilities of the computing device.
3. This algorithm will give you an exact solution.
4. Decide on Data Structures.
 Data Structure – Array
 Design Technique – Divide & Conquer approach.
 Space Complexity – O(log n) for recursive
approach, O(1) for iterative approach.
 Time Complexity is O(1).

5. Decide on the algorithmic technique, design technique

needed for Binary Search algorithm is Divide and
Conquer.
 6. Analysing the algorithm.
While analyzing the algorithm you have to determine the
Time Complexity and Space Complexity.
Space Complexity : O(1) for Iterative approach.
O(log n) – Recursive approach
Because less variables are required & these variables
needs constant space.

Time Complexity is O(1).

Sorting : Sorting problem asks us to rearrange the items of a

given list in ascending order.
As a particular matter, we usually need to sort lists of
numbers, characters from an alphabet, character strings &
most important records similar to those maintained by schools
about their students, libraries about their holdings &
companies about their employees.
In this case of records, we need to choose a piece of
information to guide Sorting.
For example, we can choose to sort student records in
alphabetical order of names (or) by student number (or) by
student GPA.
Such a specially chosen piece of information is called a Key.
Why would we want a Sorted list?
Sorting makes many questions about the list easier to answer.
The most important of them is Searching.
It is why Dictionaries, Telephone books, class lists & so on
are sorted.
There are a few good Sorting algorithms that sort an arbitrary
array of size n, using about nlog n comparisons.
2

On the other hand, no algorithm that sorts by key comparisons

[as opposed to say comparing small pieces of keys] can do
substantially better than that.
Some of the sorting algorithms are simple but relatively slow
while others are faster but more complex, some work better
on randomly ordered inputs while others do better on almost
sorted lists. Some are suitable only for lists residing in the fast
memory while others can be adapted for sorting large files
stored on a disk & so on.
A sorting algorithm is called Stable, if it preserves the relative
order of any 2 equal elements in its input.
In other words, if an input list contains two equal elements in
positions i and j where i < j, then the sorted list they have to
be in positions i’ & j’ respectively such that i’ < j’.
This property can be desirable if, for example we have a list
of students sorted alphabetically & we want to sort it
according to student GPA; a stable algorithm will yield a list
in which students with the same GPA will still be sorted
alphabetically.
Searching : The Searching problem deals with finding a
given value, called a search key in a given set [or a multiset,
which permits several elements to have the same value.]
There are plenty of searching algorithms to choose from.
They range from the straight forward sequential search to a
spectacularly efficient but limited binary search & algorithms
based on representing the underlying set in a different form
more conducive to searching.
Some algorithms works faster than others but require more
memory, some are very fast but applicable only to sorted
arrays.
Specifically, in applications where the underlying data may
change frequently relative to the no. of searches. Searching
has to be considered in conjunction with 2 other operations:
addition to & deletion from the data set of an item.
String Processing : A String is a sequence of characters
from an alphabet.
Strings of particular interest are text strings, which comprise
letters, numbers & special characters; bit strings which
comprise 0’s and 1’s & gene sequences, which can be
modeled by strings of characters from the 4 – character
alphabet {A, C, G, T}.
It should be pointed out, however, that string – processing
algorithms have been important for Computer Science for a
long time in conjunction with Computer languages &
compiling issues.
Graph Problems : A graph can be thought of as a collection
of points called vertices, some of which are connected by line
segments called edges.
Graphs can be used for modeling a wide – variety of real –
life applications including transportation & communication
networks project scheduling & games.
Basic graph algorithms include graph traversal algorithms,
shortest – path algorithms & topological sorting for graphs
with directed edges.
Some graph problems are computationally very hard; the most
well – known examples are the traveling salesman problem &
the graph – coloring problem.
The Traveling Salesman Problem [TSP] is the problem of
finding the shortest tour through n cities that visits every city
exactly once.
The graph – coloring problem asks us to assign the smallest
number of colors to vertices of a graph, so that no 2 adjacent
vertices are the same color.
Combinatorial Problems : The Traveling Salesman Problem
[TSP] & the graph – coloring problem are examples of
combinatorial problem.
These are problems that ask [explicitly or implicitly] to find a
combinatorial object such as a permutation, a combination
(or) a subset - that satisfies certain constraints & has some
desired property [e.g., maximizes a value or minimizes a
cost].
Generally, Combinatorial problems are the most difficult
problems in computing from both the theoretical & practical
standpoints.
Their difficulty stems from the following facts :
1. The number of combinatorial objects typically grows
extremely fast with a problem’s size, reaching
unimaginable magnitudes even for moderate – sized
instances.
2. There are no known algorithms for solving most such
problems exactly in an acceptable amount of time.