INTRODUCTION TO ALGORITHM

History of Algorithm

• The word algorithm comes from the name of a Persian author, Abu Ja’far Mohammed ibn
Musa al Khowarizmi (c. 825 A.D.), who wrote a textbook on mathematics.
• He is credited with providing the step-by-step rules for adding, subtracting, multiplying,
and dividing ordinary decimal numbers.
• When written in Latin, the name became Algorismus, from which algorithm is but a small
step
• This word has taken on a special significance in computer science, where “algorithm” has
come to refer to a method that can be used by a computer for the solution of a problem
• Between 400 and 300 B.C., the great Greek mathematician Euclid invented an algorithm
• Finding the greatest common divisor (gcd) of two positive integers.
• The gcd of X and Y is the largest integer that exactly divides both X and Y .
• Eg.,the gcd of 80 and 32 is 16.
• The Euclidian algorithm, as it is called, is considered to be the first non-trivial algorithm
ever devised.

What is an Algorithm?

Algorithm is a set of steps to complete a task.

For example,

Task: to make a cup of tea.

Algorithm:
· add water and milk to the kettle,
· boil it, add tea leaves,
· Add sugar, and then serve it in cup.

‘’a set of steps to accomplish or complete a task that is described precisely enough that
a computer can run it’’.

Described precisely: very difficult for a machine to know how much water, milk to be
added etc. in the above tea making algorithm.
These algorithms run on computers or computational devices..For example, GPS in our
smartphones, Google hangouts.

GPS uses shortest path algorithm.. Online shopping uses cryptography which uses RSA
algorithm.

• Algorithm Definition1:

• An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.

In addition, all algorithms must satisfy the following criteria:
• Input. Zero or more quantities are externally supplied.
• Output. At least one quantity 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.

• Algorithm Definition2:

• An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for

obtaining a required output for any legitimate input in a finite amount of time.

• Algorithms that are definite and effective are also called computational procedures.
• A program is the expression of an algorithm in a programming language

• Algorithms for Problem Solving

The main steps for Problem Solving are:

1. Problem definition
2. Algorithm design / Algorithm specification
3. Algorithm analysis
4. Implementation
5. Testing
6. [Maintenance]

DESIGN AND ANALYSIS OF ALGORITHMS Page 6

• Step1. Problem Definition
What is the task to be accomplished?
Ex: Calculate the average of the grades for a given student

• Step2.Algorithm Design / Specifications:

Describe: in natural language / pseudo-code / diagrams / etc

• Step3. Algorithm analysis

Space complexity - How much space is required
Time complexity - How much time does it take to run the algorithm
Computer Algorithm
An algorithm is a procedure (a finite set of well-defined instructions) for accomplishing
some tasks which, given an initial state terminate in a defined end-state
The computational complexity and efficient implementation of the algorithm are important
in computing, and this depends on suitable data structures.
• Steps 4,5,6: Implementation, Testing, Maintainance
• Implementation:
Decide on the programming language to use C, C++, Lisp, Java, Perl, Prolog, assembly, etc.
, etc.
Write clean, well documented code
• Test, test, test
Integrate feedback from users, fix bugs, ensure compatibility across different versions
• Maintenance.
Release Updates,fix bugs

Keeping illegal inputs separate is the responsibility of the algorithmic problem, while
treating special classes of unusual or undesirable inputs is the responsibility of the algorithm
itself.

DESIGN AND ANALYSIS OF ALGORITHMS Page 7

• 4 Distinct areas of study of algorithms:

• How to devise algorithms.  Techniques – Divide & Conquer, Branch and Bound ,
Dynamic Programming
• How to validate algorithms.
• Check for Algorithm that it computes the correct answer for all possible legal inputs. 
algorithm validation.  First Phase
• Second phase  Algorithm to Program  Program Proving or Program Verification
Solution be stated in two forms:
• First Form: Program which is annotated by a set of assertions about the input and output
variables of the program predicate calculus
• Second form: is called a specification
• 4 Distinct areas of study of algorithms (..Contd)
• How to analyze algorithms.
• Analysis of Algorithms or performance analysis refer to the task of determining how
much computing time & storage an algorithm requires
• How to test a program  2 phases 
• Debugging - Debugging is the process of executing programs on sample data sets to
determine whether faulty results occur and, if so, to correct them.
• Profiling or performance measurement is the process of executing a correct program on
data sets and measuring the time and space it takes to compute the results

PSEUDOCODE:

• Algorithm can be represented in Text mode and Graphic mode

• Graphical representation is called Flowchart
• Text mode most often represented in close to any High level language such as C,
PascalPseudocode

• Pseudocode: 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.

• Example of Pseudocode:

• To find the max element of an array

Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax  A[0]
for i  1 to n  1 do
if A[i]  currentMax then
currentMax  A[i]

DESIGN AND ANALYSIS OF ALGORITHMS Page 8

 return currentMax

• Control flow
• if … then … [else …]
• while … do …
• repeat … until …
• for … do …
• Indentation replaces braces
• Method declaration
• Algorithm method (arg [, arg…])
• Input …
• Output …
• Method call
• var.method (arg [, arg…])
• Return value
• return expression
• Expressions
• Assignment (equivalent to )
• Equality testing (equivalent to )
• n2 Superscripts and other mathematical formatting allowed

PERFORMANCE ANALYSIS:

• What are the Criteria for judging algorithms that have a more direct relationship to
performance?
• computing time and storage requirements.

• Performance evaluation can be loosely divided into two major phases:

• a priori estimates and
• a posteriori testing.
• refer as performance analysis and performance measurement respectively

• The space complexity of an algorithm is the amount of memory it needs to run to

completion.
• The time complexity of an algorithm is the amount of computer time it needs to run to
completion.

Space Complexity:

• Space Complexity Example:

• Algorithm abc(a,b,c)
{
return a+b++*c+(a+b-c)/(a+b) +4.0;
}

The Space needed by each of these algorithms is seen to be the sum of the following
component.

DESIGN AND ANALYSIS OF ALGORITHMS Page 9

1.A fixed part that is independent of the characteristics (eg:number,size)of the inputs and
outputs.
The part typically includes the instruction space (ie. Space for the code), space for simple
variable and fixed-size component variables (also called aggregate) space for constants, and
so on.

2. A variable part that consists of the space needed by component variables whose size is
dependent on the particular problem instance being solved, the space needed by referenced
variables (to the extent that is depends on instance characteristics), and the recursion stack
space.

The space requirement s(p) of any algorithm p may therefore be written as,
S(P) = c+ Sp(Instance characteristics)
Where ‘c’ is a constant.

Example 2:
Algorithm sum(a,n)
{
s=0.0;
for I=1 to n do
s= s+a[I];
return s;
}
The problem instances for this algorithm are characterized by n,the number of
elements to be summed. The space needed d by ‘n’ is one word, since it is of
type integer.
The space needed by ‘a’a is the space needed by variables of tyepe array of
floating point numbers.
This is atleast ‘n’ words, since ‘a’ must be large enough to hold the ‘n’
elements to be summed.
So,we obtain Ssum(n)>=(n+s)
• [ n for a[],one each for n,I a& s]

Time Complexity:

• The time T(p) taken by a program P is the sum of the compile time and the
run time(execution time)

• The compile time does not depend on the instance characteristics. Also we may
assume that a compiled program will be run several times without recompilation .This
rum time is denoted by tp(instance characteristics).

• The number of steps any problem statement is assigned depends on the kind of
statement.

• For example, comments à 0 steps.

Assignment statements is 1 steps.

DESIGN AND ANALYSIS OF ALGORITHMS Page 10

[Which does not involve any calls to other algorithms]
Interactive statement such as for, while & repeat-untilà Control part of the statement.

We introduce a variable, count into the program statement to increment count with
initial value 0.Statement to increment count by the appropriate amount are introduced
into the program.

This is done so that each time a statement in the original program is executes
count is incremented by the step count of that statement.

Algorithm:
Algorithm sum(a,n)
{
s= 0.0;
count = count+1;
for I=1 to n do
{
count =count+1;
s=s+a[I];
count=count+1;
}
count=count+1;
count=count+1;
return s;
}

If the count is zero to start with, then it will be 2n+3 on termination. So each
invocation of sum execute a total of 2n+3 steps.

2. The second method to determine the step count of an algorithm is to build a

table in which we list the total number of steps contributes by each statement.

First determine the number of steps per execution (s/e) of the statement and the
total number of times (ie., frequency) each statement is executed.

