CA4CRT10-DESIGN & ANALYSIS OF ALGORITHMS Module1

INTRODUCTION TO ALGORITHM
Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to
get the desired output. Algorithms are generally created independent of underlying languages, i.e. an
algorithm can be implemented in more than one programming language.
Characteristics of an Algorithm
 Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their
inputs/outputs should be clear and must lead to only one meaning.

 Input − An algorithm should have 0 or more well-defined inputs.

 Output − An algorithm should have 1 or more well-defined outputs, and should match the desired
output.
 Finiteness − Algorithms must terminate after a finite number of steps.

 Feasibility − Should be feasible with the available resources.

 Independent − An algorithm should have step-by-step directions, which should be independent of
any programming code.
Steps in algorithm/ study of algorithm

How to design algorithm

Creating an algorithm is art which may never be fully automated.
How to validate algorithm
Once an algorithm is designed, it is necessary to show that it computes the correct answer for all possible
inputs.
How to analyse algorithms
Analysis of algorithms refers to the task of determining how much computing time and storage an algorithm
requires.

How to test a program

It consists of two methods:
1. Debugging: it is the process of executing programs on sample data set to determine whether faculty
results occurs and if so to correct them.
2. Profiling or performance measurement: It is the process of executing a correct program on data sets
and measuring the time and space it takes to compute the results.
PERFORMANCE ANALYSIS

 Performance of an algorithm is a process of making evaluative judgement about algorithms.

 Performance of an algorithm means predicting the resources which are required to an algorithm to
perform its task.
 Performance analysis of an algorithm is the process of calculating space and time required by that
algorithm.

Performance analysis of an algorithm is performed by using the following measures...

1. Space required to complete the task of that algorithm (Space Complexity). It includes program space
and data space
2. Time required to complete the task of that algorithm (Time Complexity)
Space complexity
Department of computer science
1 SAC, Peruvanthanam
CA4CRT10-DESIGN & ANALYSIS OF ALGORITHMS Module1

When we design an algorithm to solve a problem, it needs some computer memory to complete its execution.
For any algorithm, memory is required for the following purposes.

1. To store program instructions.

2. To store constant values.
3. To store variable values.
4. And for few other things like function calls, jumping statements etc,
Space complexity of an algorithm can be defined as follows...
Total amount of computer memory required by an algorithm to complete its execution is called as space
complexity of that algorithm
Generally, when a program is under execution it uses the computer memory for THREE reasons. They are as
follows...

1. Instruction Space: It is the amount of memory used to store compiled version of instructions.
2. Environmental Stack: It is the amount of memory used to store information of partially executed
functions at the time of function call.
3. Data Space: It is the amount of memory used to store all the variables and constants.
The space needed by an algorithm is the sum of fixed components and variable component
Fixed component: this consists of space needed by variables, constants, instruction space.
Variable component: this consist of the space needed by referenced variables and recursion stack space.
Example: 1
Algorithm abc (a,b,c)
{
Return ((a+)/c+5));
}
The space needed for variable ‘a’ is 1 unit.

The space needed for variable ‘b’ is 1 unit.

The space needed for variable ‘c’ is 1 unit.
Therefore, the space complexity is 3 units.
Example: 2

Algorithm sum (a[ ], n)

{
s=0;

for(i=1;i<=n;i++)
s=s+a[i];
return s

}
The space needed for a[ ] is n units.

Department of computer science

2 SAC, Peruvanthanam
CA4CRT10-DESIGN & ANALYSIS OF ALGORITHMS Module1

The space needed for n is 1 unit

The space needed for s is 1 unit.
The space needed for I is 1 unit.
Therefore, the space complexity is n+3 units.

Time complexity
It is the amount of computing time needed to run to completion. The time taken by a program is the sum of
compile time and execution time. The following factors effect the time complexity of an algorithm:
1. Characteristics of compiler used to compile the program.
2. Computer machine on which the program is executed and physically clocked.
3. Multiuser execution system.
4. Number of program steps.

Example: step count method

In this method, we count the number of times one instruction is executing.

Statement Step/execution Frequency Total steps

