Algorithm

Design & Analysis

 UNIT – I
• Introduction: Algorithm, Performance Analysis-
Space complexity, Time complexity, Asymptotic
Notations- Big oh notation, Omega notation,
Theta notation and Little oh notation.
• Divide and conquer: General method,
applications-Binary search, Quick sort, Merge
sort, Strassen’s matrix multiplication
 UNIT - II
• Disjoint Sets: Disjoint set operations, union
and find algorithms

• Backtracking: General method, applications,

n-queen’s problem, sum of subsets
problem, graph coloring
 UNIT - III
• Dynamic Programming:

General method, applications- Optimal binary

search trees, 0/1 knapsack problem, All pairs
shortest path problem, Traveling sales person
problem, Reliability design.
 UNIT-IV
• Greedy method:
General method, applications-Job sequencing
with deadlines, knapsack problem, Minimum
cost spanning trees, Single source shortest
path problem.
 UNIT – V
• Branch and Bound: General method,
applications - Travelling sales person problem,
0/1 knapsack problem - LC Branch and Bound
solution, FIFO Branch and Bound solution.

• NP-Hard and NP-Complete problems: Basic

concepts, non deterministic algorithms, NP -
Hard and NP-Complete classes, Cook’s
theorem.
 Introduction to Algorithms
• History:

The word algorithm comes from the name of a

Persian author, Abu Mohammed al
Khowarizmi, who wrote a textbook on
mathematics.
 Definition
• An algorithm is a finite sequence of
instructions that, if followed, accomplishes a
particular task or Computational problem.

• In other words Algorithm is step by step

procedure to solve a particular problem.
 Characteristics of an Algorithm
• Input. Zero or more quantities are externally
supplied.
• Output. At least one Output is produced.
• Definiteness. Each instruction is clear and unambiguous.
• Finiteness. The algorithm terminates after a finite number of
steps.
• Effectiveness. Every instruction must be very basic enough
and must be feasible
 Process for design and Analysis of
Algorithm
• The main steps for Problem Solving are:
1. Problem definition
2. Requirements
3. Algorithm design /logic
[Link] Correctness
[Link] Specification
5. Algorithm analysis
6. Implementation
7. Testing/Debugging
 Algorithm Specification
• Natural Language

• Flowchart

• Pseudo code
 Pseudo code
• Pseudo code: High-level description of an
algorithm.
• More structured than plain English.
• Less detailed than a program.
• Preferred notation for describing algorithms.
• Hides program design issues.
 The general procedure for writing pseudo code
is presented below
Comments
Blocks
Identifiers
Assignment
Operators
Arrays
Control statement
Input and output
Procedure
Comments:
 Non executable statements
 Improves the readability of algorithm
 Begins and ends with ”/ /” Single line.
Blocks:
A group of statements (compound statements) are enclosed with
{ and } for example if statement, while loop, functions etc.,.
• Example
{
Statement 1;
Statement 2;
.........
.........
}
Identifiers:
 These are the names given to the elements in the particular
algorithm.
 An identifier begins with a letter.

Example: sum,sum5, a;
but not in 5sum, 4a etc.,.

• Assignment:
Assigning the value to a variable.
Assignment of values to the variables is done using
the assignment operators as := or
variable name := value;
len:=100;
Operators:
• Arithmetic operators: +, -, *, /, %;
• Relational operators: <, > , >= , <=, =.
• There are two Boolean values TRUE and FALSE.
• Logical operators: AND, OR, NOT.

Arrays:
one dimensional array
a[3]=10;
Two dimensional array
arr[2,3]=25;
Control Structures
1. Branching(if , if then else, case)

[Link] (while, for, repeat until)

if then , if then else

• if (condition) then (statement)
• if (condition) then (statement-1) else (statement-2).

Example
if(a>b) then
{
write("a is big");
}
else
{
write("b is big");
}
Case statement
case
{
:(condition -1): (statement-1)
:(condition -2): (statement-2)
:(condition -n): (statement-n)
..............
..............
else: (statement );
}
Loop statements:
• For loop:
• The general form of the for loop is

• for variable:=value 1 to value n step do