By combining these two quantities, the total contribution of all statements, the
step count for the entire algorithm is obtained.

Statement Steps per Frequency Total

execution
1. Algorithm Sum(a,n) 0 - 0
2.{ 0 - 0
3. S=0.0; 1 1 1
4. for I=1 to n do 1 n+1 n+1
5. s=s+a[I]; 1 n n
6. return s; 1 1 1
7. } 0 - 0

Total 2n+3

DESIGN AND ANALYSIS OF ALGORITHMS Page 11

How to analyse an Algorithm?

Let us form an algorithm for Insertion sort (which sort a sequence of numbers).The pseudo
code for the algorithm is give below.

Pseudo code for insertion Algorithm:

Identify each line of the pseudo code with symbols such as C1, C2 ..

PSeudocode for Insertion Algorithm Line Identification

for j=2 to A length C1
key=A[j] C2
//Insert A[j] into sorted Array A[1.....j-1] C3
i=j-1 C4
while i>0 & A[j]>key C5
A[i+1]=A[i] C6
i=i-1 C7
A[i+1]=key C8

Let Ci be the cost of ith line. Since comment lines will not incur any cost C3=0.
Cost No. Of times
Executed
C1 N
C2 n-1
C3=0 n-1
C4 n-1
C5

C6

C7

C8 n-1

Running time of the algorithm is:

T(n)=C1n+C2(n-1)+0(n-1)+C4(n-1)+C5( )+C6( )+C7( )+

C8(n-1)

Best case:

It occurs when Array is sorted.

All tj values are 1.

DESIGN AND ANALYSIS OF ALGORITHMS Page 12

T(n)=C1n+C2(n-1)+0 (n-1)+C4(n-1)+C5( ) +C6( )+C7( )+
C8(n-1)

=C1n+C2 (n-1) +0 (n-1) +C4 (n-1) +C5 + C8 (n-1)

= (C1+C2+C4+C5+ C8) n-(C2+C4+C5+ C8)

· Which is of the form an+b.

· Linear function of n.

So, linear growth.

Worst case:

It occurs when Array is reverse sorted, and tj =j

T(n)=C1n + C2(n-1)+0 (n-1)+C4(n-1)+C5( ) +C6( )+C7( )+

C8(n-1)

=C1n+C2(n-1)+C4(n-1)+C5( ) +C6( )+C7( )+ C8(n-1)

which is of the form an2+bn+c

Quadratic function. So in worst case insertion set grows in n2.

Why we concentrate on worst-case running time?

· The worst-case running time gives a guaranteed upper bound on the running time for
any input.

· For some algorithms, the worst case occurs often. For example, when searching, the
worst case often occurs when the item being searched for is not present, and searches
for absent items may be frequent.

· Why not analyze the average case? Because it’s often about as bad as the worst case.
Order of growth:

It is described by the highest degree term of the formula for running time. (Drop lower-order
terms. Ignore the constant coefficient in the leading term.)

Example: We found out that for insertion sort the worst-case running time is of the form
an2 + bn + c.

Drop lower-order terms. What remains is an2.Ignore constant coefficient. It results in n2.But
we cannot say that the worst-case running time T(n) equals n2 .Rather It grows like n2 . But it
doesn’t equal n2.We say that the running time is Θ (n2) to capture the notion that the order of
growth is n2.

DESIGN AND ANALYSIS OF ALGORITHMS Page 13

We usually consider one algorithm to be more efficient than another if its worst-case
running time has a smaller order of growth.

Complexity of Algorithms

The complexity of an algorithm M is the function f(n) which gives the running time and/or
storage space requirement of the algorithm in terms of the size ‘n’ of the input data. Mostly,
the storage space required by an algorithm is simply a multiple of the data size ‘n’.

Complexity shall refer to the running time of the algorithm.

The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of
the input data but also on the particular data. The complexity function f(n) for certain cases
are:

1. Best Case : The minimum possible value of f(n) is called the best case.

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

3. Worst Case : The maximum value of f(n) for any key possible input.

ASYMPTOTIC NOTATION

 Formal way notation to speak about functions and classify them

The following notations are commonly use notations in performance analysis and used to
characterize the complexity of an algorithm:

1. Big–OH (O) ,
2. Big–OMEGA (Ω),
3. Big–THETA (Θ) and
4. Little–OH (o)

Asymptotic Analysis of Algorithms:

Our approach is based on the asymptotic complexity measure. This means that we don’t try to
count the exact number of steps of a program, but how that number grows with the size of the
input to the program. That gives us a measure that will work for different operating systems,
compilers and CPUs. The asymptotic complexity is written using big-O notation.

· It is a way to describe the characteristics of a function in the limit.

· It describes the rate of growth of functions.
· Focus on what’s important by abstracting away low-order terms and constant factors.
· It is a way to compare “sizes” of functions:

O≈ ≤

DESIGN AND ANALYSIS OF ALGORITHMS Page 14

 Ω≈ ≥
Θ≈=
o≈<
ω≈>

Time complexity Name Example

O(1) Constant Adding an element to the
front of a linked list
O(logn) Logarithmic Finding an element in a
sorted array
O (n) Linear Finding an element in an
unsorted array
O(nlog n) Linear Logarithmic Sorting n items
by ‘divide-and-conquer’-
Mergesort
O(n2) Quadratic Shortest path between two
nodes in a graph
O(n3) Cubic Matrix Multiplication
O(2n) Exponential The Towers of Hanoi
problem

Big ‘oh’: the function f(n)=O(g(n)) iff there exist positive constants c and no such that
f(n)<=c*g(n) for all n, n>= no.
Omega: the function f(n)=(g(n)) iff there exist positive constants c and no such that
f(n) >= c*g(n) for all n, n >= no.
Theta: the function f(n)=(g(n)) iff there exist positive constants c1,c2 and no such that c1
g(n) <= f(n) <= c2 g(n) for all n, n >= no

Big-O Notation

This notation gives the tight upper bound of the given function. Generally we represent it as
f(n) = O(g (11)). That means, at larger values of n, the upper bound off(n) is g(n). For
example, if f(n) = n4 + 100n2 + 10n + 50 is the given algorithm, then n4 is g(n). That means
g(n) gives the maximum rate of growth for f(n) at larger values of n.

O —notation defined as O(g(n)) = {f(n): there exist positive constants c and no such that
0 <= f(n) <= cg(n) for all n >= no}. g(n) is an asymptotic tight upper bound for f(n). Our
objective is to give some rate of growth g(n) which is greater than given algorithms rate of
growth f(n).

In general, we do not consider lower values of n. That means the rate of growth at lower
values of n is not important. In the below figure, no is the point from which we consider the
rate of growths for a given algorithm. Below no the rate of growths may be different.

DESIGN AND ANALYSIS OF ALGORITHMS Page 15

Note Analyze the algorithms at larger values of n only What this means is, below no we do
not care for rates of growth.

Omega— Ω notation

Similar to above discussion, this notation gives the tighter lower bound of the given
algorithm and we represent it as f(n) = Ω (g(n)). That means, at larger values of n, the
tighter lower bound of f(n) is g
For example, if f(n) = 100n2 + 10n + 50, g(n) is Ω (n2).
The . Ω. notation as be defined as Ω (g (n)) = {f(n): there exist positive constants c and
no such that 0 <= cg (n) <= f(n) for all n >= no}. g(n) is an asymptotic lower bound for
f(n). Ω (g (n)) is the set of functions with smaller or same order of growth as f(n).

Theta- Θ notation

This notation decides whether the upper and lower bounds of a given function are same or
not. The average running time of algorithm is always between lower bound and upper bound.

DESIGN AND ANALYSIS OF ALGORITHMS Page 16

If the upper bound (O) and lower bound (Ω) gives the same result then Θ notation will also
have the same rate of growth. As an example, let us assume that f(n) = 10n + n is the
expression. Then, its tight upper bound g(n) is O(n). The rate of growth in best case is g (n) =
0(n). In this case, rate of growths in best case and worst are same. As a result, the average
case will also be same.

None: For a given function (algorithm), if the rate of growths (bounds) for O and Ω are not
same then the rate of growth Θ case may not be same.

Now consider the definition of Θ notation It is defined as Θ (g(n)) = {f(71): there exist
positive constants C1, C2 and no such that O<=5 c1g(n) <= f(n) <= c2g(n) for all n >= no}.
g(n) is an asymptotic tight bound for f(n). Θ (g(n)) is the set of functions with the same
order of growth as g(n).