Algorithm sum (a[ ], n)
0 0 0
{
0 0 0
s=0;
1 1 1
for(i=1;i<=n;i++)
1 n+1 n+1
s=s+a[i];
1 n n
return s
1 1 1
}
0 0 0
Total 2n+3

Rules for step count method:

1. For assignment and return statements step count is 1.
2. For comments and declarations, the step count is 0;
The steps per execution of a statement is the amount by which the count changes as a result of the execution
of that statement.
We can calculate the time complexity of an algorithm by using three methods:
1. Worst case time complexity
2. Average case time complexity
3. Best case time complexity
Consider the following program for linear search
Int search (int a[ ],int n, int x)

{
Int I;
For(i=0;i<n;i++)

{
If(a[i]==x)
Return I;

Department of computer science

3 SAC, Peruvanthanam
CA4CRT10-DESIGN & ANALYSIS OF ALGORITHMS Module1

}
Return -1;
}
Worst case time complexity

It is the function defined by maximum number of steps taken on any input of size n.
Example:
For linear search the worst case happens when the element to be searched is not present in the array in the
last position of the array.

The worst-case time complexity of linear search is O(n).

Average case time complexity
It is the function defined by an average number of steps taken on any input of size n.

If the element to be searched is in the middle of the array then the average number of comparison is n/2.
Best case time complexity
It is function defined by the minimum number of steps taken on any input of size n;
In the linear search problem, the best case occurs when the element to be searched is present at the first
position.

ALGORITHM DESIGN TECHNIQUES

Algorithm design techniques refer to the methods and strategies used to develop efficient and
effective algorithms for solving computational problems. These techniques help algorithm designers create
algorithms that are correct, optimal, and scalable.

Divide and Conquer Method

In the divide and conquer approach, the problem is divided into several small sub-problems. Then the sub-
problems are solved recursively and combined to get the solution of the original problem.

The divide and conquer approach involve the following steps at each level −

 Divide − The original problem is divided into sub-problems.

 Conquer − The sub-problems are solved recursively.
 Combine − The solutions of the sub-problems are combined together to get the solution of the original
problem.

The divide and conquer approach are applied in the following algorithms –

Binary search, Quick sort, Merge sort

Greedy Method

Department of computer science

4 SAC, Peruvanthanam
CA4CRT10-DESIGN & ANALYSIS OF ALGORITHMS Module1

In greedy algorithm of optimizing solution, the best solution is chosen at any moment. A greedy algorithm is
very easy to apply to complex problems. It decides which step will provide the most accurate solution in the
next step.

This algorithm is a called greedy because when the optimal solution to the smaller instance is
provided, the algorithm does not consider the total program as a whole. Once a solution is considered, the
greedy algorithm never considers the same solution again.

A greedy algorithm works recursively creating a group of objects from the smallest possible
component parts. Recursion is a procedure to solve a problem in which the solution to a specific problem is
dependent on the solution of the smaller instance of that problem.

Example: Knap sack problem

Dynamic Programming

Dynamic programming is an optimization technique, which divides the problem into smaller sub-problems
and after solving each sub-problem, dynamic programming combines all the solutions to get ultimate
solution. Unlike divide and conquer method, dynamic programming reuses the solution to the sub-problems
many times.

Example: multistage graph, travelling sales man problem

Backtracking Algorithm

Backtracking is an optimization technique to solve combinational problems. It is applied to both

programmatic and real-life problems. Eight queen problem, Sudoku puzzle and going through a maze are
popular examples where backtracking algorithm is used.

In backtracking, we start with a possible solution, which satisfies all the required conditions. Then we move
to the next level and if that level does not produce a satisfactory solution, we return one level back and start
with a new option.

Branch and Bound

A branch and bound algorithm is an optimization technique to get an optimal solution to the problem. It looks
for the best solution for a given problem in the entire space of the solution. The bounds in the function to be
optimized are merged with the value of the latest best solution. It allows the algorithm to find parts of the
solution space completely.

The purpose of a branch and bound search is to maintain the lowest-cost path to a target. Once a solution is
found, it can keep improving the solution. Branch and bound search are implemented in depth-bounded
search and depth–first search.
Department of computer science
5 SAC, Peruvanthanam