• {
• Statement -1;
• Statement -2;
• .......
• .......
• Statement -n;
 Loop statements
For loop:

for variable:=value 1 to value Example:

n step do for i:=1 to 10 do
{ {
Statement -1; write(i); //displaying numbers
Statement -2; from 1 to 10
....... i:=i+1;
....... }
Statement -n;
}
 While loop:
The general form of the while loop is

while <condition> do Example:

{ i:=1;
<statement 1> while(i<=10)do
<statement 2> {
........ write (i);//displaying numbers
........ from 1 to 10
<statement n> i:=1+1;
} }
 Repeat-until loop:

repeat Example
{ i:=1;
<statement 1> repeat
<statement 2> {
...... write (i); i:=i+1;
...... }
<statement n> until (i>10);
}until <condition>
 Procedures (functions):

• There is only one type of procedure:

• An algorithm consists of a heading and a body.

procedure name of the procedure

Algorithm Name (<parameter list>)

{
body of the procedure
}
 Example
• Write an algorithm to find sum of n numbers

Algorithm sum(n)
{
total:=0;
for i:=0 to n do
total:=total+1;
i=i+1;
}
 Assignment
• Write an algorithm for swapping of 2
numbers.

• Write an algorithm to perform multiplication

of 2 matrices.
• Write an algorithm for swapping of 2
numbers.

Algorithm swap(a,b)
{
temp:=a;
a:=b;
b:=temp;
}
Write an algorithm to perform multiplication of 2
matrices.

Algorithm Multiplication (A, B, n)

{
C[i,j]:=0;
for i:=1 to n do
for j:=1 to n do
for k:=1 to n do
C[i,j]:=C[i,j]+A[i,k]*B[k,j];
}
 Performance Analysis/Analysis of an
Algorithm
• Performance analysis is refers to the task of
determining the efficiency of an Algorithm.
• i.e how much computing time and storage an
Algorithm requires to run(execute).

• Space complexity

• Time complexity
 Space Complexity
• The space complexity of an algorithm is the
amount of memory it needs to run to
completion.
• The space need by an algorithm has following
components
1. Instruction Space
2. Data Space
3. Environment stack space
 Instruction Space:
• Instruction space is the space needed to store the
compiled version of the program instructions.

The amount of instruction space that is needed depends

on factors such as-
i). The compiler used to compile the program into
machine code.

ii).The compiler options in effect at the time of

compilation.

iii).The target computer, i.,e computer on which the

algorithm run.
 Data Space:
• Data space is the space needed to store all constant
and variable values.
• Data space has two components.

– Space needed by constants, for example 0, 1,

2.134.

– Space needed by dynamically allocated objects

such as arrays, structures, classes.
 Environmental Stack Space:
• Environmental stack space is used during
execution of functions.
• Each time function is involved the following
data are saved as the environmental stack.
• The return address.
• Value of local variables.
• Value of formal parameters in the function
being invoked.
• Environmental stack space is mainly used in
recursive functions. Thus, the space
requirement of any program p may therefore
be written as
• Space complexity S(P) = C + Sp (Instance
characteristics).
This equation shows that the total space needed
by a program is divided into two parts.
• Fixed space requirements(C)
• A variable space requirements (SP(1))
 Time Complexity
• The time complexity of an algorithm is the
amount of computer time it needs to run to
completion
• We can measure the time complexity of an
algorithm in approaches
1. A priori Analysis
2. A posteriori Analysis
• In priori analysis before the algorithm is
executed we will analyze the behavior of the
algorithm.
• A priori analysis concentrates on determining
the order if execution of statements.

• In Posteriori analysis while the algorithm is

executed we measure the execution time.
Posteriori analysis gives accurate values but it
is very costly.
Rapid Quiz
 Methods to find Time Complexity

• Operation Count
• Step Count
• Asymptotic Notations

Total time taken=Compile time+ Run Time

Time complexity T(P) = C + TP(n).
 Operation Count

• Find the time taken by the Basic operations

such as addition , subtraction , multiplication
and so on.

• Count the number of operations performed by

individual operators.

• Compute the Total time.