Important Notes

For analysis (best case, worst case and average) we try to give upper bound (O) and lower
bound (Ω) and average running time (Θ). From the above examples, it should also be clear
that, for a given function (algorithm) getting upper bound (O) and lower bound (Ω) and
average running time (Θ) may not be possible always.
For example, if we are discussing the best case of an algorithm, then we try to give upper
bound (O) and lower bound (Ω) and average running time (Θ).
In the remaining chapters we generally concentrate on upper bound (O) because knowing
lower bound (Ω) of an algorithm is of no practical importance and we use 9 notation if upper
bound (O) and lower bound (Ω) are same.

Little Oh Notation

The little Oh is denoted as o. It is defined as : Let, f(n} and g(n} be the non negative
functions then

DESIGN AND ANALYSIS OF ALGORITHMS Page 17

such that f(n}= o(g{n)} i.e f of n is little Oh of g of n.

f(n) = o(g(n)) if and only if f'(n) = o(g(n)) and f(n) != Θ {g(n))

PROBABILISTIC ANALYSIS

Probabilistic analysis is the use of probability in the analysis of problems.

In order to perform a probabilistic analysis, we must use knowledge of, or make assumptions
about, the distribution of the inputs. Then we analyze our algorithm, computing an average-
case running time, where we take the average over the distribution of the possible inputs.

Basics of Probability Theory

Probability theory has the goal of characterizing the outcomes of natural or conceptual
“experiments.” Examples of such experiments include tossing a coin ten times, rolling a die
three times, playing a lottery, gambling, picking a ball from an urn containing white and red
balls, and so on

Each possible outcome of an experiment is called a sample point and the set of all possible
outcomes is known as the sample space S. In this text we assume that S is finite (such a
sample space is called a discrete sample space). An event E is a subset of the sample space S.
If the sample space consists of n sample points, then there are 2n possible events.

Definition- Probability: The probability of an event E is defined to be where S is the

sample space.

Then the indicator random variable I {A} associated with event A is defined as

I {A} = 1 if A occurs ;
0 if A does not occur

The probability of event E is denoted as Prob. [E] The complement of E, denoted E, is

defined to be S - E. If E1 and E2 are two events, the probability of E1 or E2 or both
happening is denoted as Prob.[E1 U E2]. The probability of both E1 and E2 occurring at the
same time is denoted as Prob.[E1 0 E2]. The corresponding event is E1 0 E2.

Theorem 1.5

1. Prob.[E] = 1 - Prob.[E].
2. Prob.[E1 U E2] = Prob.[E1] + Prob.[E2] - Prob.[E1 ∩ E2]
<= Prob.[E1] + Prob.[E2]

Expected value of a random variable

DESIGN AND ANALYSIS OF ALGORITHMS Page 18

The simplest and most useful summary of the distribution of a random variable is the
average” of the values it takes on. The expected value (or, synonymously, expectation or
mean) of a discrete random variable X is

E[X] =

which is well defined if the sum is finite or converges absolutely.

Consider a game in which you flip two fair coins. You earn $3 for each head but lose $2 for
each tail. The expected value of the random variable X representing

your earnings is

E[X] = 6.Pr{2H’s} + 1.Pr{1H,1T} – 4 Pr{2T’s}

= 6(1/4)+1(1/2)-4(1/4)
=1

Any one of these first i candidates is equally likely to be the best-qualified so far. Candidate i
has a probability of 1/i of being better qualified than candidates 1 through i -1 and thus a
probability of 1/i of being hired.

E[Xi]= 1/i

So,
E[X] = E[ ]

=
=

AMORTIZED ANALYSIS

In an amortized analysis, we average the time required to perform a sequence of datastructure

operations over all the operations performed. With amortized analysis, we can show that the
average cost of an operation is small, if we average over a sequence of operations, even
though a single operation within the sequence might be expensive. Amortized analysis differs
from average-case analysis in that probability is not involved; an amortized analysis
guarantees the average performance of each operation in the worst case.

Three most common techniques used in amortized analysis:

1. Aggregate Analysis - in which we determine an upper bound T(n) on the total cost
of a sequence of n operations. The average cost per operation is then T(n)/n. We take
the average cost as the amortized cost of each operation

2. Accounting method – When there is more than one type of operation, each type of
operation may have a different amortized cost. The accounting method overcharges
some operations early in the sequence, storing the overcharge as “prepaid credit” on
specific objects in the data structure. Later in the sequence, the credit pays for
operations that are charged less than they actually cost.

DESIGN AND ANALYSIS OF ALGORITHMS Page 19

 3. Potential method - The potential method maintains the credit as the “potential
energy” of the data structure as a whole instead of associating the credit with
individual objects within the data structure. The potential method, which is like the
accounting method in that we determine the amortized cost of each operation and
may overcharge operations early on to compensate for undercharges later

DIVIDE AND CONQUER

General Method

In divide and conquer method, a given problem is,

i) Divided into smaller subproblems.
ii) These subproblems are solved independently.
iii) Combining all the solutions of subproblems into a solution of the whole.

If the subproblems are large enough then divide and conquer is reapplied.
The generated subproblems are usually of some type as the original problem.

Hence recurssive algorithms are used in divide and conquer strategy.

Problem of size N

Subprogram of size Subprogram of size

N/2 N/2

Solution to Solution to
subprogram 1 subprogram 2

Solution to the original problem of

size n

Pseudo code Representation of Divide and conquer rule for problem “P”

DESIGN AND ANALYSIS OF ALGORITHMS Page 20

Algorithm DAndC(P)
{
if small(P) then return S(P)
else{
divide P into smaller instances P1,P2,P3…Pk;
apply DAndC to each of these subprograms; // means DAndC(P1), DAndC(P2)…..
DAndC(Pk)
return combine(DAndC(P1), DAndC(P2)….. DAndC(Pk));
}
}

//PProblem
//Here small(P) Boolean value function. If it is true, then the function S is
//invoked

Time Complexity of DAndC algorithm:

T(n) = T(1) if n=1
aT(n/b)+f(n) if n>1

a,b contants.
This is called the general divide and-conquer recurrence.

Example for GENERAL METHOD:

As an example, let us consider the problem of computing the sum of n numbers a0, ... an-1.
If n > 1, we can divide the problem into two instances of the same problem. They are sum of
the first | n/2|numbers
Compute the sum of the 1st [n/2] numbers, and then compute the sum of another n/2 numbers.
Combine the answers of two n/2 numbers sum.
i.e.,
a0 + . . . + an-1 =( a0 + ....+ an/2) + (a n/2 + . . . . + an-1)
Assuming that size n is a power of b, to simplify our analysis, we get the following
recurrence for the running time T(n).
T(n)=aT(n/b)+f(n)

This is called the general divide and-conquer recurrence.

f(n) is a function that accounts for the time spent on dividing the problem into smaller ones
and on combining their solutions. (For the summation example, a = b = 2 and f (n) = 1.

Advantages of DAndC:
The time spent on executing the problem using DAndC is smaller than other method.
This technique is ideally suited for parallel computation.
This approach provides an efficient algorithm in computer science.

Master Theorem for Divide and Conquer

In all efficient divide and conquer algorithms we will divide the problem into subproblems,
each of which is some part of the original problem, and then perform some additional work to
compute the final answer. As an example, if we consider merge sort [for details, refer Sorting
chapter], it operates on two problems, each of which is half the size of the original, and then
uses O(n) additional work for merging. This gives the running time equation:

DESIGN AND ANALYSIS OF ALGORITHMS Page 21

T(n) = 2T( )+ O(n)

The following theorem can be used to determine the running time of divide and conquer
algorithms. For a given program or algorithm, first we try to find the recurrence relation for
the problem. If the recurrence is of below form then we directly give the answer without
fully solving it.

If the reccurrence is of the form T(n) = aT( ) + Θ (nklogpn), where a >= 1, b > 1, k >= O
and p is a real number, then we can directly give the answer as:

1) If a > bk, then T(n) = Θ ( )

2) If a = bk
a. If p > -1, then T(n) = Θ ( )
b. If p = -1, then T(n) = Θ ( )
c. If p < -1, then T(n) = Θ ( s)

3) If a < bk
a. If p >= 0, then T(n) = Θ (nklogpn)
b. If p < 0, then T(n) = 0(nk)

Applications of Divide and conquer rule or algorithm:

 Binary search,
 Quick sort,
 Merge sort,
 Strassen’s matrix multiplication.

Binary search or Half-interval search algorithm:

1. This algorithm finds the position of a specified input value (the search "key") within
an array sorted by key value.
2. In each step, the algorithm compares the search key value with the key value of the
middle element of the array.
3. If the keys match, then a matching element has been found and its index, or position,
is returned.
4. Otherwise, if the search key is less than the middle element's key, then the algorithm
repeats its action on the sub-array to the left of the middle element or, if the search
key is greater, then the algorithm repeats on sub array to the right of the middle
element.
5. If the search element is less than the minimum position element or greater than the
maximum position element then this algorithm returns not found.

Binary search algorithm by using recursive methodology:

Program for binary search (recursive) Algorithm for binary search (recursive)
int binary_search(int A[], int key, int imin, int imax) Algorithm binary_search(A, key, imin, imax)

DESIGN AND ANALYSIS OF ALGORITHMS Page 22

{ {
if (imax < imin) if (imax < imin) then
return array is empty; return “array is empty”;
if(key<imin || K>imax) if(key<imin || K>imax) then
return element not in array list return “element not in array list”
else else
{ {
int imid = (imin +imax)/2; imid = (imin +imax)/2;
if (A[imid] > key) if (A[imid] > key) then
return binary_search(A, key, imin, imid-1); return binary_search(A, key, imin, imid-1);
else if (A[imid] < key) else if (A[imid] < key) then
return binary_search(A, key, imid+1, imax); return binary_search(A, key, imid+1, imax);
else else
return imid; return imid;
} }
} }

Time Complexity:
Data structure:- Array
For successful search Unsuccessful search
Worst case O(log n) or θ(log n) θ(log n):- for all cases.
Average case O(log n) or θ(log n)
Best case O(1) or θ(1)
Binary search algorithm by using iterative methodology:
Binary search program by using iterative Binary search algorithm by using iterative
methodology: methodology:
int binary_search(int A[], int key, int imin, int Algorithm binary_search(A, key, imin, imax)
imax) {
{ While < (imax >= imin)> do
while (imax >= imin) {
{ int imid = midpoint(imin, imax);
int imid = midpoint(imin, imax); if(A[imid] == key)
if(A[imid] == key) return imid;
return imid; else if (A[imid] < key)
else if (A[imid] < key) imin = imid + 1;
imin = imid + 1; else
else imax = imid - 1;
imax = imid - 1; }
} }
}

Merge Sort:
The merge sort splits the list to be sorted into two equal halves, and places them in separate
arrays. This sorting method is an example of the DIVIDE-AND-CONQUER paradigm i.e. it
breaks the data into two halves and then sorts the two half data sets recursively, and finally
merges them to obtain the complete sorted list. The merge sort is a comparison sort and has an
algorithmic complexity of O (n log n). Elementary implementations of the merge sort make use of
two arrays - one for each half of the data set. The following image depicts the complete procedure
of merge sort.

DESIGN AND ANALYSIS OF ALGORITHMS Page 23

Advantages of Merge Sort:
1. Marginally faster than the heap sort for larger sets
2. Merge Sort always does lesser number of comparisons than Quick Sort. Worst case for
merge sort does about 39% less comparisons against quick sort’s average case.
3. Merge sort is often the best choice for sorting a linked list because the slow random-
access performance of a linked list makes some other algorithms (such as quick sort)
perform poorly, and others (such as heap sort) completely impossible.

Program for Merge sort:

#include<stdio.h>
#include<conio.h>
int n;
void main(){
int i,low,high,z,y;
int a[10];
void mergesort(int a[10],int low,int high);
void display(int a[10]);
clrscr();
printf("\n \t\t mergesort \n");
printf("\n enter the length of the list:");
scanf("%d",&n);
printf("\n enter the list elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
low=0;
high=n-1;
mergesort(a,low,high);
display(a);
getch();
}
void mergesort(int a[10],int low, int high)

DESIGN AND ANALYSIS OF ALGORITHMS Page 24

{
int mid;
void combine(int a[10],int low, int mid, int high);
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
combine(a,low,mid,high);
}
}
void combine(int a[10], int low, int mid, int high){
int i,j,k;
int temp[10];
k=low;
i=low;
j=mid+1;
while(i<=mid&&j<=high){
if(a[i]<=a[j])
{
temp[k]=a[i];
i++;
k++;
}
else
{
temp[k]=a[j];
j++;
k++;
}
}
while(i<=mid){
temp[k]=a[i];
i++;
k++;
}

while(j<=high){
temp[k]=a[j];
j++;
k++;
}
for(k=low;k<=high;k++)
a[k]=temp[k];
}
void display(int a[10]){
int i;
printf("\n \n the sorted array is \n");
for(i=0;i<n;i++)
printf("%d \t",a[i]);}

DESIGN AND ANALYSIS OF ALGORITHMS Page 25

 Algorithm for Merge sort:
Algorithm mergesort(low, high)
{
if(low<high) then // Dividing Problem into Sub-problems and
{ this “mid” is for finding where to split the set.
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high); //Solve the sub-problems
Merge(low,mid,high); // Combine the solution
}
}
void Merge(low, mid,high){
k=low;
i=low;
j=mid+1;
while(i<=mid&&j<=high) do{
if(a[i]<=a[j]) then
{
temp[k]=a[i];
i++;
k++;
}
else
{
temp[k]=a[j];
j++;
k++;
}
}
while(i<=mid) do{
temp[k]=a[i];
i++;
k++;
}

while(j<=high) do{
temp[k]=a[j];
j++;
k++;
}
For k=low to high do
a[k]=temp[k];
}
For k:=low to high do a[k]=temp[k];
}

DESIGN AND ANALYSIS OF ALGORITHMS Page 26

 Tree call of Merge sort
Consider a example: (From text book)
A[1:10]={310,285,179,652,351,423,861,254,450,520}

1, 10

1, 5 6, 10

1, 3 4, 5 6, 8 9, 10

1, 2 3,3 4, 4 5, 5 6, 7 8, 8 9,9 10, 10

Tree call of Merge sort (1, 10)
1, 1 2, 2
Tree call of Merge Sort Represents the sequence 6,
of6recursive
7, calls
7 that are produced by
merge sort.

“Once observe the explained notes in class room”

Computing Time for Merge sort:

The time for the merging operation in proportional to n, then computing time for merge sort
is described by using recurrence relation.

T(n)= a if n=1;
2T(n/2)+ cn if n>1

Here c, aConstants.

If n is power of 2, n=2k

Form recurrence relation

T(n)= 2T(n/2) + cn

2[2T(n/4)+cn/2] + cn

4T(n/4)+2cn

22 T(n/4)+2cn

23 T(n/8)+3cn

24 T(n/16)+4cn

2k T(1)+kcn

an+cn(log n)

DESIGN AND ANALYSIS OF ALGORITHMS Page 27

By representing it by in the form of Asymptotic notation O is

T(n)=O(nlog n)

Quick Sort
Quick Sort is an algorithm based on the DIVIDE-AND-CONQUER paradigm that selects a pivot
element and reorders the given list in such a way that all elements smaller to it are on one side
and those bigger than it are on the other. Then the sub lists are recursively sorted until the list gets
completely sorted. The time complexity of this algorithm is O (n log n).

 Auxiliary space used in the average case for implementing recursive function calls is
O (log n) and hence proves to be a bit space costly, especially when it comes to large
data sets.
2
 Its worst case has a time complexity of O (n ) which can prove very fatal for large