• Example:
Ca  Time taken for addition
Cs  Time taken for Subtraction
Cm  Time taken for multiplication
Cd  Time taken for Division.
n  instance of Charecterstic

T(p)=[Link](n)+[Link](n)+[Link](n)+[Link](n)
 Step Count
Step count can be calculated by using
[Link] method
[Link] count method

Count Method
Globally initialize a variable Count=0.
Count every step when executed in an Algorithm
Example:
for i:=0 to n do
{
Statement;
}
 Complexity of Algorithms

• The term algorithm Complexity measures how many

steps are required by the algorithm to solve the given
problem.
• It evaluate the order of count operations executed by
an algorithm as a function of input data size.

• To asses the complexity, the Order(approximation) of

the count of operation is always considered.

• O(f) notation represents the complexity of an

algorithm, which is also termed as an Asymptotic
The complexity function f(n) for certain cases are:

• Best Case: The minimum possible value of f(n) is

called the best case.

• Average Case : The expected value of f(n).

• Worst Case: The maximum value of f(n) for any key

possible input.
 Typical Complexities of an Algorithm
• Constant Complexity:O(1).
• Logarithmic Complexity:O(log(N)).
• Linear Complexity:O(N).&O(n*log(n))
• Quadratic Complexity:O(n2).
• Cubic Complexity:O(n3).
• Exponential Complexity:O(2n), O(N!), O(nk), …
Constant Complexity
It imposes a complexity of O(1).The count of operations is
independent of the input data size.
Logarithmic Complexity:
It imposes a complexity of O(log(N)).
To perform operations on N elements, it often takes the
logarithmic base as 2.
Linear Complexity:
It imposes a complexity of O(N). It encompasses the same
number of steps as that of the total number of elements
to implement an operation on N elements.
Basically, in linear complexity, the number of elements
linearly depends on the number of steps.
• Quadratic Complexity:
• It imposes a complexity of O(n2).
• For N input data size, it undergoes the order
of N2 count of operations on N number of
elements for solving a given problem.
• Cubic Complexity:
It imposes a complexity of O(n3). For N input
data size, it executes the order of N3 steps on
N elements to solve a given problem.
Exponential Complexity:
• It imposes a complexity of O(2n), O(N!), O(nk),
…. For N elements, it will execute the order of
count of operations that is exponentially
dependable on the input data size.
 Asymptotic Notations
• Accurate measurement of time complexity is possible
with asymptotic notation. Asymptotic complexity
gives an idea of how rapidly the space requirement
or time requirement grow as problem size increase.

• There are three important asymptotic notations.

– Big oh notation (O)
– Omega notation
– Theta notation
• Let f(n) and g(n) are two non-negative functions.
 Big oh notation
• Big oh notation is denoted by ‘O’. it is used to
describe the efficiency of an algorithm.

• It is used to represent the upper bound of an

algorithms running time.

• Using Big O notation, we can give largest

amount of time taken by the algorithm to
complete.
Let f(n) and g(n) be the two non-negative functions.

We say that f(n) is said to be O(g(n)) if and only if there exists a

positive constant ‘c’ and ‘n0‘ such that,
f(n)<=c*g(n) for all non-negative values of n, where n≥n0.
Here, g(n) is the upper bound for f(n).
 Big omega notation
Definition: The function f(n)= W(g(n)) (read as for of n
is omega of g of n) if and only if there exist positive
constants ‘c’ and ‘n0’ such that,
f(n) ≥ c*g(n) for all n, n≥n0
 Big Theta notation