data sets. Competitive sorting algorithms
Quick sort program
#include<stdio.h>
#include<conio.h>
int n,j,i;
void main(){
int i,low,high,z,y;
int a[10],kk;
void quick(int a[10],int low,int high);
int n;
clrscr();
printf("\n \t\t mergesort \n");
printf("\n enter the length of the list:");
scanf("%d",&n);
printf("\n enter the list elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
low=0;
high=n-1;
quick(a,low,high);
printf("\n sorted array is:");
for(i=0;i<n;i++)
printf(" %d",a[i]);
getch();
}

int partition(int a[10], int low, int high){

int i=low,j=high;
int temp;
int mid=(low+high)/2;
int pivot=a[mid];
while(i<=j)
{
while(a[i]<=pivot)
i++;

DESIGN AND ANALYSIS OF ALGORITHMS Page 28

while(a[j]>pivot)
j--;
if(i<=j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}}
return j;
}
void quick(int a[10],int low, int high)
{
int m=partition(a,low,high);
if(low<m)
quick(a,low,m);
if(m+1<high)
quick(a,m+1,high);
}

Algorithm for Quick sort

Algorithm quickSort (a, low, high) {
If(high>low) then{
m=partition(a,low,high);
if(low<m) then quick(a,low,m);
if(m+1<high) then quick(a,m+1,high);
}}

Algorithm partition(a, low, high){

i=low,j=high;
mid=(low+high)/2;
pivot=a[mid];
while(i<=j) do { while(a[i]<=pivot)
i++;
while(a[j]>pivot)
j--;
if(i<=j){ temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}}
return j;
}

Time Complexity
Name Best case Average Worst Space
Case Case Complexity
Bubble O(n) - O(n2) O(n)
Insertion O(n) O(n2) O(n2) O(n)
Selection O(n2) O(n2) O(n2) O(n)

DESIGN AND ANALYSIS OF ALGORITHMS Page 29

 Quick O(log n) O(n log n) O(n2) O(n + log n)
Merge O(n log n) O(n log n) O(n log n) O(2n)
Heap O(n log n) O(n log n) O(n log n) O(n)

Comparison between Merge and Quick Sort:

 Both follows Divide and Conquer rule.
 Statistically both merge sort and quick sort have the same average case time i.e., O(n
log n).
 Merge Sort Requires additional memory. The pros of merge sort are: it is a stable sort,
and there is no worst case (means average case and worst case time complexity is
same).
 Quick sort is often implemented in place thus saving the performance and memory by
not creating extra storage space.
 But in Quick sort, the performance falls on already sorted/almost sorted list if the
pivot is not randomized. Thus why the worst case time is O(n2).

Randomized Sorting Algorithm: (Random quick sort)

 While sorting the array a[p:q] instead of picking a[m], pick a random element (from
among a[p], a[p+1], a[p+2]---a[q]) as the partition elements.
 The resultant randomized algorithm works on any input and runs in an expected O(n
log n) times.

Algorithm for Random Quick sort

Algorithm RquickSort (a, p, q) {
If(high>low) then{
If((q-p)>5) then
Interchange(a, Random() mod (q-p+1)+p, p);
m=partition(a,p, q+1);
quick(a, p, m-1);
quick(a,m+1,q);
}}

Strassen’s Matrix Multiplication:

Let A and B be two n×n Matrices. The product matrix C=AB is also a n×n matrix whose i, jth
element is formed by taking elements in the ith row of A and jth column of B and multiplying
them to get
C(i, j)=
Here 1≤ i & j ≤ n means i and j are in between 1 and n.

To compute C(i, j) using this formula, we need n multiplications.

The divide and conquer strategy suggests another way to compute the product of two n×n
matrices.
For Simplicity assume n is a power of 2 that is n=2k
Here k any nonnegative integer.

DESIGN AND ANALYSIS OF ALGORITHMS Page 30

If n is not power of two then enough rows and columns of zeros can be added to both A and
B, so that resulting dimensions are a power of two.

Let A and B be two n×n Matrices. Imagine that A & B are each partitioned into four square
sub matrices. Each sub matrix having dimensions n/2×n/2.
The product of AB can be computed by using previous formula.
If AB is product of 2×2 matrices then
=

C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B21
C22= A21B12+A22B22

Here 8 multiplications and 4 additions are performed.

Note that Matrix Multiplication are more Expensive than matrix addition and subtraction.
T(n)= b if n≤2;
8T(n/2)+ cn2 if n>2
Volker strassen has discovered a way to compute the Ci,j of above using 7 multiplications
and 18 additions or subtractions.
For this first compute 7 n/2×n/2 matrices P, Q, R, S, T, U & V
P=(A11+A22)(B11+B22)
Q=(A21+A22)B11
R=A11(B12-B22)
S=A22(B21-B11)
T=(A11+A12)B22
U=(A21-A11)(B11+B12)
V=(A12-A22)(B21+B22)

C11=P+S-T+V
C12=R+T T(n)= b if n≤2;
C21=Q+S 7T(n/2)+ cn2 if n>2
C22=P+R-Q+U

DESIGN AND ANALYSIS OF ALGORITHMS Page 31

UNIT II:
Searching and Traversal Techniques: Efficient non - recursive binary tree traversal
algorithm, Disjoint set operations, union and find algorithms, Spanning trees, Graph
traversals - Breadth first search and Depth first search, AND / OR graphs, game trees,
Connected Components, Bi - connected components. Disjoint Sets- disjoint set operations,
union and find algorithms, spanning trees, connected
components and biconnected components.

Efficient non recursive tree traversal algorithms

in-order: (left, root, right)
3,5,6,7,10,12,13
15, 16, 18, 20, 23

pre-order: (root, left, right)

15, 5, 3, 12, 10, 6, 7,
13, 16, 20, 18, 23

post-order: (left, right, root)

3, 7, 6, 10, 13, 12, 5,
18, 23,20,16, 65

Non recursive Inorder traversal algorithm

1. Start fiom the root. let's it is current.

2. Ifcurrent is not NULL. push the node on to stack.
3. Move to left child of current and go to step 2.
4. Ifcurrent is NULL, and stack is not empty, pop node from the stack.
5. Print the node value and change current to right child of current.
6. Go to step 2.

So we go on traversing all left node. as we visit the node. we will put that node into
stack.remember need to visit parent after the child and as We will encounter parent first when
start from root. it's case for LIFO :) and hence the stack). Once we reach NULL node. we will
take the node at the top of the stack. last node which we visited. Print it.
Check if there is right child to that node. If yes. move right child to stack and again start
traversing left child node and put them on to stack. Once we have traversed all node. our
stack will be empty.

Non recursive postorder traversal algorithm

Left node. right node and last parent node.

1.1 Create an empty stack
2.1 Do Following while root is not NULL
a) Push root's right child and then root to stack.

DESIGN AND ANALYSIS OF ALGORITHMS Page 32

b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
Ia) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

Disjoint Sets: If Si and Sj, i≠j are two sets, then there is no element that is in both Si and Sj..
For example: n=10 elements can be partitioned into three disjoint sets,
S1= {1, 7, 8, 9}
S2= {2, 5, 10}
S3= {3, 4, 6}

Tree representation of sets:

1 5 3

7 8 9 2 10 4 6
1 S1 S2 S3

Disjoint set Operations:

 Disjoint set Union
 Find(i)

Disjoint set Union: Means Combination of two disjoint sets elements. Form above
example S1 U S2 ={1,7,8,9,5,2,10 }
For S1 U S2 tree representation, simply make one of the tree is a subtree
of the other.

1 1

5 5 7 8 9
7 8 9
1
1
S1 U S2 2 10 2 10
S1 U S2 S2 U S1

Find: Given element i, find the set containing i.

Form above example:
Find(4)S3

DESIGN AND ANALYSIS OF ALGORITHMS Page 33

 Find(1)S1
Find(10)S2

Data representation of sets:

Tress can be accomplished easily if, with each set name, we keep a pointer to the root of the
tree representing that set.

For presenting the union and find algorithms, we ignore the set names and identify sets just
by the roots of the trees representing them.
For example: if we determine that element ‘i’ is in a tree with root ‘j’ has a pointer to entry
‘k’ in the set name table, then the set name is just name[k]

For unite (adding or combine) to a particular set we use FindPointer function.

Example: If you wish to unite to Si and Sj then we wish to unite the tree with roots
FindPointer (Si) and FindPointer (Sj)
FindPointer is a function that takes a set name and determines the root of the tree that
represents it.
For determining operations:
Find(i) 1St determine the root of the tree and find its pointer to entry in setname table.
Union(i, j) Means union of two trees whose roots are i and j.

If set contains numbers 1 through n, we represents tree node

P[1:n].
nMaximum number of elements.

Each node represent in array

i 1 2 3 4 5 6 7 8 9 10
P -1 5 -1 3 -1 3 1 1 1 5
Find(i) by following the indices, starting at i until we reach a node with parent value -1.
Example: Find(6) start at 6 and then moves to 6’s parent. Since P[3] is negative, we reached
the root.

DESIGN AND ANALYSIS OF ALGORITHMS Page 34

 Algorithm for finding Union(i, j): Algorithm for find(i)
Algorithm Simple union(i, j) Algorithm SimpleFind(i)
{ {
P[i]:=j; // Accomplishes the union While(P[i]≥0) do i:=P[i];
} return i;
}

If n numbers of roots are there then the above algorithms are not useful for union and find.
For union of n trees Union(1,2), Union(2,3), Union(3,4),…..Union(n-1,n).
For Find i in n trees Find(1), Find(2),….Find(n).

Time taken for the union (simple union) is  O(1) (constant).

For the n-1 unions O(n).

Time taken for the find for an element at level i of a tree is  O(i).
For n finds  O(n2).

To improve the performance of our union and find algorithms by avoiding the creation of
degenerate trees. For this we use a weighting rule for union(i, j)

Weighting rule for Union(i, j):

If the number of nodes in the tree with root ‘i’ is less than the tree with root ‘j’, then make ‘j’
the parent of ‘i’; otherwise make ‘i’ the parent of ‘j’.

DESIGN AND ANALYSIS OF ALGORITHMS Page 35

 Algorithm for weightedUnion(i, j)
Algorithm WeightedUnion(i,j)
//Union sets with roots i and j, i≠j
// The weighting rule, p[i]= -count[i] and p[j]= -count[j].
{
temp := p[i]+p[j];
if (p[i]>p[j]) then
{ // i has fewer nodes.
P[i]:=j;
P[j]:=temp;
}
else
{ // j has fewer or equal nodes.
P[j] := i;
P[i] := temp;
}
}

For implementing the weighting rule, we need to know how many nodes there are
in every tree.
For this we maintain a count field in the root of every tree.
i root node
count[i] number of nodes in the tree.
Time required for this above algorithm is O(1) + time for remaining unchanged is
determined by using Lemma.

Lemma:- Let T be a tree with m nodes created as a result of a sequence of unions each
performed using WeightedUnion. The height of T is no greater than
|log2 m|+1.

DESIGN AND ANALYSIS OF ALGORITHMS Page 36

Collapsing rule: If ‘j’ is a node on the path from ‘i’ to its root and p[i]≠root[i], then set
p[j] to root[i].
Algorithm for Collapsing find.
Algorithm CollapsingFind(i)
//Find the root of the tree containing element i.
//collapsing rule to collapse all nodes form i to the root.
{
r;=i;
while(p[r]>0) do r := p[r]; //Find the root.
While(i ≠ r) do // Collapse nodes from i to root r.
{
s:=p[i];
p[i]:=r;
i:=s;
}
return r;
}

Collapsing find algorithm is used to perform find operation on the tree created by
WeightedUnion.

For example: Tree created by using WeightedUnion

Now process the following eight finds: Find(8), Find(8),……….Find(8)

If SimpleFind is used, each Find(8) requires going up three parent link fields for a total of 24
moves to process all eight finds.

DESIGN AND ANALYSIS OF ALGORITHMS Page 37

When CollapsingFind is uised the first Find(8) requires going up three links and then
resetting two links. Total 13 movies requies for process all eight finds.

Spanning Tree:-
Let G=(V<E) be an undirected connected graph. A sub graph t=(V,E1) of G is a spanning tree
of G iff t is a tree.

Spanning Trees have many applications.

Example:-

It can be used to obtain an independent set of circuit equations for an electric network.
Any connected graph with n vertices must have at least n-1 edges and all connected graphs
with n-1 edges are trees. If nodes of G represent cities and the edges represent possible
communication links connecting two cities, then the minimum number of links needed to
connect the n cities is n-1.
There are two basic algorithms for finding minimum-cost spanning trees, and both are greedy
algorithms
Prim’s Algorithm
Kruskal’s Algorithm

DESIGN AND ANALYSIS OF ALGORITHMS Page 38

Prim’s Algorithm: Start with any one node in the spanning tree, and repeatedly add the
cheapest edge, and the node it leads to, for which the node is not already in the spanning tree.

Kruskal’s Algorithm: Start with no nodes or edges in the spanning tree, and repeatedly add
the cheapest edge that does not create a cycle.

Connected Component:
Connected component of a graph can be obtained by using BFST (Breadth first search and
traversal) and DFST (Dept first search and traversal). It is also called the spanning tree.
BFST (Breadth first search and traversal):
 In BFS we start at a vertex V mark it as reached (visited).
 The vertex V is at this time said to be unexplored (not yet discovered).
 A vertex is said to been explored (discovered) by visiting all vertices adjacent from it.
 All unvisited vertices adjacent from V are visited next.
 The first vertex on this list is the next to be explored.
 Exploration continues until no unexplored vertex is left.
 These operations can be performed by using Queue.

This is also called connected graph or spanning tree.

Spanning trees obtained using BFS then it called breadth first spanning trees.
Algorithm for BFS to convert undirected graph G to Connected component or spanning
tree.

Algorithm BFS(v)
// a bfs of G is begin at vertex v
// for any node I, visited[i]=1 if I has already been visited.
// the graph G, and array visited[] are global
{

DESIGN AND ANALYSIS OF ALGORITHMS Page 39

U:=v; // q is a queue of unexplored vertices.
Visited[v]:=1;
Repeat{
For all vertices w adjacent from U do
If (visited[w]=0) then
{
Add w to q; // w is unexplored
Visited[w]:=1;
}
If q is empty then return; // No unexplored vertex.
Delete U from q; //Get 1st unexplored vertex.
} Until(false)
}

Maximum Time complexity and space complexity of G(n,e), nodes are in adjacency list.
T(n, e)=θ(n+e)
S(n, e)=θ(n)

If nodes are in adjacency matrix then

T(n, e)=θ(n2)
S(n, e)=θ(n)

DFST(Dept first search and traversal).:

 Dfs different from bfs
 The exploration of a vertex v is suspended (stopped) as soon as a new vertex is
reached.
 In this the exploration of the new vertex (example v) begins; this new vertex has been
explored, the exploration of v continues.
 Note: exploration start at the new vertex which is not visited in other vertex exploring
and choose nearest path for exploring next or adjacent vertex.

DESIGN AND ANALYSIS OF ALGORITHMS Page 40

Algorithm for DFS to convert undirected graph G to Connected component or spanning
tree.