• Definition: Let f(n) and g(n) be the two non-negative
functions. We say that f(n) is said to be q(g(n)) if and only if
there exists a positive constants ‘c1’ and ‘c2’, such that,
• c1g(n) <= f(n) <= c2g((n) for all non-negative values n, where n
≥ n0.
 Little–OH (o)
•
• T(n) = o(p(n)) (pronounced little oh), says that
the growth rate of T(n) is less than the growth
rate of p(n) [if T(n) = O(p(n)) and T(n) ¹
q(p(n))].
•
 Divide-and-conquer method
• The “divide-and-conquer” technique involves
solving a particular problem by dividing it into
one or more sub-problems of smaller size,
recursively solving each sub-problem and then
“merging” the solution of sub-problems to
produce a solution to the original problem.
• Divide-and-conquer algorithms work according
to the following general plan.
• Divide: Divide the problem into a number of
smaller sub-problems ideally of about the same
size.
• Conquer: The smaller sub-problems are solved,
typically recursively. If the sub-problem sizes
are small enough, just solve the sub-problems
in a straight forward manner.
• Combine: If necessary, the solution obtained
the smaller problems are connected to get the
solution to the original problem.
 Control abstraction for divide-and-conquer technique:
Algorithm DandC(p)
{
if small (p) then return S(p)
else
{
Divide P into small instances P1, P2, P3 Pk, k≥1;
Apply DandC to each of these sub-problems;\
return combine (DandC(P1), DandC(P1),…. (DandC(Pk);
}
}
 Applications of Divide-and Conquer

The applications of divide-and-conquer methods

are-
• Binary search.
• Quick sort
• Merge sort.
 Binary Search:
• Binary search is an efficient searching
technique that works with only sorted lists
• The method starts with looking at the middle
element of the list.
• If it matches with the key element, then
search is complete.
• Otherwise, the key element may be in the first
half or second half of the list.
• If the key element is less than the middle
element, then the search continues with the
first half of the list.
• If the key element is greater than the middle
element, then the search continues with the
second half of the list.
• This process continues until the key element is
found or the search fails indicating that the
key is not there in the list.
 iterative binary Search Algorithm
Algorithm BinarySearch(a, n, key)
{
Low: = 0;
High: = n-1;
While (low < high) do
{
Mid: = (low + high)/2;
If ( key = a[mid]) then
Return mid;
Else if (key < a[mid])
{
High: = mid +1;
}
Else if( key > a[mid])
{
Low: = mid +1;
}
 Recursive Binary Search
Algorithms Binsearch ( a, n, key, low, high)
{
Mid: = (low + high)/2;
If ( key = a[mid]) then Return mid;
Else if (key < a[mid])
Binsearch ( a, n, key, low, mid-1);
Else if ( key > a[mid])
Binsearch ( a, n, key, mid+1, high);
}
Return -1;
}
 Quick Sort
• This method is based on divide-and-conquer
technique i.e. the entire list is divided into
various partitions and sorting is applied again
and again on these partitions
• This method is also called as partition
exchange sorts.
 Advantages of Binary Search

• The main advantage of binary search is that it

is faster than sequential (linear) search.

• Because it takes fewer comparisons, to

determine whether the given key is in the list,
then the linear search method.
 Disadvantages of Binary Search

• The disadvantage of binary search is that can

be applied to only a sorted list of elements.

• The binary search is unsuccessful if the list is

unsorted.
 Efficiency of Binary Search

• To evaluate binary search, count the number

of comparisons in the best case, average case,
and worst case.
Best Case O(1)
Average Case O( log n)
Worst Case O(log n)
 Quick sort algorithm
• Algorithm Quicksort(i, j)
• {
• // sorts the array from a[i] through a[j]
• If ( i <j) then //if there are more than one element
• {
• //divide P into two sub-programs K: = partition (a, i, j+1);
• //Here K denotes the position of the partitioning element
• //solve the sub problems Quicksort(i, K-1); Quicksort(K=1,
j);
• // There is no need for combining solution
• }
• }
• Algorithm Partition (a, left, right)
• {
• i:= left; j:=right; repeat
• {
• repeat
• i: =i+1;
• until (a[i] ≥ pivot); repeat
• j: =j-1;
• until (a[j] < pivot);
• if( i<j) then Swap (a, i, j);
• }until (i ≥ j);
• a[left]: = a[j];
• a[j]: = pivot;
• return j;
• }
• Algorithm Swap (a, i, j)
• {
• //Example a[i] with a[j] temp:= a[i];
• a[i]: = a[j]; a[j]:= temp;
• }
 Advantages of Quick-sort

• Quick-sort is the fastest sorting method

among all the sorting methods. But it is
somewhat complex and little difficult to
implement than other sorting methods.
• Quick Sort
•
• Best Case O(n log n)
• Average Case O(n log n)
• Worst Case O(n2)