Algorithm dFS(v)
// a Dfs of G is begin at vertex v
// initially an array visited[] is set to zero.
//this algorithm visits all vertices reachable from v.
// the graph G, and array visited[] are global
{
Visited[v]:=1;
For each vertex w adjacent from v do
{
If (visited[w]=0) then DFS(w);
{
Add w to q; // w is unexplored
Visited[w]:=1;
}
}

Maximum Time complexity and space complexity of G(n,e), nodes are in adjacency list.
T(n, e)=θ(n+e)
S(n, e)=θ(n)

If nodes are in adjacency matrix then

T(n, e)=θ(n2)
S(n, e)=θ(n)
Bi-connected Components:

DESIGN AND ANALYSIS OF ALGORITHMS Page 41

A graph G is biconnected, iff (if and only if) it contains no articulation point (joint or
junction).
A vertex v in a connected graph G is an articulation point, if and only if (iff) the deletion of
vertex v together with all edges incident to v disconnects the graph into two or more none
empty components.

The presence of articulation points in a connected graph can be an undesirable(un wanted)

feature in many cases.
For example
if G1Communication network with
Vertex  communication stations.
Edges Communication lines.

Then the failure of a communication station I that is an articulation point, then we loss the
communication in between other stations. F
Form graph G1

(Here 2 is articulation point)

If the graph is bi-connected graph (means no articulation point) then if any station i
fails, we can still communicate between every two stations not including station i.

DESIGN AND ANALYSIS OF ALGORITHMS Page 42

From Graph Gb

There is an efficient algorithm to test whether a connected graph is biconnected. If the case of
graphs that are not biconnected, this algorithm will identify all the articulation points.
Once it has been determined that a connected graph G is not biconnected, it may be desirable
(suitable) to determine a set of edges whose inclusion makes the graph biconnected.

DESIGN AND ANALYSIS OF ALGORITHMS Page 43

UNIT III:
Greedy method: General method, applications - Job sequencing with deadlines, 0/1
knapsack problem, Minimum cost spanning trees, Single source shortest path problem.
Dynamic Programming: General method, applications-Matrix chain multiplication, Optimal
binary search trees, 0/1 knapsack problem, All pairs shortest path problem, Travelling sales
person problem, Reliability design.

Greedy Method:
The greedy method is perhaps (maybe or possible) the most straight forward design
technique, used to determine a feasible solution that may or may not be optimal.

Feasible solution:- Most problems have n inputs and its solution contains a subset of inputs
that satisfies a given constraint(condition). Any subset that satisfies the constraint is called
feasible solution.

Optimal solution: To find a feasible solution that either maximizes or minimizes a given
objective function. A feasible solution that does this is called optimal solution.

The greedy method suggests that an algorithm works in stages, considering one input at a
time. At each stage, a decision is made regarding whether a particular input is in an optimal
solution.

Greedy algorithms neither postpone nor revise the decisions (ie., no back tracking).
Example: Kruskal’s minimal spanning tree. Select an edge from a sorted list, check, decide,
and never visit it again.
Application of Greedy Method:
 Job sequencing with deadline
 0/1 knapsack problem
 Minimum cost spanning trees
 Single source shortest path problem.

Algorithm for Greedy method

Algorithm Greedy(a,n)
//a[1:n] contains the n inputs.
{
Solution :=0;
For i=1 to n do
{
X:=select(a);
If Feasible(solution, x) then
Solution :=Union(solution,x);
}
Return solution;
}
Selection  Function, that selects an input from a[] and removes it. The selected input’s
value is assigned to x.
Feasible  Boolean-valued function that determines whether x can be included into the
solution vector.
Union  function that combines x with solution and updates the objective function.

DESIGN AND ANALYSIS OF ALGORITHMS Page 44

Knapsack problem

The knapsack problem or rucksack (bag) problem is a problem in combinatorial optimization: Given a set of
items, each with a mass and a value, determine the number of each item to include in a collection so that the
total weight is less than or equal to a given limit and the total value is as large as possible

There are two versions of the problems

1. 0/1 knapsack problem

2. Fractional Knapsack problem
a. Bounded Knapsack problem.
b. Unbounded Knapsack problem.

Solutions to knapsack problems

 Brute-force approach:-Solve the problem with a straight farward algorithm

 Greedy Algorithm:- Keep taking most valuable items until maximum weight is
reached or taking the largest value of eac item by calculating vi=valuei/Sizei
 Dynamic Programming:- Solve each sub problem once and store their solutions in
an array.

DESIGN AND ANALYSIS OF ALGORITHMS Page 45

0/1 knapsack problem:

Let there be items, to where has a value and weight . The maximum
weight that we can carry in the bag is W. It is common to assume that all values and weights
are nonnegative. To simplify the representation, we also assume that the items are listed in
increasing order of weight.

Maximize subject to

Maximize the sum of the values of the items in the knapsack so that the sum of the weights must be less
than the knapsack's capacity.
Greedy algorithm for knapsack
Algorithm GreedyKnapsack(m,n)
// p[i:n] and [1:n] contain the profits and weights respectively
// if the n-objects ordered such that p[i]/w[i]>=p[i+1]/w[i+1], m size of knapsack and
x[1:n] the solution vector
{
For i:=1 to n do x[i]:=0.0
U:=m;
For i:=1 to n do
{
if(w[i]>U) then break;
x[i]:=1.0;
U:=U-w[i];
}
If(i<=n) then x[i]:=U/w[i];
}

Ex: - Consider 3 objects whose profits and weights are defined as

(P1, P2, P3) = ( 25, 24, 15 )
W1, W2, W3) = ( 18, 15, 10 )
n=3number of objects
m=20Bag capacity

Consider a knapsack of capacity 20. Determine the optimum strategy for placing the objects
in to the knapsack. The problem can be solved by the greedy approach where in the inputs
are arranged according to selection process (greedy strategy) and solve the problem in
stages. The various greedy strategies for the problem could be as follows.

(x1, x2, x3) ∑ xiwi ∑ xipi

(1, 2/15, 0) 2 2
18x1+ x15 = 20 25x1+ x 24 = 28.2
15 15
(0, 2/3, 1) 2 2
x15+10x1= 20 x 24 +15x1 = 31
3 3

DESIGN AND ANALYSIS OF ALGORITHMS Page 46

(0, 1, ½ ) 1 1
1x15+ x10 = 20 1x24+ x15 = 31.5
2 2
(½, ⅓, ¼ ) ½ x 18+⅓ x15+ ¼ x10 = 16. 5 ½ x 25+⅓ x24+ ¼ x15 =
12.5+8+3.75 = 24.25

Analysis: - If we do not consider the time considered for sorting the inputs then all of the
three greedy strategies complexity will be O(n).

Job Sequence with Deadline:

There is set of n-jobs. For any job i, is a integer deadling di≥0 and profit Pi>0, the profit Pi is
earned iff the job completed by its deadline.

To complete a job one had to process the job on a machine for one unit of time. Only one
machine is available for processing jobs.

A feasible solution for this problem is a subset J of jobs such that each job in this subset can
be completed by its deadline.

The value of a feasible solution J is the sum of the profits of the jobs in J, i.e., ∑i∈jPi
An optimal solution is a feasible solution with maximum value.

The problem involves identification of a subset of jobs which can be completed by its
deadline. Therefore the problem suites the subset methodology and can be solved by the
greedy method.

DESIGN AND ANALYSIS OF ALGORITHMS Page 47

Ex: - Obtain the optimal sequence for the following jobs.
j1 j2 j3 j4
(P1, P2, P3, P4) = (100, 10, 15, 27)

(d1, d2, d3, d4) = (2, 1, 2, 1)

n =4

Feasible Processing Value

solution sequence
j1 j2
(2,1) 100+10=110
(1, 2)
(1,3) (1,3) or (3,1) 100+15=115
(1,4) (4,1) 100+27=127
(2,3) (2,3) 10+15=25
(3,4) (4,3) 15+27=42
(1) (1) 100
(2) (2) 10
(3) (3) 15
(4) (4) 27

In the example solution ‘3’ is the optimal. In this solution only jobs 1&4 are processed and
the value is 127. These jobs must be processed in the order j4 followed by j1. the process of
job 4 begins at time 0 and ends at time 1. And the processing of job 1 begins at time 1 and
ends at time2. Therefore both the jobs are completed within their deadlines. The optimization
measure for determining the next job to be selected in to the solution is according to the
profit. The next job to include is that which increases ∑pi the most, subject to the constraint
that the resulting “j” is the feasible solution. Therefore the greedy strategy is to consider the
jobs in decreasing order of profits.

DESIGN AND ANALYSIS OF ALGORITHMS Page 48

The greedy algorithm is used to obtain an optimal solution.

We must formulate an optimization measure to determine how the next job is chosen.

algorithm js(d, j, n)
//d dead line, jsubset of jobs ,n total number of jobs
// d[i]≥1 1 ≤ i ≤ n are the dead lines,
// the jobs are ordered such that p[1]≥p[2]≥---≥p[n]
//j[i] is the ith job in the optimal solution 1 ≤ i ≤ k, k subset range
{
d[0]=j[0]=0;
j[1]=1;
k=1;
for i=2 to n do{
r=k;
while((d[j[r]]>d[i]) and [d[j[r]]≠r)) do
r=r-1;
if((d[j[r]]≤d[i]) and (d[i]> r)) then
{
for q:=k to (r+1) setp-1 do j[q+1]= j[q];
j[r+1]=i;
k=k+1;
}
}
return k;
}

Note: The size of sub set j must be less than equal to maximum deadline in given list.

Single Source Shortest Paths:

 Graphs can be used to represent the highway structure of a state or country with
vertices representing cities and edges representing sections of highway.
 The edges have assigned weights which may be either the distance between the 2
cities connected by the edge or the average time to drive along that section of
highway.
 For example if A motorist wishing to drive from city A to B then we must answer the
following questions
o Is there a path from A to B
o If there is more than one path from A to B which is the shortest path
 The length of a path is defined to be the sum of the weights of the edges on that path.

Given a directed graph G(V,E) with weight edge w(u,v). e have to find a shortest path from

source vertex S∈v to every other vertex v1∈ v-s.

DESIGN AND ANALYSIS OF ALGORITHMS Page 49

  To find SSSP for directed graphs G(V,E) there are two different algorithms.

 Bellman-Ford Algorithm
 Dijkstra’s algorithm

 Bellman-Ford Algorithm:- allow –ve weight edges in input graph. This algorithm
either finds a shortest path form source vertex S∈V to other vertex v∈V or detect a –
ve weight cycles in G, hence no solution. If there is no negative weight cycles are
reachable form source vertex S∈V to every other vertex v∈V
 Dijkstra’s algorithm:- allows only +ve weight edges in the input graph and finds a
shortest path from source vertex S∈V to every other vertex v∈V.

 Consider the above directed graph, if node 1 is the source vertex, then shortest path
from 1 to 2 is 1,4,5,2. The length is 10+15+20=45.

 To formulate a greedy based algorithm to generate the shortest paths, we must

conceive of a multistage solution to the problem and also of an optimization measure.

 This is possible by building the shortest paths one by one.

 As an optimization measure we can use the sum of the lengths of all paths so far
generated.

 If we have already constructed ‘i’ shortest paths, then using this optimization measure,
the next path to be constructed should be the next shortest minimum length path.

 The greedy way to generate the shortest paths from Vo to the remaining vertices is to
generate these paths in non-decreasing order of path length.

 For this 1st, a shortest path of the nearest vertex is generated. Then a shortest path to
the 2nd nearest vertex is generated and so on.

DESIGN AND ANALYSIS OF ALGORITHMS Page 50

 Algorithm for finding Shortest Path

Algorithm ShortestPath(v, cost, dist, n)

//dist[j], 1≤j≤n, is set to the length of the shortest path from vertex v to vertex j in graph g
with n-vertices.
// dist[v] is zero
{
for i=1 to n do{
s[i]=false;
dist[i]=cost[v,i];
}
s[v]=true;
dist[v]:=0.0; // put v in s
for num=2 to n do{
// determine n-1 paths from v
choose u form among those vertices not in s such that dist[u] is minimum.
s[u]=true; // put u in s
for (each w adjacent to u with s[w]=false) do
if(dist[w]>(dist[u]+cost[u, w])) then
dist[w]=dist[u]+cost[u, w];
}
}

Minimum Cost Spanning Tree:

SPANNING TREE: - A Sub graph ‘n’ of o graph ‘G’ is called as a spanning tree if
(i) It includes all the vertices of ‘G’
(ii) It is a tree

Minimum cost spanning tree: For a given graph ‘G’ there can be more than one spanning
tree. If weights are assigned to the edges of ‘G’ then the spanning tree which has the
minimum cost of edges is called as minimal spanning tree.

The greedy method suggests that a minimum cost spanning tree can be obtained by contacting
the tree edge by edge. The next edge to be included in the tree is the edge that results in a
minimum increase in the some of the costs of the edges included so far.

There are two basic algorithms for finding minimum-cost spanning trees, and both are greedy
algorithms
Prim’s Algorithm
Kruskal’s Algorithm
Prim’s Algorithm: Start with any one node in the spanning tree, and repeatedly add the
cheapest edge, and the node it leads to, for which the node is not already in the spanning tree.

DESIGN AND ANALYSIS OF ALGORITHMS Page 51

PRIM’S ALGORITHM: -
i) Select an edge with minimum cost and include in to the spanning tree.
ii) Among all the edges which are adjacent with the selected edge, select the one
with minimum cost.
iii) Repeat step 2 until ‘n’ vertices and (n-1) edges are been included. And the sub
graph obtained does not contain any cycles.

Notes: - At every state a decision is made about an edge of minimum cost to be included
into the spanning tree. From the edges which are adjacent to the last edge included in the
spanning tree i.e. at every stage the sub-graph obtained is a tree.

DESIGN AND ANALYSIS OF ALGORITHMS Page 52

 Prim's minimum spanning tree algorithm
Algorithm Prim (E, cost, n,t)
// E is the set of edges in G. Cost (1:n, 1:n) is the
// Cost adjacency matrix of an n vertex graph such that
// Cost (i,j) is either a positive real no. or ∞ if no edge (i,j) exists.
//A minimum spanning tree is computed and
//Stored in the array T(1:n-1, 2).
//(t (i, 1), + t(i,2)) is an edge in the minimum cost spanning tree. The final cost is returned
{
Let (k, l) be an edge with min cost in E
Min cost: = Cost (x,l);
T(1,1):= k; + (1,2):= l;
for i:= 1 to n do//initialize near
if (cost (i,l)<cost (i,k) then n east (i): l;
else near (i): = k;
near (k): = near (l): = 0;
for i: = 2 to n-1 do
{//find n-2 additional edges for t
let j be an index such that near (i) 0 & cost (j, near (i)) is minimum;
t (i,1): = j + (i,2): = near (j);
min cost: = Min cost + cost (j, near (j));
near (j): = 0;
for k:=1 to n do // update near ()
if ((near (k) 0) and (cost {k, near (k)) > cost (k,j)))
then near Z(k): = ji
}
return mincost;
}

The algorithm takes four arguments E: set of edges, cost is nxn adjacency matrix cost of
(i,j)= +ve integer, if an edge exists between i&j otherwise infinity. ‘n’ is no/: of vertices. ‘t’ is a
(n-1):2matrix which consists of the edges of spanning tree.
E = { (1,2), (1,6), (2,3), (3,4), (4,5), (4,7), (5,6), (5,7), (2,7) }
n = {1,2,3,4,5,6,7)

DESIGN AND ANALYSIS OF ALGORITHMS Page 53

 i) The algorithm will start with a tree that includes only minimum cost edge of
G. Then edges are added to this tree one by one.
ii) The next edge (i,j) to be added is such that i is a vertex which is already
included in the treed and j is a vertex not yet included in the tree and cost of
i,j is minimum among all edges adjacent to ‘i’.
iii) With each vertex ‘j’ next yet included in the tree, we assign a value near ‘j’.
The value near ‘j’ represents a vertex in the tree such that cost (j, near (j)) is
minimum among all choices for near (j)
iv) We define near (j):= 0 for all the vertices ‘j’ that are already in the tree.
v) The next edge to include is defined by the vertex ‘j’ such that (near (j))  0 and
cost of (j, near (j)) is minimum.
Analysis: -
The time required by the prince algorithm is directly proportional to the no/: of vertices. If a
graph ‘G’ has ‘n’ vertices then the time required by prim’s algorithm is 0(n2)

DESIGN AND ANALYSIS OF ALGORITHMS Page 54

Kruskal’s Algorithm: Start with no nodes or edges in the spanning tree, and repeatedly
add the cheapest edge that does not create a cycle.
In Kruskals algorithm for determining the spanning tree we arrange the edges in the
increasing order of cost.
i) All the edges are considered one by one in that order and deleted from the graph
and are included in to the spanning tree.
ii) At every stage an edge is included; the sub-graph at a stage need not be a tree.
Infect it is a forest.
iii) At the end if we include ‘n’ vertices and n-1 edges without forming cycles then we
get a single connected component without any cycles i.e. a tree with minimum
cost.
At every stage, as we include an edge in to the spanning tree, we get disconnected trees
represented by various sets. While including an edge in to the spanning tree we need to
check it does not form cycle. Inclusion of an edge (i,j) will form a cycle if i,j both are in same
set. Otherwise the edge can be included into the spanning tree.
Kruskal minimum spanning tree algorithm
Algorithm Kruskal (E, cost, n,t)
//E is the set of edges in G. ‘G’ has ‘n’ vertices
//Cost {u,v} is the cost of edge (u,v) t is the set
//of edges in the minimum cost spanning tree
//The final cost is returned
{ construct a heap out of the edge costs using heapify;
for i:= 1 to n do parent (i):= -1 // place in different sets
//each vertex is in different set {1} {1} {3}
i: = 0; min cost: = 0.0;
While (i<n-1) and (heap not empty))do
{
Delete a minimum cost edge (u,v) from the heaps; and reheapify using adjust;
j:= find (u); k:=find (v);
if (jk) then
{ i: = 1+1;
+ (i,1)=u; + (i, 2)=v;
mincost: = mincost+cost(u,v);
Union (j,k);
}
}
if (in-1) then write (“No spanning tree”);
else return mincost;
}

Consider the above graph of , Using Kruskal's method the edges of this graph are considered
for inclusion in the minimum cost spanning tree in the order (1, 2), (3, 6), (4, 6), (2, 6), (1, 4),
(3, 5), (2, 5), (1, 5), (2, 3), and (5, 6). This corresponds to the cost sequence 10, 15, 20, 25,
30, 35, 40, 45, 50, 55. The first four edges are included in T. The next edge to be considered
is (I, 4). This edge connects two vertices already connected in T and so it is rejected. Next,
the edge (3, 5) is selected and that completes the spanning tree.

DESIGN AND ANALYSIS OF ALGORITHMS Page 55

Analysis: - If the no/: of edges in the graph is given by /E/ then the time for Kruskals
algorithm is given by 0 (|E| log |E|).

DESIGN AND ANALYSIS OF ALGORITHMS Page 56