Algorithm Notes
Algorithm Notes
UNIT I
INTRODUCTION
Algorithm analysis: Time and space complexity - Asymptotic Notations and its
properties Best case, Worst case and average case analysis – Recurrence relation:
substitution method - Lower bounds – searching: linear search, binary search and
Interpolation Search, Pattern search: The naïve string matching algorithm - Rabin-
Karp algorithm - Knuth-Morris-Pratt algorithm. Sorting: Insertion sort – heap sort
PART A
19. How to measure an algorithm’s running time? Nov/Dec 2017, Apr/May 2024
Unit for measuring the running time is the algorithms basic operation. The running time
is measured by the count of no. of times the basic operations is executed.
Basic operation: the operation that contributes the most to the total running time.
Example: the basic operation is usually the most time-consuming operation in the
algorithm’s innermost loop.
1 Constant
log n Logarithmic
n Linear
n log n Linearithmic
n2 Quadratic
n3 Cubic
2n Exponential
n! Factorial
24. What are six steps processes in algorithmic problem solving? Dec 2009
Understanding the problem.
Ascertaining the capabilities of a computational device.
Choosing between exact and approximate problem solving.
Deciding on appropriate data structures.
Algorithm Design Techniques.
Methods of specifying an algorithm
Proving an algorithm's correctness.
Analysing an algorithm.
Coding an algorithm.
26. How is the efficiency of the algorithm defined? Or How do you measure the
efficiency of an algorithm? May/June 2019
The efficiency of an algorithm is defined with the components.
(i) Time efficiency -indicates how fast the algorithm runs
(ii) Space efficiency -indicates how much extra memory the algorithm
needs
28. What are the different criteria used to improve the effectiveness of algorithm?
(i) The effectiveness of algorithm is improved, when the design, satisfies the
44. what do you mean worst case efficiency of [Link]/Dec 2017, Apr/May 2024
The worst case analysis of an algorithm is analysing the algorithm for the worst case
input of size n, for which the algorithm runs the longest among all the possible inputs of
that size.
[Link] an algorithm that finds the number of binary digits in the binary
representation ofa positive decimal integer. (AU april/may 2015)
Number of major comparisons=⌊ log2n⌋ + 1∈log2n.
Algorithm :
Finding the number of binary digits in the binary representation of a positive decimal
integer.
Algorithm Binary(n)
count:=1;
whilen >1
do
count:=count+ 1;
n:=⌊ n/2⌋ ;
end
return count;
46. Write down the properties of asymptotic notations. (AU april/may 2015)
The following property is useful in analyzing algorithms that comprise two
consecutively executed parts.
Theorem
If t1(n) Є O(g1(n)) and t2(n) Є O(g2(n)) then,
t2(n) Є O(g2(n))
t2(n) ≤ C2 (g2(n)) for all n ≥ n2
Let us denote,
C3=max {C1, C2} and
Consider n ≥ max {n1, n2}, so that both the inequalities can be used.
The addition of two inequalities becomes,
t1(n)+ t2(n) ≤ C1 (g1(n))+ C2 (g2(n))
≤ C3 (g1(n))+ C3 (g2(n))
≤ C3 2 max{g1(n), (g2(n))}
Hence,
t1(n) +t2(n) Є O (max {g1(n),g2(n)}),
47. Give the Euclid’s algorithm for computing gcd(m, n) (AU nov 2016) or write an
algorithm to compute the greatest common divisor of two numbers. (Apr-2017, 18)
ALGORITHM Euclid_gcd(m, n)
//Computes gcd(m, n) by Euclid’s algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: Greatest common divisor of m and n
while n ≠ 0 do
r ←m mod n
m←n
n←r
return m
Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12.
[Link] the order of growth n(n-1)/2 and n2. (AU nov 2016)
if n<1
return n
Else
return F(n-1)+(n-2)
the algorithm’s basic operation is addition.
Let A(n) is the number of additions performed by the algorithm to compute F(n).
The number of additions needed to compute F(n-1) is A(n-1) and the number of
additions needed to compute F(n-2) is A(n-2).
The worst-case complexity of the algorithm is the function defined by the maximum number
of steps taken on any instance of size n. It represents the curve passing through the highest
point of each column.
The best-case complexity of the algorithm is the function defined by the minimum number of
steps taken on any instance of size n. It represents the curve passing through the lowest
point of each column.
Finally, the average-case complexity of the algorithm is the function defined by the average
number of steps taken on any instance of size n.
Worst-case - O(logn)
The worst occurs when the algorithm keeps on searching for the target element
until the size of the array reduces to 1. Since the number of comparisons
required is logn, the time complexity is O(logn).
The Pattern Searching algorithms are sometimes also referred to as String Searching
Algorithms. These algorithms are useful in the case of searching a pattern in a string.
through every character in the initial phase rather it filters the characters that do not
match and then performs the comparison.
Initially calculate the hash value of the pattern.
Start iterating from the starting of the string:
o Calculate the hash value of the current substring having length m.
o If the hash value of the current substring and the pattern are same, check
if the substring is same as the pattern.
o If they are same, store the starting index as a valid answer. Otherwise,
continue for the next substrings.
Return the starting indices as the required answer.
60. Define Sorting.
Sorting is the processing of arranging the data in ascending and descending order.
There are several types of sorting in data structures namely,
Bubble sort
Insertion sort
Selection sort
Bucket sort
Heap sort
Quick sort
Radix sort etc.
PART – B
Diagram:
Algorithm heading
It consists of name of algorithm, problem description, input
Algorithm Body
and output.
It consists of logical body of the algorithm by making use of
various programming constructs and assignment statement.
used to return control from one point to another. Generally used while exiting
from function
Note: The statements in an algorithm executes in sequential order i.e. in the
same order as they appear – one after the other
For k ← 1 to n do
C[I ,j ] ←c[i, j] +A[i,k]B[k,j]
Implementation of algorithms
An algorithm describes what the program is going to perform. It states some of the actions
to be executed and the order in which these actions are to be executed.
The various steps in developing algorithm are,
1. Finding a method for solving a problem. Every step of an algorithm should be in
a precise and in a clear manner. Pseudo code is also used to describe the
algorithm.
2. The next step is to validate the algorithm. This step includes, all the algorithm
should be done manually by giving the required input, performs the required
steps including in the algorithm and should get the required amount of output in
a finite amount of time.
3. Finally, implement the algorithm in terms of programming language.
Order of an algorithm
The order of an algorithm is a standard notation of an algorithm that has been
developed to represent function that bound the computing time for algorithms.
It is an order notation. It is usually referred as O-notation.
Example
Problem size = 'n'
Analysis framework
o The efficiency of an algorithm can be decided by measuring the performance
of an algorithm.
o The performance of an algorithm is computed by two factors
amount of time required by an algorithm to execute
amount of storage required by an algorithm
Overview
(i) Space complexity
(ii) Time complexity
(iii) Measuring an Input's size
(iv) Measuring Running Time
(v)Orders of Growth
i++ n times
sum = sum + a[i] n times
Total 3n + 2
words.
But for many algorithms the running time depends not only on an input size but
also on the specifics of a particular input.
= +n(1-p)
Cavg(n)= + n(1-p)
Example:
o If p = 1 (i.e.) if the search is successful, then the average number of key
comparisons made by sequential search is (n+1)/2.
o If p = 0 (i.e.) if the search is unsuccessful, then the average number of key
comparisons will be 'n' because the algorithm will inspect all n elements on
all such inputs.
3. Explain the Asymptotic Notations and its properties? Or explain briefly Big oh
notation, Omega notation and Theta notation give an example (Apr/May-2017) or what
are the Rules of Manipulate Big-Oh Expression and about the typical growth rates of
algorithms? Nov/Dec 2017 Nov/Dec 2018 OR Define Big O notation, Big Omega and Big
Theta Notation. Depict the same graphically and explain. May/June 2018, Nov/Dec 2019,
Apr/May 2024 OR Explain various complexity measures and the role of asymptotic
notations toward algorithm analysis. ( Nov/Dec 2024)
Asymptotic Notations
Asymptotic notations are mathematical tools to represent the time and space
complexity of algorithms for asymptotic analysis.
if n = 2 then,
t(n) = 2n + 2
= 2(2) +2
t(n) = 6
And g(n) = n2
= (2) 2
g(n) = 4
i.e t(n) > g(n)
if n = 3 then,
t(n) = 2n + 2
= 2(3) +2
t(n) = 8
And g(n) = n2
= (3) 2
g(n) = 9
Definition
A function t(n) is said to be in Ω(g(n)) (t(n) Є Ω(g(n))),
if t(n) is bounded below by constant multiple of g(n) for all values of n, and if there exist
a positive constant c and non negative integer n0 such that
t(n) ≥ c*g(n) for all n ≥ n0.
Example:
Consider t(n)=2n2 + 5 and g(n) = 7n
Then if n = 0
t(n) = 2 (0)2 + 5
=5
g(n) = 7(0)
= 0 i.e t(n) > g(n)
But if n = 1
t(n) = 2 (1)2 + 5
=7
g(n) = 7(1)
= 7 i.e t(n) = g(n)
But if n = 2
t(n) = 2 (2)2 + 5
= 13
g(n) = 7(2)
= 14 i.e. t(n) < g(n)
But if n = 3
t(n) = 2 (3)2 + 5
= 18 + 5
= 23
g(n) = 7(3)
= 21 i.e t(n) > g(n)
Thus for n>3 we get t(n) > c * g(n).
It can be represented as
2n2 + 5 Ω(n)
Example :
If t(n) = 2n + 8 and g(n) = 7n, 5n
Where n ≥ 2
C2*g(n) ≤ t(n) ≤ c1*g(n) for all n ≥ n0
Θ(g(n)) = O(g(n) ) Ω(g(n))
(t(n) Є Θ(g(n)))
Similarly t(n) = 2n + 8
g(n) = 7n
g(n) = 5n
i.e 5n < 2n + 8 < 7n for n ≥ 2
Here c2 = 5 and c1 = 7 with n0 = 2
Little oh notation(o)
The function t(n) = o(g(n)), if O(g(n)) and t(n) <> (g(n))
Example
t(n) = 3n+2
Where n>0, 3n+2 ≤ 5 n2
By definition of Big Oh
t(n) = Cg(n)
C = 5; g(n) = n2
But t(n) = 3n+2 < > (n2)
Therefore t(n) = 3n+2 = o(n2)
Let us denote,
C3=max {C1, C2} and
Consider n ≥ max {n1, n2}, so that both the inequalities can be used.
The addition of two inequalities becomes,
The property implies that the algorithms overall efficiency will be determined by
the part with a larger order of growth.
(i.e.) its least efficient part is
t1(n) Є O(g1(n)) t1(n) +t2(n) Є O (max {g1(n),g2(n)})
t2(n) Є O(g2(n))
Stirling’s formula
Recurrence Relation
A recurrence relation is an equation that defines a sequence based on a rule that gives
the next term as a function of the previous term(s). It helps in finding the subsequent
term (next term) with the previous term. If we know the previous term in a given
series, then we can easily determine the next term.
Example 1:
Example 2:
Recursive definition for Fibonacci sequence
Fib(n)=Fib(n−1)+Fib(n−2)
Recurrence relations are often used to model the cost of recursive functions. For
example, the number of multiplications required by a recursive version of the factorial
function for an input of size n will be zero when n=0 or n=1 (the base cases), and it will
be one plus the cost of calling fact on a value of n−1.
General plan for analyzing efficiency of Recursive algorithms
Mathematical Analysis:
Step 1: The algorithm’s input size is n.
Step 2: The algorithm’s basic operation in computing factorial is multiplication .
Step 3 : The recursive function call can be formulated as
According to the formula, F(n) is computed as
F(n) = F(n-1) * n, for n>0
And the number of execution is denoted by M(n).
The number of multiplication M(n) is computed as
M(n) = M(n-1) + 1, for n>0
To compute To multiply
F(n-1) F(n-1) by n
Forward Substitution:
M(1) = M(0) +1
M(2) = M(1) + 1 = 1 + 1 =2
M(3) = M(2) + 1 = 2 + 1=3
The recurrence relation and the initial condition for the algorithm
number of multiplication M(n) is
M(n)=M(n-1)+1,for n<0, M(0)=0
Backward substitution:
M(n) = M(n-1) + 1
Substitute M(n-1) = M(n-2) + 1
Now M(n) becomes
M(n) = [M(n-2)+1]+1
= M(n-2) + 2
Substitute M(n-2) =M(n-3)+1
Now M(n) becomes
M(n)=[M(n-3)+1] + 2
= M(n-3) + 3
From the substitution method we can establish a general formula as :
M(n)= M(n-i) + i;
Since n=0, substitute i=n;
Now let us prove correctness of this formula using mathematical induction as
follows
Proof
M(n) = n by using mathematical induction
Basis : let n = 0 then
M(n) =0
i.e M(0) = 0=n
Induction: if we assume M(n – 1) = n-1 then
M(n) = M( n-1) + 1
= n-1 + 1
=n
i.e M(n) = n Thus the time complexity of factorial function is Θ (n)
5. Give the general plan for Analyzing the time efficiency of Recursive Algorithms
and use recurrence to find number of moves for Towers of Hanoi problem.
May/June 2018
o In this puzzle, there are n disks of different sizes, and three pegs.
o Initially all the disks are on the first peg in order if size, the largest on the bottom
and the smallest on the top as shown in Fig 1.4
o The goal is to move all the disks from peg 1 to peg 3 using peg 2 as auxiliary.
o One disk should be moved at a time and do not place a larger disk on top of a
smaller one.
The following steps are used to move n>1 disks from peg 1 to peg 3, peg 2 as auxiliary
as shown in Fig 1.5
1. Move n-1 disks recursively from peg 1 to peg 3.( peg 2 as auxiliary).
2. Move the largest disk directly from peg 1 to peg 3.
3. Move n-1 disks recursively from peg 2 to peg 3.( peg 2 as
auxiliary).
For example, if n=1 then the single disks is moved from source peg to destination peg
directly.
A B C
M(n)=2M(n-1)+1,for n>1
M(1)=1
The recurrence relation is solved by using backward substitution method
Backward substitution Method
M(n)=2M(n-1)+1
Substitute
M(n-1)=2M(n-2)+1
M(n)=2[2M(n-2)+1]+1
M(n)=22M(n-2)+2+1
Substitute
M(n-2)=2M(n-3)+1
Now, M(n) becomes
M(n)=22[2M(n-3)+1]+2+1
M(n)=23[M(n-3)+22+2+1
Hence after I substitution M(n) becomes
M(n)=2iM(n-i)+2i-1+2i-2+2i-3+…….2+1
=2iM(n-i)+2i-1
Therefore te general formula is 2iM(n-i)+2i-1
= A(2k−2) + 2
substitute A(2k−2) = A(2k−3) + 1
= [A(2k−3) + 1] + 2
= A(2k−3) + 3 ... ...
After i iteration
A(2k) = A(2k−i) + i
= A(2k−k) + k
= A(20) + k
= A(1) + k
Thus, we end up with
A(2k) = A(1) + k = k
After returning to the original variable
n = 2k and hence k = log2 n,
A(n) = log2 n ∈ Ө(log n)
Example : Fibonacci series
A sequence of Fibonacci numbers is 0,1,1,2,3,5,8,13,21,34………..
The Fibonacci sequence can be defined by the simple recurrence
F(n)=F(n-1)+F(n-2),for n>1…………………1
The two initial conditions are
F(0)=0
F(1)=1
Explicit formula for the nth Fibonacci number
Backward substitution method is not used to solve the recurrence F(n)=F(n-1)+F(n-
2),for n>1,because which fails to produce easily discernible pattern.
So, the theorem that describes solution to a homogeneous second order linear
recurrence with constant coefficient is used to solve the problem.
The homogenous with constant coefficient is
ax(n)+bx(n-1)+cx(n-2)=0 ……………(2)
Where,
a,b,c are fixed real numbers called the coefficients of recurrence and a≠0
x(n) is the unknown sequence to be found
R1,2=
R1,2=
R1=
R2=
The characteristics equation has two distinct real roots.
Now the recurrence relation is
X(n)=αr1n+βr2n ……..(5)
Substitute r1 and r2 in (5),
α( )+β( )=0
( ) β-( ) β=-1
+ β- + β = -1
β = -1
β=-
Substitute β = - in (9)
α+β=0
α- =0
α= β=-
F(n) = n- n
F(n) =
Where
Φ=
Φ = 1.61803
Φ^ =-
Φ^ = - 0.61803
The constant Φ is known as, Golden Ratio.
The value of Φ^ is lies between -1 and 0.
When n goes to infinity, Φ^ gets infinitely small value. So, it can be omitted.
Therefore F(n) = Φn
So, for every non negative n, F(n) = Φ n is rounded to the nearest integer.
return n
Else
return F(n-1)+(n-2)
the algorithm’s basic operation is addition.
Let A(n) is the number of additions performed by the algorithm to compute F(n).
The number of additions needed to compute F(n-1) is A(n-1) and the number of
additions needed to compute F(n-2) is A(n-2).
The algorithm needs one more addition to compute the sum of A(n-1) and A(n-2).
Thus the recurrence for A(n) is
A(n)=A(n-1) + A(n-2)+1, for n>1
A(0)=0
A(1)=0
The recurrence A(n)-A(n-1)-A(n-2)=1 is same as F(n)-F(n-1)-F(n-2)=0, but its right
hand side not equal to zero. These recurrences are called inhomogeneous
recurrences.
General techniques are used to solve inhomogeneous recurrences.
The inhomogeneous recurrences is converted into homogeneous recurrence by
rewriting the in homogeneous recurrence as,
A(n)+1]-[A(n-1)+1]-[A(n-2)+1]=0
Now substitute, B(n)=A(n)+1
Now (14) becomes, B(n)-B(n-1)-B(n-2)=0
B(0)=0
B(1)=1
Here B(n)=F(n+1)
Since B(n)=A(n)+1
B(n-1)=A(n)
So A(n)=B(n)-1
Substitute F(n+1)-1
We know that
F(n)=
F(n+1)=
A(n)= -1
Hence
A(n)€
The poor efficiency class of algorithm could be anticipated from the class of recurrence
The reason behind the algorithm inefficiency can be traced by looking at the tree of
recursive calls n=6
The same values of the function are evaluated again and again which is extremely
inefficiently.
T(n)=2T(n/2)+3
=2{(2T(n/2)+3)/2}+3
=2{(2T(n/4)+3/2}+3
....
=4T(n/4)+6
= 4{(2T(n/2)+3)/4}+6
.....
=8T(n/8)+9
----
=2kT(n/2k)+3n
T(n)=nlogn+3n Time complexity=o(nlog n)
T(n)=2T(n/2)+cn
=2{(2T(n/2)+cn)/2}+cn
=2{(2T(n/4)+cn/2}+cn
----
=4T(n/4)+cn+cn
= 4{(2T(n/8)+cn/4}+ cn+cn
------
=8T(n/8)+ cn+cn+cn
---
=2kT(n/2k)+k(cn)
T(n)=nlogn+ k(cn)
Time complexity=o(nlog n)
7. Show the following equalities are correct. June 2013, Nov 2010
i. 5n2-6n = Φ(n2)
ii. n!=O(nn)
iii. n3+106n2=Θ(n3)
iv. 2n22n + n log n = Θ(n22n)
8. Prove that for any two functions f(n) and g(n), we have f(n)-> Θ(g(n))
if and only if f(n) -> O(g(n)) and f(n) ->Ω(g(n)) Nov 2010
Given function:
f(n) and g(n)
f(n)= O(g(n)) when f(n) ≤C1g(n) for all n≥n0---------(1)
f(n)= Ω(g(n)) when f(n) ≥C2g(n) for all n≥n0---------(2)
from (1) and (2)
C2 g(n) ≤f(n) ≤ C1g(n) for all n≥n0 -------(3)
(i.e) Θ(g(n)) = O(g(n)) Ω(g(n))
From (3) f(n) = Θ(g(n)) hence proved
9. Derive the worst case analysis of merge sort using suitable illustration (AU april
2015)
Efficiency of Merge Sort:
In merge sort algorithm the two recursive calls are made. Each recursive call
focuses on n/2 elements of the list .
After two recursive calls one call is made to combine two sublist i.e to merge all
n elements.
Hence we can write recurrence relation as
T(n) = T(n/2) + T(n/2) + cn
T(n/2) = Time taken by left sublist
T(n/2) = time taken by right sublist
T(n) = time taken for combining two sublists
where n> 1 T (1) = 0
The time complexity of merge sort can be calculated using two methods
Master theorem
Substitution method
Master theorem
Let , the recurrence relation for merge sort is
T(n) = T(n/2) + T(n/2) + cn
Let T(n) = aT(n/b) + f(n) be a recurrence relation
i.e. T(n) = 2T(n/2) + cn ------- ( 1 )
T(1) = 0 ----------- (2 )
As per master theorem T(n) = Θ (n d long n ) if a = b
As equation ( 1),a =2 , b = 2 and f(n) = cn and a = bd i.e 2 = 2`
This case gives us , T (n) =Θ (n log2 n)
Hence the average and worst case time complexity of merge sort is
C worst (n) = (n log2 n)
Substitution method Let, the recurrence relation for merge sort be
T(n) = T(n/2) + T(n/2) + cn for n>1
i.e. T(n) = 2T(n/2) + cn for n>1 ------- (3)
T(1) = 0 -------(4)
Let us apply substitution on equation ( 3) .
Assume n=2k
T(n) = 2T(n/2) + cn
T(n) = 2T(2k/2 ) + c.2k
T(2k) = 2T(2k-1) + c.2k
If k = k-1 then,
T(2k) = 2T(2k-1) + c.2k
T(2k) = 2[2T(2k-2) + c.2k -1] + c.2k
T(2k) = 22 T(2k-2) + 2.c.2k -1 + c .2k
T(2k) = 22 T(2k-2) + 2.c.2k /2 + c.2k
T(2k) = 22 T(2k-2) + c.2k + c.2k
T(2k) = 22 T(2k-2) + 2c .2k
Similarly we can write,
T(2k) = 23 T(2k-3) + 3c .2k
T(2k) = 24 T(2k-4) + 4c .2k
…..
….
T(2k) = 2k T(2k-k) + k.c.2k
T(2k) = 2k T(20) + k.c.2k
T(2k) = 2k T(1) + k.c.2k -------- (5)
But as per equation (4), T(1) =0
There equation (5) becomes ,
T(2k) = 2k .0 +. k. c . 2k
T(2k) = k. c . 2k
But we assumed n=2k , taking logarithm on both sides.i.e. log 2 n = k
Therefore T(n) = log 2 n. cn
Therefore T (n) =Θ (n log2 n)
Hence the average and worst case time complexity of merge sort is
C worst (n) = (n log2 n)
Time complexity of merge sort
Best case Average case Worst case
Θ (n log2 n) Θ (n log2 n) Θ (n log2 n)
[Link] the most appropriate notation to indicate the time efficiency class of sequential
search algorithm in the worst case,best case and the average case.
Hence proved.
ALGORITHM MaxElement(A[0..n-1])
//Problem Description : This algorithm is for finding the
//maximum value element from the array
//Input:An array A[0..n-1] of real numbers
//Output: Returns the largest element from array
Maxval ← A[0]
For i ← 1 to n-1 do Searching the maximum element from an array
{
If ( A[i]>max_value)then
Maxval ← A[i] If any value is large than current
} Max_ Value then set new Max_value
Return Max_value by obtained larger value
Mathematical Analysis
Step 1: The input size is the number of elements in the array(ie.),n
Step 2 : The basic operation is comparison in loop for finding larger value There are
two
operations in the for loop
Comparison operation a[i]->maxval
i+bi)= I + i R2
2. = =1+2+…..+n
=n(n+1)/2
=1/2n2 o(n2) S2
ALGORITHM UniqueElements(A[0..n-1])
//Checks whether all the elements in a given array are distinct
//Input :An array A[0..n-1]
//Output Returns ‘true’ if all elements in A are distinct and ‘false’
//otherwise
for i to n-2 do
for j i+1 to n-1 do If any two elements in the array
if a[i] = a[j] then are similar then return .false
return false indicating that the array elements
else are not distinct
return true
Mathematical analysis
Step 1: Input size is n i.e total number of elements in the array A
Step 2: The basic iteration will be comparison of two elements . this
operation the innermost operation in the loop . Hence
if a[i] = a[j] then comparison will be the basic operation .
Step 3 : The number of comparisons made will depend upon the input n .
but the algorithm will have worst case complexity if the same
element is located at the end of the list. Hence the basic operation
depends upon the input n and worst case
Step 4: The worst case input is an array for which the number od elements
comparison cworst(n) is the largest among the size of the array.
There are two kinds of worst case inputs, They are
[Link] with no equal elements.
[Link] in which the last two elements are pair of equal elements.
For the above inputs, one comparison is made for each repetition of the inter most
loop (ie) for each value of the loop's variable 'j' between its limits i+1 and n-1 and
this is repeated limit for each values of the outer loop (ie) for each value of the
loop's variable `i' between 0 and n-2. Accordingly,
Cworst(n) =
= Θ
= -
= (n-1)
= (( n2 – n) / 2
=1/2 n2 Θ (n2)
We can say that in the worst case the algorithm needs to compare all
n (n – 1 )/2 distinct of its n elements.
13. Explain in detail the various Searching techniques with an example. (APR/MAY
2023), Apr/May 2024 or Describe Binary search and interpolation search algorithm
with an [Link] its respective complexity measures.( Nov/Dec 2024)
Example
Fig 1.7 The Element is FOUND. Hence stop the searching process.
defLinearSearch(mylist, n, k):
for j in range(0, n):
if (mylist[j] == k):
return j
return -1
mylist = [1, 3, 5, 7, 9]
print("Given Elements : ", mylist)
Execution:
Input
Given Elements : [1, 3, 5, 7, 9]
Enter the element to be searched : 3
Output
Element found at index: 1
Space Complexity
The space complexity of the linear search is O(1), as we don't need any auxiliary
space for the algorithm.
Fig 1.8 :The Element is FOUND. Hence stop the searching process.
myarray = [3, 4, 5, 6, 7, 8, 9]
print("Elements in the array: " , myarray)
x = int(input("Enter the element to be searched : "))
result = mybinarySearch(myarray, x, 0, len(myarray)-1)
if result != -1:
print("Element is present at index :" + str(result))
else:
print("Element not found ")
Execution:
Input
Elements in the array: [33, 44, 55, 66, 77, 88, 99]
Enter the element to be searched: 66
Output
Element is present at index :3
Program:
Def mybinary_search(myarr, low, high, x):
if high >= low:
mid = (high + low) // 2
if myarr[mid] == x:
return mid
# If element is smaller than mid, then it can only
# be present in left subarray
elifmyarr[mid] > x:
return mybinary_search(myarr, low, mid - 1, x)
# Else the element can only be present in right subarray
else:
return mybinary_search(myarr, mid + 1, high, x)
else:
# Element is not present in the array
return -1
# Test data
myarr = [ 2, 3, 4, 10, 40 ]
print("Elements in the array :", myarr)
# Function call
result = mybinary_search(myarr, 0, len(myarr)-1, x)
if result != -1:
print("Element is present at index : ", str(result))
else:
print("Element is not present in array")
Execution:
Input
Elements in the array : [2, 3, 4, 10, 40]
Enter the element to be searched : 10
Output
Element is present at index : 3
n = len(arr)
index = interpolationSearch(arr, 0, n - 1, x)
if index != -1:
print("Element found at index", index)
else:
print("Element not found")
Execution:
Input
Elements in the array : [10, 12, 13, 16, 18, 19, 20, 21, 22,
23, 24, 33, 35, 42, 47]
Enter the element to be searched : 20
Output
Element found at index 6
Worst-case - O(n)
The worst case occurs when the given data set is exponentially distributed.
If the data set is sorted and uniformly distributed, then it takes O(log(log(n)))
time as on an average (log(log(n))) comparisons are made as shown in Table
1.5 Space Complexity
Since no extra space is needed, the space complexity of the interpolation search
is O(1).
14. Explain in detail the Pattern Search or String Searching Algorithms with Various
string matching algorithms. (APR/MAY 2023), Apr/May 2024
The Pattern Searching algorithms are sometimes also referred to as String Searching
Algorithms. These algorithms are useful in the case of searching a pattern in a string.
Input:
string = “This is my class room”
pattern = “class”
Output:
Pattern found at index 11
Input:
string = “AABAACAADAABAABA”
pattern = = “AABA”
Output:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
string = "hellohihello"
print("Given String : ", string)
pattern = input("Enter the pattern to be searched :")
naïve_algorithm(string, pattern)
Execution:
Input
Given String : hellohihello
Enter the pattern to be searched :hi
Output
Pattern found at index: 5
Space Complexity
Since no extra space is needed, the space complexity of the naïve search is O(1).
Disadvantage:
Naive method is inefficient because information from a shift is not used again.
every character in the initial phase rather it filters the characters that do not match and then
performs the comparison as shown in Fig 1.10
Initially calculate the hash value of the pattern.
Start iterating from the starting of the string:
o Calculate the hash value of the current substring having length m.
o If the hash value of the current substring and the pattern are same, check if the
substring is same as the pattern.
o If they are same, store the starting index as a valid answer. Otherwise, continue
for the next substrings.
Return the starting indices as the required answer.
Step 2:
Here, we have taken first ten alphabets only (i.e. A to J) and given the weights.
A B C D E F G H I J
1 2 3 4 5 6 7 8 9 10
Step 3:
n Length of the text
mLength of the pattern
Here, n = 10 and m = 3.
d Number of characters in the input set.
Here, we have taken input set {A, B, C, ..., J}. So, d = 10.
Step 5:
We calculate the hash value of the next window by subtracting the first term and adding
the next term as shown below.
Simple Numerical example:
o Pattern length is 3 and string is “23456”
o Let us assume that we computed the value of the first window as 234.
o How to compute the value of the next window “345”?
It’s just (234 – 2*100)*10 + 5 and we get 345.
hash value for text(t) = ((1 * 102) + ((2 * 101) + (3 * 100) - (1 * 102)) * 10 + (3 * 100)) mod 13
= 233 mod 13
= 12
For BCC, t = 12 (≠6). Therefore, go for the next window.
After a few searches, we will get the match for the window CDA in the text.
d = 10
def search(pattern, text, q):
m = len(pattern)
n = len(text)
p = 0
t = 0
h = 1
i = 0
j = 0
for i in range(m-1):
h = (h*d) % q
j += 1
if j == m:
print("Pattern is found at position: " + str(i+1))
if i< n-m:
t = (d*(t-ord(text[i])*h) + ord(text[i+m])) % q
if t < 0:
t = t+q
text = "hihellohi"
print("Given String : ", text)
pattern = input("Enter the pattern to be searched :")
q = int(input("Enter the prime number :"))
search(pattern, text, q)
Execution:
Input
Given String : hihellohi
Enter the pattern to be searched :hello
Enter the prime number :3
Output
Pattern is found at position: 3
The worst case of the Rabin-Karp algorithm occurs when all characters of pattern and
text are the same as the hash values of all the substrings of text matches with the hash
value of pattern.
Space Complexity
Since no extra space is needed, the space complexity of the naïve search is O(1).
Step 1: Define a one dimensional array with the size equal to the length of the Pattern.
(LPS[size])
Step 2: Define variables i& j. Set i = 0, j = 1 and LPS[0] = 0.
Step 3: Compare the characters at Pattern[i] and Pattern[j].
Step 4: If both are matched then set LPS[j] = i+1 and increment both i& j values by one.
GotoStep 3.
Step 5: If both are not matched then check the value of variable 'i'. If it is '0' then set LPS[j] = 0
and increment 'j' value by one, if it is not '0' then set i = LPS[i-1]. Goto Step 3.
Step 6: Repeat above steps until all the values of LPS[] are filled.
Example:
Given Pattern Initialize LPS[] table with size 7 which is equal to
A B C D A B D the length of the pattern
0 1 2 3 4 5 6
LPS
Step 1:
Define variables i& j.
Set i = 0, j= 1 and LPS[0] = 0.
0 1 2 3 4 5 6
LPS 0
Step 2:
Compare Pattern[i] with Pattern[j] ====>A is compared with B. Since both were not
matching, check the value of i.
i = 0, so set LPS[j] = 0 and increment ‘j’ value by 1.
0 1 2 3 4 5 6
LPS 0 0
Now, i = 0 & j = 2
Step 3:
Compare Pattern[i] with Pattern[j] ====>A is compared with C. Since both were not
matching, check the value of i.
i = 0, so set LPS[j] = 0 and increment ‘j’ value by 1.
0 1 2 3 4 5 6
LPS 0 0 0
Now, i = 0 & j = 3
Step 4:
Compare Pattern[i] with Pattern[j] ====>A is compared with D. Since both were not
matching, check the value of i.
i = 0, so set LPS[j] = 0 and increment ‘j’ value by 1.
0 1 2 3 4 5 6
LPS 0 0 0 0
Now, i = 0 & j = 4
Step 5:
Compare Pattern[i] with Pattern[j] ====>A is compared with A. Since both are
matching, set LPS[j] = i+1 and increment both ‘i’ & ‘j’ value by 1.
0 1 2 3 4 5 6
LPS 0 0 0 0 1
Now, i = 1 & j = 5
Step 6:
Compare Pattern[i] with Pattern[j] ====>B is compared with B. Since both are
matching, set LPS[j] = i+1 and increment both ‘i’ & ‘j’ value by 1.
0 1 2 3 4 5 6
LPS 0 0 0 0 1 2
Now, i = 2 & j = 6
Step 7:
Compare Pattern[i] with Pattern[j] ====>C is compared with D. Since both were not
matching, check the value of i.
i !=0, so set i= LPS[i-1]====>i= LPS[2-1]
i= 0
0 1 2 3 4 5 6
LPS 0 0 0 0 1 2
Now, i = 0 & j = 6
Step 7:
Compare Pattern[i] with Pattern[j] ====>A is compared with D. Since both were not
matching, check the value of i.
i = 0, so set LPS[j] = 0 and increment ‘j’ value by 1.
0 1 2 3 4 5 6
LPS 0 0 0 0 1 2 0
Now, i = 0 & j = 7
Example:
Consider the following Text and Pattern
Text : ABC ABCDAB ABCDABCDABDE
Pattern : ABCDABD
LPS[] table for the above pattern is as follows:
0 1 2 3 4 5 6
LPS 0 0 0 0 1 2 0
Step 1:
Start comparing the first character of the pattern with the first character of Text
from left to right.
Text A B C A B C D A B A B C D A B C D A B D E
0 1 2 3 4 5 6
Pattern A B C D A B D
Step 2:
Start comparing first charater in pattern with next character in Text.
Text A B C A B C D A B A B C D A B C D A B D E
0 1 2 3 4 5 6
Pattern A B C D A B D
Step 3:
Since LPS value is ‘2’ no need to compare Pattern[0] & Pattern[1] values..
Text A B C A B C D A B A B C D A B C D A B D E
0 1 2 3 4 5 6
Pattern A B C D A B D
Here mismatch occurs at pattern[2]. We need to consider LPS[2] value is ‘0’. Hence
compare first charater in pattern with next character in Text.
Step 4:
Since LPS value is ‘2’ no need to compare Pattern[0] & Pattern[1] values..
Text A B C A B C D A B A B C D A B C D A B D E
0 1 2 3 4 5 6
Pattern A B C D A B D
Step 5:
Since LPS value is ‘2’ no need to compare Pattern[0] & Pattern[1] values. Compare
pattern[2] with mismatched character in Text.
Text A B C A B C D A B A B C D A B C D A B D E
0 1 2 3 4 5 6
Pattern A B C D A B D
Here all the characters of the pattern matched with the substring in the Text, which
starts at index value 15. Hence, conclude that pattern found at index 15.
initial_point = []
m = 0
n = 0
while m != a:
if text[m] == pattern[n]:
m += 1
n += 1
else:
n = prefix_arr[n-1]
if n == b:
initial_point.append(m-n)
n = prefix_arr[n-1]
elif n == 0:
m += 1
return initial_point
Execution:
Input
Given String : hihellohihellohi
Enter the pattern to be searched :hi
Output
Pattern is found at index: 0
Pattern is found at index: 7
Pattern is found at index: 14
Insertion Sort
Insertion sort is a simple sorting algorithm that works similar to the way you
play cards in your hands. The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and placed at the correct position in
the sorted part as shown in fig 1.11
Second Pass:
Now, move to the next two elements and compare them
11 12 13 5 6
Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence,
no swapping will occur. 12 also stored in a sorted sub-array along with 11
Third Pass:
Now, two elements are present in the sorted sub-array which are 11 and 12
Moving forward to the next two elements which are 13 and 5
11 12 13 5 6
Both 5 and 13 are not present at their correct place so swap them
11 12 5 13 6
After swapping, elements 12 and 5 are not sorted, thus swap again
11 5 12 13 6
Here, again 11 and 5 are not sorted, hence swap again
5 11 12 13 6
Fourth Pass:
Now, the elements which are present in the sorted sub-array are 5, 11 and 12
Moving to the next two elements 13 and 6
5 11 12 13 6
Clearly, they are not sorted, thus perform swap between both
5 11 12 6 13
Now, 6 is smaller than 12, hence, swap again
5 11 6 12 13
Here, also swapping makes 11 and 6 unsorted hence, swap again
5 6 11 12 13
Finally, the list is completely sorted.
definsertionSort(arr):
for index in range(1,len(arr)):
currentvalue = arr[index]
position = index
arr[position]=currentvalue
arr = [54,26,93,17,77,91,31,44,55,20]
print("Given list : ", arr)
insertionSort(arr)
print("Sorted list : ",arr)
Execution:
Input
Given list : [54, 26, 93, 17, 77, 91, 31, 44, 55, 20]
Output
Sorted list : [17, 20, 26, 31, 44, 54, 55, 77, 91, 93]
Space Complexity
Space complexity of insertion sort is O(1)
[Link] Heap sort and Explain in detail about the Heap sort. Aprl/May 2024
Heap sort is a comparison-based sorting technique based on Binary Heap data
structure. It is similar to the selection sort where we first find the minimum element and place
the minimum element at the beginning.
Repeat the same process for the remaining elements. Heap sort processes the elements
by creating the min-heap or max-heap using the elements of the given array. Min-heap or max-
heap represents the ordering of array in which the root element represents the minimum or
maximum element of the array as shown in Fig 1.12
Heap
A heap is a complete binary tree, and the binary tree is a tree in which the node can have
the utmost two children. A complete binary tree is a binary tree in which all the levels
except the last level, i.e., leaf node, should be completely filled, and all the nodes should
be left-justified.
A complete binary tree has an interesting property that we can use to find the children
and parents of any node.
If the index of any element in the array is i, the element in the index 2i+1 will become
the left child and element in 2i+2 index will become the right child. Also, the parent of
any element at index iis given by the lower bound of (i-1)/2 as shown in Table 1.4
Example:
Given array elements:
0 1 2 3 4 5
1 12 9 5 6 10
Array is converted to Heap
Steps
Heapify:Heapify the root element again so that we have the highest element at root.
Step 4: Put the removed element into the Sorted list.
Step 5: Repeat the same until Max Heap becomes empty.
Step 6:Display the sorted list.
6 7
0 1 2 3 4 5
81 89 9 11 14 76 54 22
Array is
converted
to Heap
After converting the given heap into max heap, the array elements are -
0 1 2 3 4 5 6 7
89 81 76 22 14 9 54 11
Next, we have to delete the root element (89) from the max heap. To delete this node, we have
to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify
it to convert it into max heap.
After swapping the array element 89 with 11, and converting the heap into max-heap, the
elements of array are –
0 1 2 3 4 5 6 7
81 22 76 11 14 9 54 89
In the next step, again, we have to delete the root element (81) from the max heap. To delete
this node, we have to swap it with the last node, i.e. (54). After deleting the root element, we
again have to heapify it to convert it into max heap.
After swapping the array element 81 with 54 and converting the heap into max-heap, the
elements of array are –
0 1 2 3 4 5 6 7
76 22 54 11 14 9 81 89
In the next step, we have to delete the root element (76) from the max heap again. To delete this
node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again
have to heapify it to convert it into max heap.
After swapping the array element 76 with 9 and converting the heap into max-heap, the
elements of array are –
0 1 2 3 4 5 6 7
54 22 9 11 14 76 81 89
In the next step, again we have to delete the root element (54) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (14). After deleting the root element, we again
have to heapify it to convert it into max heap.
After swapping the array element 54 with 14 and converting the heap into max-heap, the
elements of array are –
0 1 2 3 4 5 6 7
22 14 9 11 54 76 81 89
In the next step, again we have to delete the root element (22) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again
have to heapify it to convert it into max heap.
After swapping the array element 22 with 11 and converting the heap into max-heap, the
elements of array are –
0 1 2 3 4 5 6 7
14 11 9 22 54 76 81 89
In the next step, again we have to delete the root element (14) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.
After swapping the array element 14 with 9 and converting the heap into max-heap, the
elements of array are –
0 1 2 3 4 5 6 7
11 9 14 22 54 76 81 89
In the next step, again we have to delete the root element (11) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again
have to heapify it to convert it into max heap.
After swapping the array element 11 with 9, the elements of array are –
0 1 2 3 4 5 6 7
9 11 14 22 54 76 81 89
Now, heap has only one element left. After deleting it, heap will be empty.
/* 5.2.5 Python Program to sort the elements in the list using Heap sort */
defheapify(array, a, b):
largest = b
l = 2 * b + 1
root = 2 * b + 2
# Change root
if largest != b:
array[b], array[largest] = array[largest], array[b]
heapify(array, a, largest)
# Building maxheap..
for b in range(a // 2 - 1, -1, -1):
heapify(array, a, b)
# swap elements
for b in range(a-1, 0, -1):
array[b], array[0] = array[0], array[b]
heapify(array, b, 0)
array = [81,89,9,11,14,76,54,22]
print("Original Array :", array)
Heap_Sort(array)
a = len(array)
print ("Sorted Array : ", array)
Execution:
Input
Original Array : [81, 89, 9, 11, 14, 76, 54, 22]
Output
Sorted Array : [9, 11, 14, 22, 54, 76, 81, 89]
It occurs when the array elements are required to be sorted in reverse order. It means
suppose we need to sort the array elements in ascending order, but its elements are in
descending order.
Average case complexity - O(nlogn)
It occurs when the array elements are in jumbled order that is not properly ascending and
not properly descending as shown in Table 1.8
Space Complexity
Space complexity of Heap sort is O(1)
IMPORTANT QUESTIONS
Part A
Part B
1. Find the time complexity and space complexity of the following problems. Factorial using
recursion and compute the nth Fibonacci number using iterative statements. Dec 2012
[Link] the following recurrence relations: Dec 2012
1. T(n)= 2T(n/2)+3 n>2
2 n=2
[Link] between Big Oh, Theta and Omega notation. Dec 2012
[Link] the best case, average and worst case analysis for linear search. Dec 2012
[Link] how time complexity is calculated. Give an example. Apr 2010
[Link] on asymptotic notation with example. Apr 2010
[Link] explain the time complexity, space complexity estimation June 2013
[Link] linear search algorithm and analyse its complexity. June 2013
[Link] the following equalities are correct June 2013
i. 5n2-6n = Φ(n2)
ii. n!=O(nn)
iii. n3+106n2=Θ(n3)
iv. 2n22n + n log n = Θ(n22n)
10. What is space complexity? With an example explain the components of fixed and variable
part in space complexity. June 2014
[Link] towers of Hanoi problem and solve it using recursion. June 2014
[Link] the recurrence relation for Fibonacci series algorithm : also carry out time
complexity analysis. June 2014
[Link] in details about the efficiency of the algorithm with [Link] 2014
14. Explain the procedure to calculate the time complexity of binarysearch using nonrecursive
Algm.
[Link] briefly the time complexity and space complexity [Link] 2010
[Link] a linear search algorithm and analyse its best, worst and average case time
complexity.
[Link] that for any two functions f(n) and g(n), we have f(n)-> Θ(g(n))
if and only if f(n) - > O(g(n)) and f(n) ->Ω(g(n)) Nov 2010
APRIL/MAY 2024
PART A
1. How to measure an algorithm’s running time? Nov/Dec 2017, Apr/May 2024 [Link] 4
[Link].19
2. what do you mean worst case efficiency of algorithm. Nov/Dec 2017, Apr/May 2024 [Link] 8
[Link].44
PART B
1. Explain the Asymptotic Notations and its properties? Or explain briefly Big oh notation, Omega
notation and Theta notation give an example (Apr/May-2017) or what are the Rules of Manipulate
Big-Oh Expression and about the typical growth rates of algorithms? Nov/Dec 2017 Nov/Dec 2018
OR Define Big O notation, Big Omega and Big Theta Notation. Depict the same graphically and
explain. May/June 2018, Nov/Dec 2019, Apr/May 2024 [Link] 23 [Link].3
2. Use Substitution method to shoe that T(n)= 2T(n/2)+n is O(n log(n)) Apr/May 2024 [Link] 42
[Link].6
3. Explain in detail the various Searching techniques with an example. (APR/MAY 2023),
Apr/May 2024 [Link] 50 [Link].13
4. Explain the working of naïve string matching algorithm with ABCCDDAEFG as the text
input and CDD as the search string. Apr/May 2024 [Link] 59 [Link].14
PART C
16. (a) (i) How many spurious hits does the Rabin-Karp matcher encounter in the text
T3141592653589793 when Working modulo q 11 and looking for the pattern P = 26. Briefly write
about the processing time, worst-case running time and average-case running time of Rabin-Karp
algorithm. [Link] 62, Q.no14 & Refer Class work
(ii) With an example to show the best-case, worst-case and average case analysis of heap sort.
[Link] 74, Q.no16
Nov/Dec 2024
PART-A
[Link] time complexity of an [Link].6
[Link] is reccurence relation? [Link].38
PART – B
[Link] various complexity measures and the role of asymptotic notations toward algorithm
analysis. [Link].3
[Link] Binary search and interpolation search algorithm with an [Link] its
respective complexity measures. [Link].13
PART - A
Example:
Example:
The weight of an edge is a positive value that may be representing the distance
between the vertices or the weights of the edges along the path.
Example:
10. What does traversing a graph mean? State the different ways of traversing a
graph? ( Nov/Dec 2024)
Traversing a graph means visiting all the nodes in the graph. The two important
graph traversal methods are
Depth first traversal or depth first search (DFS)
Breadth first traversal or breadth first search (BFS)
11. Prove that the number of odd degree vertices in a connected graph should be
even. (May/June 2007)
The sum of degree of all the vertices is equal to the sum of the degree of all the
odd degree vertices plus sum of the degree of all the even degree vertices.
Sum = 2 * e. where e denotes edges.
Sum of the degree of all odd degree vertices is even.
3
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
15. How a graph is represented?OR What are the representation of the graphs?
[Apr/May 2015] Nov/Dec 2018 Aprl/May2024
There are two way of representing the graph are
Adjacency matrix representation
Adjacency list representation
Number of vertices is 4
Number of edges is 6
20. Define indegree and outdegree of a graph. (Nov/Dec 2011) ( Nov/Dec 2024)
Indegree
Indegree of a vertex in a digraph is the number of edges that are incident on it.
Outdegree
Outdegree of vertex is the number of edges that leave the vertex.
Eg:
Indegree(V1) = 1
Indegree(V2) = 1
Outdegree(V3) = 1
Outdegree(V4) = 1
4
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Biconnectivity
A connected undirected graph is biconnected if there are no vertices if there are no
vertices whose remo0vel disconnects the rest of the graph.
help of queue i.e. FIFO implementation. help of Stack i.e. LIFO implementations.
This algorithm works in single stage. The This algorithm works in two stages – in the
visited vertices are removed from the queue first stage the visited vertices are pushed
and then displayed at once. onto the stack and later on when there is no
vertex further to visit those are popped-off.
BFS is slower than DFS. DFS is more fasterthan BFS.
BFS requires morememory compare to DFS. DFS require less memory compare to BFS
BFS is useful in finding shortest path. BFS DFS in not so useful in finding shortest path.
can be used to find the shortest distance It is used to perform a traversal of a general
between some starting node and the graph and the idea of DFS is to make a path
remaining nodes of the graph. as long as possible, and then go back
(backtrack) to add branches also as long as
possible.
B D
A topological sort is given by : B,A,D,C,E. there could be several topological sorts for a
given DAG.
A B
C D
F
G E 6
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
B A
C D
F
G E
Here the removel of ‘C’ vertex will disconnect G from the graph.
Similarly removal of ‘D’ vertex will disconnect E & F from the graph. Therefore ‘C’ & ‘D’ are
articulation points.
32. Given a weighted, undirected graph with |V| nodes, assume all weights are non-
negative. If each edge has weight <= w , What can you say about the cost of Minimum
spanning tree?Apr/May 2019
Given an undirected and connected graph G=(V,E), a spanning tree of the graph G is a tree
that spans G(that is, it includes every vertex of G) and is a sub graph of G (every edge in the
tree belongs to G)
7
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Minimum spanning tree has direct application in the design of networks. It is used in
algorithms approximating the travelling salesman problem, multi-terminal minimum cut
problem and minimum-cost weighted perfect matching. Other practical applications are:
1. Cluster Analysis
2. Handwriting recognition
3. Image segmentation
Multistage Graph
Optimal Binary Search Tree (OBST)
0/1 Knapsack Problem
Travelling Salesman Problem.
All Pair Shortest Path Problem
35. Define Warshall’s algorithm.
8
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
It contains exactly one vertex with no entering edges is called source and
assumed to be numbered 1.
It contains exactly one vertex with no leaving edges is called the sink and
assumed to be numbered n.
The weight u ijof each directed edge (i, j )is a positive integer, called the edge
capacity. (defines upper bound)
39. What is flow conservation requirement?
The total amount of the material entering an intermediate vertex must be equal to the
total amount of the material leaving the vertex is called the flow-conservation
requirement.
The value of a maximum flow in a network is equal to the capacity of its minimum cut.
A preflowis a flow that satisfies the capacity constraints but not the flow- conservation
requirement.
A matching in a graph is a subset of its edges with the property that no two edges share
a vertex. A maximum matching also referred as maximum cardinality matching is a
matching with the largest number of edges.
In a bipartite graph, all the vertices can be partitioned into two disjoint sets V and U,
not necessarily of the same size, so that every edge connects a vertex in one of these
sets to a vertex in the other set.
The graph G = (V, E) in which the vertex set V is divided into two disjoint sets X and Y
in such a way that every edge e € E has one end point in X and other end point in Y.
The two colorable graph is a graph that can be colored with only two colors in such a
way that no edge connect the same color .the bipartite graph is two colorable graph
9
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
48. What do you mean by perfect matching in bipartite graph? (MAY 2015, Apr/May -
2017)
A perfect matching is a matching which matches all vertices of the graph. That is, every vertex
of the graph is incident to exactly one edge of the matching. Figure (b) above is an example of a
perfect matching. Every perfect matching is maximum and hence maximal. In some literature,
the term complete matching is used. In the above figure, only part (b) shows a perfect
matching. A perfect matching is also a minimum-size edge cover. Thus, ν(G) ≤ ρ(G) , that is, the
size of a maximum matching is no larger than the size of a minimum edge cover.
Maximum flow
Definition. The capacity of an edge is a mapping c :E→R+, denoted by cuv or c(u, v). It
represents the maximum amount of flow that can pass through an edge.
Definition. A flow is a mapping f : E→R+, denoted by fuv or f (u, v), subject to the following
two constraints:
1. Capacity Constraint:
2. Conservation of Flows:
wheres is the source of N. It represents the amount of flow passing from the source to the
sink.
Maximum Flow Problem. Maximize | f |, that is, to route as much flow as possible from s to
t.
10
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Minimum cut
Definition. An s-t cutC = (S, T) is a partition of V such that s∈S and t∈T. The cut-set
of C is the set
50. What is Depth first search? Or write procedure for DFS algorithm? APR/MAY-2017
Select an unvisited node x, visit it, and treat as the current node
Find an unvisited neighbor of the current node, visit it, and make it the new current
node;
If the current node has no unvisited neighbors, backtrack to the its parent, and make
that parent the new current node;
Repeat steps 3 and 4 until no more nodes can be visited.
If there are still unvisited nodes, repeat from step 1.
Note: DFS can be implemented efficiently using a stack
11
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Prim’s algorithm is one of the ways to compute a minimum spanning tree which uses a
greedy technique. This algorithm begins with a set U initialized to {1}. It then grows a
spanning tree, one edge at a time .At each step, it finds a shortest edge(u, v) such that the
cost of(u, v) is the smallest among all edges ,where u is in Minimum spanning tree and V is
not in Minimum spanning tree.
The general method to solve the single source shortest path problem is known as
Dijkstra’s algorithm. The solution is prime example of greedy algorithms.
At each stage, it select a vertex ‘V’, which has the smallest dv among all the unknown
vertices, and declares that the shortest path form’s’ to ‘V’ is known.
Formula: To find the adjacency distance value
VW
T[W].dist=Min[T[W].dist,T[V].dist+CVW]
T[W].path=V
56. What is the principle behing Bellman-Ford algorithm to detect the negative
weight cycles? APR/MAY 2015
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general
case in which edge weights may be negative.
Given a weighted, directed graph G =(V,E) with source s and weight function w : E -> R, the
Bellman-Ford algorithm returns a boolean value indicating whether or not there is a
negative-weight cycle that is reachable from the source. If there is such a cycle, the
algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces
the shortest paths and their weights.
12
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
1 This algorithm begins to construct the This algorithm begins to construct the
shortest spanning tree from any shortest spanning tree from the vertex having
vertex in the graph. the lowest weight in the graph.
2 To obtain the minimum distance, it It crosses one node only one time.
traverses one node more than one
time.
4 In Prim’s algorithm, all the graph Kruskal’s algorithm may have disconnected
elements must be connected. graphs.
5 When it comes to dense graphs, the When it comes to sparse graphs, Kruskal’s
Prim’s algorithm runs faster. algorithm runs faster.
Slower.O(V^3)
Harder to understand
13
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
PART-B
In Directed graph, the edges between the vertices are ordered. E1 is the edge between
the vertices V1 and V2.
V1 is called the Head and V2 is called the Tail.
So, E1 is a set of (V1, V2) and not of (V2, V1).
In Undirected graph, the edges between the vertices are not ordered.
So, E1 is a set of (V1, V2) or (V2, V1).
Weighted Graphs
A graph is said to be weighted graph if every edge in the graph is assigned a weight
or value. It can be either a directed or an undirected graph.
Complete Graph
A complete graph is a graph in which there is an edge between every pair of vertices.
A complete graph with n vertices will have n(n - 1) /2 edges.
Sub Graph
A sub graph G’ of G is a graph G such that the set of vertices and set of edges of G’ are
proper subset of the set of edges of G.
Connected Graphs
An undirected graph is said to be connected if for every pair of distinct vertices Vi
and Vj, there is a path from Vi to Vj in G.
15
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Cyclic Graphs
A directed graph is said to be a cyclic graph in which no vertex is repeated except the
first and last vertex are the same.
An undirected graph is said to be a cyclic graph in which if any edge appears more
than once it appears with the same orientation.
Cycle = A BC A
Acyclic Graphs
A graph is said to be a acyclic graph if it has no cycles.
16
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Representation of graphs:
There are two representations of graphs:
Adjacency matrix representation
Adjacency lists representation
17
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
- Simple to implement
- Easy and fast to tell if a pair (i, j) is an edge: simply check if A[i][j] is 1 or 0.
- Degree of a vertex can easily be calculated by counting all non-zero entries in the
corresponding row of the adjacency matrix.
-
Disadvantages of adjacency matrix:
- No matter how few edges the graph has, the matrix takes O (n2) in memory.
A graph can also be represented using a linked list. For each vertex, a list of adjacent
vertices is maintained using a linked list. It creates a separate linked list for each vertex Vi
in the graph G = (V, E).
18
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
- Adjacency list representation of a graph is very memory efficient when the graph
has a large number of vertices but very few edges.
Disadvantages of adjacency list:
- Checking the existence of an edge between two vertices i and j is also time
consuming. Linked list of vertex i must be searched for the vertex j.
Connectivity between two vertices can be tested Vertices adjacent to another vertex can be
quickly found quickly
The order in which the vertices of a graph are visited is called as graph
traversal.
During a traversal we must keep track of which vertices have been visited. There are two
types of graph traversals:
4. Write an algorithm for depth first search (DFS)on a graph and give the nodes of the
graph ‘G’ given in the fig based on the algorithm. (NOV/DEC-2016)(APR/MAY 2023)
In DFS, go as far as possible along a single path until reach a dead end (a vertex with
no edge out or no neighbor unexplored) then backtrack. After visiting a vertex v, which is
adjacent to w1, w2, w3. Next we visit one of v's adjacent vertices, w1 say. Next, we visit all
vertices adjacent to w1 before coming back to w2, etc. Must keep track of vertices already
visited to avoid cycles. The method can be implemented using recursion or iteration.
To do this, when we visit a vertex v, we mark it visited, since now we have been there, and
recursively call depth-first search on all adjacent vertices that are not already marked.
Step 1: Choose any node in the graph. Fix it as the search node and mark it as Visited.
Step 2: Using the adjacency matrix of the graph, find a node adjacent to the search node
that has not been visited yet. Fix this as the new search node and mark it as visited.
Step 3: Repeat step 2 using the new search node. If no nodes satisfying (2) can be Found,
return to the previous search node and continue from there
Step 4: When a return to the previous search node. In (3) is impossible, the search from the
originally choose search node is complete.
Step 5: If the graph still contains unvisited nodes, choose any node that has not been
visited and repeat step (1) through (4).
20
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
B D E
V A B C D E
A 0 1 0 0 1
B 1 0 1 1 0
C 0 1 0 1 1
D 0 1 1 0 0
E 1 0 1 0 0
Implementation
2. B is adjacent node of A which is not visited and call DFS(B) then mark B as visited.
A
3. C is adjacent node of B which is not visited and call DFS(C) then mark C as visited.
21
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
4. D is adjacent node of C which is not visited and call DFS(D) then mark D as visited.
A
D E
Since all the vertices starting from ‘A’ are visited, the above graph is said to be connected. If
the graph is not connected, then processing all nodes requires calls to DFS, and each
generates a tree. This entire collection is a defth first spanning forest.
22
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
ALGORITHM
DFS traversal of the graph produces the minimum spanning tree and all pair
shortest path tree for an unweighted graph.
Detects cycle in a graph
Path Finding
Topological Sorting
To test if a graph is bipartite (Bipartite means the vertices can be colored red or
black such that no edge links vertices of the same color).
Finding Strongly Connected Components of a graph.
Solving puzzles with only one solution, such as mazes.
Time Complexity
23
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
5. Write an algorithm for breadth first search on a graph and give the nodes of the
graph ‘G’ given in the fig based on the algorithm. (NOV/DEC-2016)(APR/MAY 2023)
Breath First Search (BFS) of a graph, G starts from an unvisited vertex u. Then all unvisited
vertices vi adjacent to u are visited and then all unvisited vertices wj adjacent to vi are
visited and so on. The traversal terminates when there are no more nodes to visit.
STEPS:
Step 1: Choose any node in the graph, fix it as the search node and mark it as visited.
Step 2: Using the adjacency matrix of the graph, find all the unvisited adjacent nodes to the
search node and enqueue them in to the queue Q.
Step 3: Then the node which is dequeued from the queue. Mark that node as visited and fix
it as the new search node.
Step 5: This process continues until queue Q which keeps track of the adjacent nodes is
Empty.
B D E
24
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
V A B C D E
A 0 1 0 0 1
B 1 0 1 1 0
C 0 1 0 1 1
D 0 1 1 0 0
E 1 0 1 0 0
Implementation
2. Find the adjacent unvisited vertices of ‘A’ and enqueue then into the queue. Here B and E
are adjacent node of A.
Queue Q:
B E
3. Then vertex ‘B’ is dequeued and marks it as visited. Its adjacent vertices C and D are
taken from the adjacency matrix for enqueuing.
Queue Q:
E C D
4. Then vertex ‘E’ is dequeued and marks it as visited. Its adjacent vertex C is taken from
the adjacency matrix for enqueuing. Since vertex C is already in the queue, it’s not
enqueued.
Queue Q:
C D
Here E is dequeued.
5. Then vertex ‘C’ is dequeued and marks it as visited. Its adjacent vertices B, D and E are
taken, in which vertices B and E are visited and vertex D is already in the queue, so all
vertices are not enqueued.
Queue Q:
D
25
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Here C is dequeued.
6. Then vertex ‘D’ is dequeued and marks it as [Link] this process terminates
since all the vertices are visited and the queue is also empty.
Queue Q:
Null
Here D is dequeued.
B E
D
D
Algorithm:
BFS(vertices, start)
Input: The list of vertices, and the start vertex.
Output: Traverse all of the nodes, if the graph is connected.
Begin
define an empty queue que
at first mark all nodes status as unvisited
add the start vertex into the que
whileque is not empty, do
delete item from que and set to u
display the vertex u
for all vertices 1 adjacent with u, do
if vertices[i] is unvisited, then
mark vertices[i] as temporarily visited
add v into the queue
mark
done
mark u as completely visited
26
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
done
End
Applications of BFS
Find and report a path with the minimum number of edges between two given
vertices.
Find a simple cycle, if there is one.
To find Shortest path
To find Single Source & All pairs shortest paths
Used to construct a Spanning tree
Used to check Connectivity
6. Explain the graph connectivity With an examples.
Connectivity
A graph is said to be connected if there is a path between every pair of vertex. From
every vertex to any other vertex, there should be some path to traverse. That is called the
connectivity of a graph. A graph with multiple disconnected vertices and edges is said to be
disconnected.
Example 1
In the following graph, it is possible to travel from one vertex to any other vertex. For
example, one can traverse from vertex 'a' to vertex 'e' using the path 'a-b-e'.
Example 2
In the following example, traversing from vertex 'a' to vertex 'f' is not possible because
there is no path between them directly or indirectly. Hence it is a disconnected graph.
27
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Connectivity Types
Graph Connectivity can be classified broadly into two categories −
Edge Connectivity
Vertex Connectivity
Edge Connectivity
Let 'G' be a connected graph. The minimum number of edges whose removal makes 'G'
disconnected is called edge connectivity of G.
Notation − λ(G)
In other words, the number of edges in a smallest cut set of G is called the edge
connectivity of G.
If 'G' has a cut edge, then λ(G) is 1. (edge connectivity of G.)
Example 3
Take a look at the following graph. By removing two minimum edges, the connected graph
becomes disconnected. Hence, its edge connectivity (λ(G)) is 2.
Here are the four ways to disconnect the graph by removing two edges −
28
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Vertex Connectivity
Let 'G' be a connected graph. The minimum number of vertices whose removal makes 'G'
either disconnected or reduces 'G' in to a trivial graph is called its vertex connectivity.
Notation − K(G)
Example 4
In the above graph, removing the vertices 'e' and 'i' makes the graph disconnected.
Solution:
From the graph,
δ(G) = 3
K(G) ≤ λ(G) ≤ δ(G) = 3 (1)
K(G) ≥ 2 (2)
Deleting the edges {d, e} and {b, h}, we can disconnect G.
Therefore,
λ(G) = 2
29
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
In a directed graph is said to be strongly connected, when there is a path between each
pair of vertices in one component.
To solve this algorithm, firstly, DFS algorithm is used to get the finish time of each vertex,
now find the finish time of the transposed graph, then the vertices are sorted in
descending order by topological sort.
Algorithm
Begin
mark start as visited
for all vertices v connected withstart,do
if v isnotvisited,then
traverse(graph, v, visited)
done
End
GetStrongConComponents(graph)
Input: The given graph.
Output − All strongly connected components.
Begin
initially all nodes are unvisited
for all vertex i in the graph, do
if i is not visited, then
topoSort(i, vis, stack)
done
We can say that a graph G is a bi-connected graph if it is connected, and there are no articulation points or cut vertex are
present in the graph.
To solve this problem, we will use the DFS traversal. Using DFS, we will try to find if there is any articulation point is
present or not. We also check whether all vertices are visited by the DFS or not, if not we can say that the graph is not
connected.
Articulation Points
The vertices whose removal would disconnect the graph are known as articulation points.
31
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
B A
C D
G E
Here the removal of ‘C’ vertex will disconnect G from the graph.
Similarly removal of ‘D’ vertex will disconnect E & F from the graph. Therefore ‘C’ & ‘D’ are
articulation points.
B A
C D
G E
Removal of vertex ‘C’
B A
C D
G E
Removal of Vertex ‘D’
The graph is not biconnected, if it has articulation points.
32
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Depth first search provides a linear time algorithm to find all articulation points in a
connected graph.
Step 1: Perform depth first search starting at any vertex.
Step 2: Number the vertex as they are visited, as Num (V).
Step 3: Compute the lowest numbered vertex for every vertex V in the Depth
First spanning tree, which we call as low (W),that is reachable from v by
Taking zero or more tree edges and then possible one back edge. By
Definition, Low (V) is the Minimum of
(i) Num(V)
(ii) The lowest Num (w) among all back edges (V,W)
(iii) The lowest low (W) among aii tree edge (V,W)
Step 4: (i) they root is an articulation if and only if it has more than two child.
(ii) Any vertex V other than root is an articulation point if and only if V has same
child W such that low (W) >Num (V), the time taken to compute this algorithm
an a graph is O (|E| + |V|)
D G
A spanning tree of a graph is just a sub graph that contains all the vertices and
is a tree.
Informally spanning tree is defined as: given n points, connect them in the
cheapest possible way so that there will be a path between every pair of nodes.
The Minimum Spanning Tree for a given graph is the spanning Tree of minimum
cost for that graph.
33
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
The weight of a tree is defined as the sum of the weights on all its edges.
The number of spanning trees grows exponentially with the graph size.
There are two algorithms or methods to construct minimum spanning trees: Prim’s and
Kruskal’s algorithm.
[Link] Prim’s algorithm. Find the minimum spaning tree for the following graph
using any node of the [Link]/MAY2016
Prim’s Algorithm
34
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
2 7 V Known Dv pv
3 4 5
V1 0 0 0
8 4
5 V2 0 ∞ 0
6
6 7 V3 0 ∞ 0
1
V4 0 ∞ 0
V5 0 ∞ 0
V6 0 ∞ 0
V7 0 ∞ 0
Vertex V1 is marked as visited and then distance of its adjacent vertices are updated as
follows
V1 1 0 0
3 4 5
V2 0 2 V1
V3 0 4 V1
6 7 V4 0 1 V1
V5 0 ∞ 0
T[V2].dist = min[T[V2].dist ,CV1,V2] V6 0 ∞ 0
= min [∞, 2] = 2 V7 0 ∞ 0
T[V4].dist = min[T[V4].dist ,CV1,V4]
= min [∞, 1] = 1
35
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
= min [∞, 4] = 4
Vertex V4 is marked as visited and then the distance of its adjacent vertices are updated.
V Known Dv pv
3 4 5 V1 1 0 0
V2 0 2 V1
6 7 V3 0 2 V4
T[V2].dist = min[T[V2].dist ,CV4,V2] V4 1 1 V1
= min [2, 3] = 2 V5 0 2 V4
T[V3].dist = min[T[V3].dist , CV4,V3] V6 0 8 V4
= min [4, 2] = 2 V7 0 4 V4
T[V5].dist = min[T[V5].dist ,CV4,V5]
= min [∞, 2] = 7
= min [∞, 8] = 8
= min [∞, 4] = 4
Vertex V2 is marked as visited and then the distance of its adjacent vertices are updated.
The tables after V2 is declared know
V Known Dv pv
1 2
V1 1 0 0
V2 1 2 V1
3 4 5
V3 0 2 V4
V4 1 1 V1
6 7 V5 0 7 V4
V6 0 8 V4
T[V4].dist = min[T[V4].dist ,CV2,V4] V7 0 4 V4
36
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
= min [1, 3] = 1
Vertex V3 is marked as visited and then the distance of its adjacent vertices are updated
V1 1 0 0
3 4 5
V2 1 2 V1
V3 1 2 V4
6 7 V4 1 1 V1
T[V6].dist = min[T[V6].dist ,CV3,V6] V5 0 7 V4
= min [8, 5] = 5 V6 0 5 V3
V7 0 4 V4
Vertex V7 is marked as visited and then the distance of its adjacent vertices are updated
1 2 The tables after V7is declared known
V Known Dv pv
3 4 5 V1 1 0 0
V2 1 2 V1
V3 1 2 V4
6 7
V4 1 1 V1
T[V6].dist = min[T[V6].dist ,CV7,V6] V5 0 6 V7
= min [5, 1] = 1 V6 0 1 V7
T[V5].dist = min[T[V5].dist ,CV7,V5] V7 1 4 V4
= min [7, 6] = 6
Vertex V6 is marked as visited and then the distance of its adjacent vertices are updated
37
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
V Known Dv pv
1 2
V1 1 0 0
V2 1 2 V1
3 4 5 V3 1 2 V4
V4 1 1 V1
6 7 V5 0 6 V7
Vertex V5 is marked as visited and then V6 1 1 V7 the
distance of its adjacent vertices are
updated V7 1 4 V4
V Known Dv pv
1 2
V1 1 0 0
V2 1 2 V1
3 4 5 V3 1 2 V4
V4 1 1 V1
6 7 V5 1 6 V7
V6 1 1 V7
The edges in the spanning tree can be V7 1 4 V4 read
from the table as follows:
(V1, V2) = 2
(V3, V4) = 2
(V1, V4) = 1
(V7, V5) = 6
Vertex V, W:
\* table initialization*/
For (i=0; i<num vertex; i++)
{
T[i].known = false;
T[i].Dist = infinity;
T[i].path = Not A vertex;
}
T [start]. Dist = 0;
For (;;)
{
V = smallest unknown distance vertex;
If (V==not a vertex)
Break;
T [V}].known = true;
For each w adjacent to V
If (! T [W].known)
{
T [W].dist = min [T [W].dist, C v w]
T [W].path = V;
}}}
39
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
10. Consider the following graph, Construct MST using Kruskals algorithm.(Apr/May-
2016)
In kruskal’s algorithm, we select edges inorder of smallest weight and accept an
edge if it doest not form a cycle.
The algorithm uses two data structure namely find and union.
Find (U) returns the root of the tree that contains the vertexU.
Union (S, U, V) merge the two trees by making the root pointer of one node point to
the root node of the other tree.
1 2
3 4 5
6 7
Step 1:
1 2
3 4 5
6 7
Step 2:
1 2
3 4 5
6 7
40
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Step 3:
1 2
3 4 5
6 7
Step 4:
1 2
3 4 5
6 7
Step 5:
1 2
3 4 5
6 7
(V1,V4) 1 ACCEPTED
(V6,V7) 1 ACCEPTED
41
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
(V1,V2) 2 ACCEPTED
(V3,V4) 2 ACCEPTED
(V2,V4) 3 REJECTED
(V1,V3) 4 REJECTED
(V4,V7) 4 ACCEPTED
(V3,V6) 5 REJECTED
(V5,V7) 6 ACCEPTED
Disjoint Set;
Heap H;
Vertex U, V;
Edge E;
Initialize (s);
If (Uset ! = Vset)
}}}
The worst –case running time of this algorithm is O (|E| log |E|), which is dominated
by heap operation.
Notice that since |E|= O|V| 2), this running time is actually O|E| log |V|).
Example 2:
43
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Prim's algorithm it start with a node. Kruskal’s algorithm it begins with an edge
Prim's algorithm it move from one node to Kruskal's Algorithm select the next edge in
another. increasing order
The single source shortest path algorithm finds the minimum cost from single
source vertex to all other vertices.
Common algorithms: Dijkstra's algorithm, Bellman-Ford algorithm
Dijkstra's algorithm solves the single-source shortest path
problem.
Bellman–Ford algorithm solves the single-source problem if edge
weights may be negative.
is used to solve this problem which follows the greedy technique.
44
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
12. Using Dijiktra’s algorithm, find the shortest path from the source to all nodes of
the graph ‘G’ given in the following figure. (APR/MAY 2023)
All the edges are assigned a weighted of ‘1’ for each vertex.
Three piece of information
1) Known Specifies whether the vertex processed or not.
2) dv Specifies the distance from the source
3) pv Actual path
Algorithm:
1) Assign the source node (s) and enqueue s.
2) Dequeue S and assign the value (known) then find its adjacency vertices.
3) If distance of adjacent vertices is equal to infinity then change the distance
T[W].dist=T[V].distance+1 if dw = infinity
T[W].path=V
VW
4) Repeat from step – 2 , until the queue becomes empty.
unweighted directed graph
STEP 1: INITIAL STATE
DEQUEUE
1 2 V Known Dv pv
V1 0 ∞ 0
V2 0 ∞ 0
4 5 V3 0 0 0
3
V4 0 ∞ 0
V5 0 ∞ 0
6 7 V6 0 ∞ 0
V7 0 ∞ 0
ENQUEUE V3
We choose‘s’ to be source vertex ‘V3’
The shortest path form’s’ to ‘V3’ is a path of length 0.
STEP 2: DEQUEUED V3
45
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
1 2 DEQUEUED V3
V Known Dv pv
V1 0 1 V3
4 5 V2 0 ∞ 0
3
V3 1 0 0
V4 0 ∞ 0
6 7 V5 0 ∞ 0
V6 0 1 V3
V7 0 ∞ 0
ENQUEUE V1,V6
Dequeue V3 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V3]= V1, V6 enqueue it.
T[V6].dist=T[V3].distance+1
= 0+1=1
T[V6].path=V3
STEP 3: DEQUEUED V1
1 2 DEQUEUED V1
V Known Dv pv
V1 1 1 V3
V2 0 2 V1
4 5 V3 1 0 0
3
4 0 2 V1
V5 0 ∞ 0
V6 0 1 V3
6 7 V7 0 ∞ 0
ENQUEUE V6,V2,V4
Dequeue V1 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V1]= V2, V4 enqueue it.
If distance of adjacent vertices is equal to infinity then change the distance
T[V2].dist=T[V3].distance+1
= 1+1=2
T[V2].path=V1
T[V4].dist=T[V3].distance+1
= 1+1=2
46
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
T[V4].path=V1
STEP 4: DEQUEUED V6
DEQUEUED V6
1 2
V Known Dv pv
V1 1 1 V3
V2 0 2 V1
4 V3 1 0 0
3 5 V4 0 2 V1
V5 0 ∞ 0
V6 1 1 V3
6 7 V7 0 ∞ 0
ENQUEUE V2,V4
Dequeue V6 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V3]= no adjacency enqueue it.
STEP 5: DEQUEUED V2
DEQUEUED V2
1 2 V Known Dv pv
V1 1 1 V3
V2 1 2 V1
V3 1 0 0
4 5 V4 0 2 V1
3
V5 0 3 V2
V6 1 1 V3
V7 0 ∞ 0
6 7 ENQUEUE V4,V5
Dequeue V2 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V2]= V4, V5
T[V5].dist=T[V3].distance+1
= 2+1=3
T[V5].path=V2
STEP 6: DEQUEUED V4
1 2 DEQUEUED V4
V Known Dv pv
V1 1 1 V3
4 V2 1 2 V1
3 5
V3 1 0 0
6 7 47
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
V4 1 2 V1
V5 0 3 V2
V6 1 1 V3
V7 0 3 V4
ENQUEUE V5,V7
Dequeue V4 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V4]= V3, V5,V6,V7
T[V5].dist=T[V4].distance+1
= 2+1=3
T[V5].path=V4
T[V6].dist=T[V4].distance+1
= 2+1=3
T[V6].path=V4
T[V7].dist=T[V4].distance+1
= 2+1=3
T[V7].path=V4
STEP 7: DEQUEUED V5
DEQUEUED V5
V Known Dv pv
1 2
V1 1 1 V3
V2 1 2 V1
V3 1 0 0
4 V4 1 2 V1
3 5 V5 1 3 V2
V6 1 1 V3
V7 0 3 V4
6 7 ENQUEUE V7
Dequeue V5 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V5]= V7
T[V7].dist=T[V5].distance+1
= 3+1=4
T[V7].path=V5
STEP 8: DEQUEUED V7
1 2
DE 4 5 QUEUED V7
3
V Known Dv pv
V1 1 1 V3
6 7 V2 1 2 V1
V3 1 0 0
V4 1 2 V1
V5 1 3 V2
V6 1 1 V3
V7 1 3 V4
ENQUEUE empty
Dequeue V7 and assign the value (known=1) then find its adjacency vertices.
adjacency vertices [V7]=V6
If distance of adjacent vertices is equal to infinity then change the distance
T[V6].dist=T[V7].distance+1
= 3+1=4
T[V1].path=V7
Data changes during the unweighted shortest path algorithm.
The shortest distance from the source vertex V3 to all other vertex is listed below:
V3->V1 is 1
V3->V2 is 2
V3->V4 is 2
V3->V5 is 3
V3->V6 is 1
V3->V7 is 3
ROUTINE FOR ALGORITHM
T[V].known = true;
For each W adjacent to V
If ( (T[W}.dist = = infinity)
{
T[W].dist = T[V].dist + 1;
T[W].path = V;
Enqueue (W,Q);
}}
Dispose queue (Q);
}
ANALYSIS
The input is a weighted graph: associated with each edge (vi, vj) is a cost ci,j to
traverse the arc. The cost of a path v1v2 ... vn is referred to as the weighted path length.
6 7 50
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
The following table represents the initial configuration, assuming that the start node, S is
V1.
INITIAL STATE
2 V Known Dv pv
1 2
10 V1 0 0 0
4 1 3
V2 0 ∞ 0
2 2
4 5 V3 0 ∞ 0
3
8
V4 0 ∞ 0
5 6
6 7 V5 0 ∞ 0
1
V6 0 ∞ 0
V7 0 ∞ 0
Step 2
Select the minimum distance vertex from unknown vertex the first vertex selected is V1,
with path length 0.
2 V2 0 2 V1
2
4 5
3 V3 0 ∞ 0
8
5 6 V4 0 1 V1
6 7 V5 0 ∞ 0
1
V6 0 ∞ 0
V7 0 ∞ 0
51
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Dequeue V1 and this vertex is marked ‘1’( known)then find its adjacency [Link]
vertices [V1]=V2,V4
V 1V2,V4
=Min[∞,0+2] =2
T[V2].path=V1
=Min[∞,0+1] =1
T[V4].path=V1
Step 3:
2 V Known Dv pv
1 2
10 V1 1 0 0
4 1 3
V2 0 2 V1
2 2
4 5 V3 0 3 V4
3
8
V4 1 1 V1
5 6
6 7 V5 0 3 V4
1
V6 0 9 V4
V7 0 ∞ 0
Dequeue V4 and this vertex is marked ‘1’( known)then find its adjacency vertices.
V 4V3,V5,V6
=Min[∞,1+2] = Min[∞,3] =3
TV3].path=V4
52
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
=Min[∞,1+2] = Min[∞,3] =3
T[V5].path=V4
=Min[∞,1+8] = Min[∞,9] =9
T[V6].path=V4
V6 0 9 V4
V7 0 ∞ 0
Dequeue V2 and this vertex is marked ‘1’( known) then find its adjacency vertices.
V 2V4,V5
=Min[1,2+3] = Min[1,5]
=1
=Min[3,2+10] = Min[3,12]
=3
53
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
2
V2 1 2 V1
2
4 5
3 V3 1 3 V4
8
5 6 V4 1 1 V1
6 7 V5 0 3 V4
1
V6 0 8 V3
V7 0 ∞ 0
Dequeue V3 and this vertex is marked ‘1’( known) then find its adjacency vertices.
V 3V1,V6
=Min[0,3+4] = Min[0,7] =0
=Min[9,3+5] = Min[9,8] =8
T[V6].path=V3
Step 6:
2 2 V2 1 2 V1
4 5
3 V3 1 3 V4
8
5 6
6 7 54
1 ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
PREPARED BY: [Link]
CS3401 ALGORITHMS UNIT 2 MEC
V4 1 1 V1
V5 1 3 V4
V6 0 8 V3
V7 0 9 V5
Dequeue V5 and this vertex is marked ‘1’( known) then find its adjacency vertices.
V 5V7
T[V7].dist =Min[T[V7].dist, T[V5].dist+CV5V7]
=Min[∞,3+6] = Min[∞,9]
=9
T[V7].path=V5
Step 7: Next select V6 is minimum from unknown
2
1 2
1
4 1 3
0
2 2
4 5
3
8 After V6 is declared known
5 6 V Known Dv pv
6 7
1 V1 1 0 0
V2 1 2 V1
V3 1 3 V4
V4 1 1 V1
V5 1 3 V4
V6 1 6 V3
V7 0 9 V5
Dequeue V6 and this vertex is marked ‘1’( known) then find its adjacency vertices.
55
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
2 V Known Dv pv
1 2
10 V1 1 0 0
4 1 3
V2 1 2 V1
2 2
4 5 V3 1 3 V4
3
8
V4 1 1 V1
5 6
6 7 V5 1 3 V4
1
V6 1 6 V7
V7 1 9 V5
V 7V6
=Min[9,3+6]
=9
The shortest distance from the source vertex V1 to all other vertex is listed below:
If (V==not a vertex)
Break;
T [V}].known = true;
For each w adjacent to V
If (! T [W].known)
{
T [W].dist = min [T [W].dist, T [V].dist + C v w]
T [W].path = V;
}}}
Warshall’s algorithm constructs the transitive closure of given diagraph with n vertices
through a series of n × n boolean matrices.
The computations in Warshall’s algorithm are given by following sequence,
R(0), . . . , R(k−1), R(k), . . . R(n).
Edge from b to d
adjacency matrix.
Transitive closure : Transitive closure is basically a boolean matrix ( matrix with 0 and 1
values ) in which the existence of directed paths of arbitrary lengths between vertices is
mentioned.
57
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
transitive closure.
The transitive closure can be generated with Depth First Search (DFS) or with Breadh
First Search (BFS).
This traversing can be done on any vertex.
While computing transitive closure we have to start with some vertex and have to find all
the edges which are reachable to every other vertex . the reachable edges for all the
vertices has to obtained
Procedure to be followed :
Start with computation of R(0). In R(0) any path with intermediate vertices is not
allowed . the means only direct edges towards the vertices are considered. in other
words the path length of one edge is allowed in R (0). Thus V R(0) is adjacency matrix
for the diagraph.
Construct R(1) in which first vertex is used as intermediate vertex and a path length
of two edges is allowed. Note that R(1) is build using R(0) which is already computed.
Go on building R(k) by adding one intermediate vertex each time and with more
path length . each R(k) has to be built from R(k-1).
The last matrix in this series is R(n), in thisR(n) all yhe n verticesare used as
intermediate vertices . and the R(n) which is obtained is nothing but the transitive
closure of given digraph.
Let us understand this algorithm with some example
Obtain the transitive closure for the following digraph using Warshall’s algorithm.
Let us first obtain adjacency matrix for given digraph .it is denoted by R(0) .
58
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Algorithm :
59
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
for (k ← 1 to n ) do
{
for(i ← 1 to n ) do
{
for (j ← 1 to n ) do
{
R(k) [ i, j] ← R(k-1) [ i, j] OR R(k-1) [ i, k]
AND R(k-1) [ k, j]
}}}
return R(n)
V A B C d Analysis:
Floyd’s algorithm is used for finding the shortest path between every pair of vertices of a
graph. It is all pairs shortest path algorithm.
The algorithm works for both directed and undirected graphs. This algorithm is invented
by R. Floyd hence is the name.
Weighted graph: the weighted graph is a graph in which weights or distances are given
along the edges. The weighted graph can be represented by weighted matrix as follows,
Here
w[i][j] = 0 if i=j
and j .
60
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Formulation:
Let ,Dk [i,j] denotes the weight of shortest path from vi to vj using {v1 , v2, v3…vk} as
intermediate vertices.
1. A shortest path from vi to vjwith intermediate vertices from {v1 , v2, v3…vk} that
does not use vk. in this case
Dk [i,j] = D(k-1)[i,j]
2. A shortest path from vi to vjrestricted to using intermediate vertices {v 1 , v2, v3…vk}
which uses vk. in this case-
Dk [i,j] = D(k-1) [i,k] + D(k-1) [k,j]
The graphical representation of these two case is shortest path using vertices from
1. The Floyd’s algorithm is for computing shortest path between every pair of vertices
of graph.
2. The graph may contain negative edges but it should not contain negative cycles.
3. The Floyds algorithm requires a weighted graph.
4. Floyd’s algorithm computes the distance matrix of a weighted graph with n vertices
through a series of n × n matrices :
D(0), . . . , D(k−1), D(k), . . . , D(n).
5. In each matrix D(k) the shortest distance “dij” has to be computed between vertex vi
and vj
6. In particular the series starts withD(0) with no intermediate vertex. That means D(0)
is a matrix in which vi and [Link] row and jth column contains the weights given by
direct edges . in D(1) matrix – the shortest distance going through one intermediate
vertex ( starting vertex as intermediate) with maximum path length of 2 edges is
given continuing in this fashion we will compute D (n), contains the lengths of
61
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
shortest paths among all paths that can use all n vertices as intermediate. Thus we
get all pair shortest paths from matrix D(n)
Obtain the all pair – shortest path using Floyd’s algorithm for the
Algorithm:
fork←1 to n do
62
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
fori ←1 to ndo
{
forj ←1 to n do
{
D[i, j ]←min{D[i, j ], D[i, k]+ D[k, j]}
}
}
}
returnD
Analysis :
In the above given algorithm the basic operation is –
C(n) = ∑𝑛𝑘=1 n2
C(n) = n3
If a graph G = (V, E) contains a negative-weight cycle, then some shortest paths may
not exist.
The relaxation procedure takes two nodes as arguments and an edge connecting
these nodes. If the distance from the source to the first node ( ) plus the edge length is
less than distance to the second node, than the first node is denoted as the predecessor of
63
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
the second node and the distance to the second node is recalculated (
). Otherwise no changes are applied.
The path from the source node to any other node can be at maximum
edges long, provided there is no cycle of negative length. Hence if we perform for all nodes
the relaxation operation , than the algorithm will find all shortest paths. We will
verify the output by running the relaxation once more – if some edge will be relaxed, than
the algorithm contains a cycle of negative length and the output is invalid. Otherwise the
output is valid and the algorithm can return shortest path tree.
The bellman-Ford algorithm solves the single source shortest path problems even in
the cases in which edge weights are negative. This algorithm returns a Boolean value
indicating whether or not there is a negative weight cycle that is reachable from the source.
If there is such a cycle, the algorithm indicates that no solution exists and it there is no such
cycle, it produces the shortest path and their weights.
Algorithm:
Input Format: Graph is directed and weighted. First two integers must be number of
vertices and edges which must be followed by pairs of vertices which has an edge between
them.
Algorithm:
int distance[vertices];
intiter,jter,from,to;
for(iter=0;iter<vertices;iter++)
distance[iter] = INF;
distance[source] = 0;
/* We have to repeatedly update the distance |V|-1 times where |V| represents
number of vertices */
for(iter=0;iter<vertices-1;iter++)
for(from=0;from<vertices;from++)
for(jter=0;jter<size[from];jter++)
to = graph[from][jter];
65
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
}
}
}
}
for(iter=0;iter<vertices;iter++)
{
printf("The shortest distance to %d is %d\n",iter,distance[iter]);
}
}
66
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
ASYMPTOTIC COMPLEXITY
The Bellman-Ford algorithm runs in time O(VE), since the initialization takes Θ(V)
time, each ofthe |V| - 1 passes over the edges takes O(E) time and calculating the distance
takes O(E) times.
The maximum flow problem, in which the goal is to maximize the total amount of flow
out of the source terminals and into the sink terminals
The minimum-cost flow problem, in which the edges have costs as well as capacities
and the goal is to achieve a given amount of flow (or a maximum flow) that has the
minimum possible cost
The multi-commodity flow problem, in which one must construct multiple flows for
different commodities whose total flow amounts together respect the capacities
Nowhere-zero flow, a type of flow studied in combinatory in which the flow amounts
are restricted to a finite set of nonzero values
67
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
The max-flow min-cut theorem equates the value of a maximum flow to the value of
a minimum cut, a partition of the vertices of the flow network that minimizes the total
capacity of edges crossing from one side of the partition to the other. Approximate max-
flow min-cut theorems provide an extension of this result to multi-commodity flow
problems. The Gomory–Hu tree of an undirected flow network provides a concise
representation of all minimum cuts between different pairs of terminal vertices.
Algorithms for constructing flows include
Flow Network
In graph theory, a flow network is defined as directed graph G= (V,E) constrained with a
function c, which bounds each edge e with a non-negative integer value which is known
as capacity of the edge e with two additional vertices defined as source S and sink T.
As shown in the flow network given below, a source vertex has all outgoing edges and no
incoming edges, more formally we can say Indegree[source]=0 and sink vertex has all
incoming edges and no outgoing edge more formally outdegree[sink]=0
Also, any flow network should satisfy all the underlying conditions --
68
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
For all the vertices (except the source and the sink vertex), input flow must be equal
to output flow.
For any given edge Ei) in the flow network, 0≤flow(Ei)≤Capacity)≤ (Ei) hold, we
cannot send more flow through an edge than its capacity.
Total outflow from the source vertex must be equal to total inflow to the sink vertex.
17. Explain in detail about algorithm for maximum flow problem Apr/May 2024
Given a flow network G with source s and sink t, the maximum flow problem is
an optimization problem to find a flow of maximum value from s to t. Flow
network G=(V, E), is essentially just a directed graph where each edge has a
nonnegative flow capacity.
Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow
in a network or a graph.
A term, flow network, is used to describe a network of vertices and edges with a source (S)
and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff
through it. S can only send and T can only receive stuff.
We can visualize the understanding of the algorithm using a flow of liquid inside a network
of pipes of different capacities. Each pipe has a certain capacity of liquid it can transfer at
an instance. For this algorithm, we are going to find how much liquid can be flowed from
the source to the sink at an instance using the network.
Terminologies Used
Augmenting Path
It is the path available in a flow network.
Residual Graph
It represents the flow network that has additional possible flow.
69
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Residual Capacity
It is the capacity of the edge after subtracting the flow from the maximum capacity.
1. Select any arbitrary path from S to T. In this step, we have selected path S-A-B-T.
2. Find a path
The minimum capacity among the three edges is 2 (B-T). Based on this, update
the flow/capacity for each [Link] the capacities
70
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
3. Select another path S-D-C-T. The minimum capacity among these edges is 3 (S-D).
4. Findnextpath
8. Updating the capacities. Thecapacity for forward and reverse paths is considered
separately.
71
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
9. Adding all the flows = 2 + 3 + 1 = 6, which is the maximum possible flow on the flow
network.
Note that if the capacity for any edge is full, then that path cannot be used.
Algorithm
FORD-FULKERSON METHOD (G, s, t)
[Link] flow f to 0
2. while there exists an augmenting path p
3. do argument flow f along p
4. Return f
FORD-FULKERSON (G, s, t)
1. for each edge (u, v) ∈ E [G]
2. do f [u, v] ← 0
3. f [u, v] ← 0
4. while there exists a path p from s to t in the residual network Gf.
5. docf (p)←min?{ Cf (u,v):(u,v)is on p}
6. for each edge (u, v) in p
7. do f [u, v] ← f [u, v] + cf (p)
8. f [u, v] ←-f[u,v]
Example 2: let us first find the augmenting path.
Step 1:
7 5
3
8 3
t
s 2
2 4 6
2 4
72
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Step2: here along the augmenting path the residual capacity is c(3,t) =5 . hence we
can draw residual network.
Step3: now we will again mark augmenting path for maximum flow.
Here cf=c(2,3) =3
This is the residual graph, we will now find the augmenting path giving maximum
flow from source to sink. Here the only remaining path is s-1-4-t.
The cf=(s,1)=2
Step 4:
Step 5: Now there is no path from s to t in following graph, hence we will exit the
while loop.
Now once again consider the original graph which we have taken for discussing above
example.
73
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
When the graph has maximum flow then it gives minimum cut which is as shown below.
Analysis : The algorithm for Ford-Fulkerson has a while loop which executes for O (E).
Hence running time of Ford-Fulkerson algorithm is O(EF*) where F* is the maximum flow
found b algorithm.
18. Explain the Maximum Matching in Bipartite Graph algorithm with supporting example
Aprl/May 2024
Bipartite Graph:
The graph G = (V, E) in which the vertex set V is divided into two disjoint sets X and Y in
such a way that every edge e € E has one end point in X and other end point in Y.
For example
74
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Matching:
A matching M is a subset of edges such that each node in V appears in at most one
edge in M. In other words matching in a graph is a subset of edges that no two edges
share a vertex.
Two-colorable Graph:
A graph can be colored with only two colors (i.e. two colorable graph) such that no
edge connects the same color. The bi-partite graph is 2-colorable.
Free vertex:
Alternating path:
The alternating path P is a path in graph G, such that for every pair of subsequent
edges one of them is matching pair M and other is not.
Augmenting path:
The augmenting path P is a path in graph G, such that it is an alternating path with
special property that its start and end vertices are free or unmatched.
w <Front(Q)
75
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
if w ε V then
w <Front(Q)
if w ε V then
augment
v< w
u< label of v
V< label of u
reinitialize Q with
remove all
else// u is matched
Enqueue(Q, u)
Application of Algorithm
Step 1:
Step 2:
77
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Step 5:
Solution:
Step 1: Step 2:
Step 3: Step 4:
78
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Step 5: Step 6:
Step 7:
19. Write the pseudocode for BFS and DFS traversals on the graph given below and
compare the time and space complexity of the two traversals. Apr/May 2024
Fig 12.a(i)
Breadth-First Search (BFS) Pseudocode
BFS explores the graph level by level using a queue (FIFO structure).
BFS(Graph, start_node):
Enqueue start_node to Q
Enqueue neighbor to Q
DFS explores as deeply as possible before backtracking, using either recursion (implicit stack)
or an explicit stack (LIFO structure).
Recursive DFS
DFS(Graph, start_node):
Push start_node to S
for each neighbor in adjacency_list[node] (in reverse order for proper order of traversal):
80
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Push neighbor to S
BFS O(V + E) O(V) (for queue & visited set) Queue (FIFO) Key
Points:
DFS (Recursive) O(V + E) O(V) (call stack in worst case) Stack (LIFO via recursion)
BFS
DFS (Iterative) O(V + E) O(V) (for stack & visited set) Stack (LIFO) is ideal for
finding the
shortest
path in an unweighted graph.
DFS is useful for exploring all paths and solving connectivity problems.
DFS can have worse space complexity in the worst case (O(V) due to recursion depth).
20. Find the minimum spanning tree for the following graph using Kruskals algorithm Apr/May 2024
Kruskal’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of
a graph. It works by sorting edges by weight and adding them one by one while avoiding cycles.
Edge Weight
(a, b) 4
(a, h) 8
(b, h) 11
81
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Edge Weight
(b, c) 8
(h, i) 7
(h, g) 1
(i, g) 6
(c, d) 7
(g, f) 2
(d, f) 14
(d, e) 9
(f, e) 10
1. (h, g) - 1
2. (g, f) - 2
3. (a, b) - 4
4. (i, g) - 6
5. (c, d) - 7
6. (h, i) - 7
7. (b, c) - 8
8. (a, h) - 8
9. (d, e) - 9
10. (f, e) - 10
11. (b, h) - 11
12. (d, f) - 14
We use the Union-Find data structure to add edges while ensuring there are no cycles.
1. Add (h, g) - 1 ✅
2. Add (g, f) - 2 ✅
82
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
3. Add (a, b) - 4 ✅
4. Add (i, g) - 6 ✅
5. Add (c, d) - 7 ✅
6. Add (h, i) - 7 ✅
7. Add (b, c) - 8 ✅
8. Add (d, e) - 9 ✅
Now we have V-1 = 8 edges (since we have 9 vertices, the MST should have 8 edges).
Edge Weight
(h, g) 1
(g, f) 2
(a, b) 4
(i, g) 6
(c, d) 7
(h, i) 7
(b, c) 8
(d, e) 9
1+2+4+6+7+7+8+9=441 + 2 + 4 + 6 + 7 + 7 + 8 + 9 = 441+2+4+6+7+7+8+9=44
83
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
21. Given a graph and a source vertex in the graph, find the shortest paths from the source
vertex 0 to all vertices in the given graph Apr/May 2024
solution
[Link] kruskals algorithm and to find the minimum spanning tree for the following
[Link]/Dec 2024
Edges included:
84
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
(F,E) → 1
(A, F) → 2
(A, B) → 3
(D, I) → 4
(E, H) → 5
(E, G) → 6
(C, D) → 8
(I, J) → 9
(I, E) → 10
1 + 2 + 3+ 4+ 5 + 6 + 8 + 9 + 10 = 48
[Link] the given graph, the vertex represents the city and edge represents the cost between
the two vertices. Apply Dijikstra’s shortest algorithm and find the optimal cost to reach the
destination. Also determine the worst case time complexity of the algorithm. Nov/Dec 2024
s 0 -
t ∞ -
x ∞ -
y ∞ -
z ∞ -
85
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
t: 0+10=100 + 10 = 100+10=10
y: 0+5=50 + 5 = 50+5=5
s 0 -
t 10 s
x ∞ -
y 5 s
z ∞ -
Mark s as visited.
From y (5):
s 0 -
t 7 y
x ∞ -
y 5 s
z 7 y
Mark y as visited.
86
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
From t (7):
x: 7+1=87 + 1 = 87+1=8
z: 7+9=167 + 9 = 167+9=16 (not better than 7)
s 0 -
t 7 y
x 8 t
y 5 s
z 7 y
Mark t as visited.
From z (7):
No updates.
s 0 -
t 7 y
x 8 t
y 5 s
z 7 y
Mark z as visited.
87
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
From x (8):
No new updates.
s 0 -
t 7 y
x 8 t
y 5 s
z 7 y
Mark x as visited.
t=7
x=8
y=5
z=7
Time Complexity
Dijkstra’s algorithm runs in O(V²) using an adjacency matrix, where V is the number of vertices.
Using a priority queue (binary heap), it runs in O((V + E) log V).
V = 5 (s, t, x, y, z)
E = 6 (number of edges)
88
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
24..Apply ford Fulkerson algorithm for the following graph and determine the maximum flow in the
graph.(Nov/Dec2024)
Below is one systematic way to find the maximum flow using the (Edmond–Karp) Ford–
Fulkerson method. The network (with source V1V_{1}V1 and sink V6V_{6}V6) has edges and
capacities:
We repeatedly look for a path from V1V_{1}V1 to V6V_{6}V6 in the residual network (i.e.,
along edges that still have available capacity > 0). Once found, we send flow equal to the
minimum residual capacity (the “bottleneck”) on that path, update the residual capacities, and
repeat until no augmenting path remains.
89
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Augmenting Path 1
Augmenting Path 2
Augmenting Path 3
90
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Now we try to find any further augmenting path from V1V_{1}V1 to V6V_{6}V6. In the
residual network:
Hence there is no way to push additional flow into V6V_{6}V6. The BFS fails to find a path to
the sink. No more augmenting paths remain.
We can also confirm this by noting a cut of capacity 18: for instance, take
S={V1,V2,V3,V4,V5},T={V6}. S = \{V_{1}, V_{2}, V_{3}, V_{4}, V_{5}\}, \quad T = \{V_{6}\}.S={V1,V2,V3,V4
,V5},T={V6}.
All edges crossing from SSS to TTT are exactly V4→V6V_{4}\to V_{6}V4→V6 (capacity 14)
and V5→V6V_{5}\to V_{6}V5→V6 (capacity 4), summing to 18. Since no flow can exceed
any cut’s capacity, 18 is indeed the maximum.
Final Answer
The maximum flow in the given network is 18.
91
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
IMPORTANT QUESTION
PART-A
PART-B
1. Write algorithm for weighted and unweightedshorest paths. Explain the above
algorithms with suitable examples. (May/June 2006)
92
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
2. Explain briefly about the Dijkstra’s algorithm. obtain the single –source shortest
path for the following graph. (Nov/Dec2005) (Nov/Dec2006) (May/June 2006)
(Nov/Dec2007) (Nov/Dec2010) (Nov/Dec2010)
Find the shortest path from ‘a’ to ‘d’ using Dijkstra’s algorithm in the graph . (NOV\DEC
09) (APR/MAY2010)
5. Consider the following 'graph. Determine the 'shortest distance to all other nodes
using Dijikstra's algorithm. Write Procedure. (10+3)
93
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
[Link] the Dijkstra’s algorithm for finding the shortest path following graph
12. Illustrate the working of Warshall’s algorithm
[Link] the minimum spanning tree for the following graph. (8)
1 6
A B C
3 5 1 4 2
1 4
D E F
3 4
1 8 3
7 1
4 5
2
5 4
6
16. Assume the following keys form the Binary Search tree {50, 30, 60, 40, 35, 80, 90}.
Analyze the time complexity involved in searching the keys 90 and then 80, when the
given BST is converted into AVL or Splay tree. Identify the suitable tree data structure
for representing this data and
justify your answer with valid reasons.
94
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
[Link] the all-pair shortest-path problem for the digraph with the following weight
matrix(16)
18. Apply kruskal’s algorithm to find a minimum spanning tree of the following graph.(16)
19. Apply the shortest-augmenting-path algorithm to find a maximum flow and a minimum cut in
the following networks.
PART B
1. Write the pseudocode for BFS and DFS traversals on the graph given below in fig. 12 (a) (i)
and compare the time and space complexity of the two traversals. Apr/May 2024 [Link] 78
[Link] 19
95
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
Fig 12.a(i)
2. Find the minimum spanning tree for the following graph using Kruskals algorithm Apr/May
2024 pg no 80 [Link] 20
3. Given a graph and a source vertex in the graph, find the shortest paths from the source
vertex 0 to all vertices in the given graph Apr/May 2024 [Link] 83 [Link] 21
PART C
(b) iRun the Bellman-Ford algorithm on the directed graph of figure below using vertex s as the source and show
the results after each pass of an algorithm. Refer Class work, [Link] 63, [Link] 15
96
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 2 MEC
ii With an example, Show that the cardinality of a maximum matching M in a bipartite graph G
equals the value of a maximum flow f in its corresponding flow network G'. [Link] 74 , [Link] 18
Nov/Dec 2024
PART-A
[Link] the graph traversal techniques.([Link] 10)
[Link] indegree and outdegree. .([Link] 20)
PART-B
[Link] kruskals algorithm and to find the minimum spanning tree for the following graph. ([Link] 22)
[Link] the given graph, the vertex represents the city and edge represents the cost between the two
vertices. Apply Dijikstra’s shortest algorithm and find the optimal cost to reach the destination.
Also determine the worst case time complexity of the algorithm. ([Link] 23)
PART-C
[Link] ford Fulkerson algorithm for the following graph and determine the maximum flow in the graph.
([Link] 24)
97
PREPARED BY: [Link] ASP/CSE [Link] AP/CSE , [Link] PRIYA ,AP/CSE
CS3401 ALGORITHMS UNIT 3 MEC
UNIT-III
ALGORITHM DESIGN TECHNIQUES 9
Divide and Conquer methodology: Finding maximum and minimum - Merge sort - Quick
sort Dynamic programming: Elements of dynamic programming — Matrix-chain
multiplication - Multi stage graph — Optimal Binary Search Trees. Greedy Technique:
Elements of the greedy strategy - Activity-selection problem –- Optimal Merge pattern —
Huffman Trees.
PART –A
1. Define the divide and conquer method. Nov/Dec 2024, Apr/May 2024
The algorithm which follows divide and conquer technique involves 3 steps:
Combine the solutions of these sub problems to get the solution of original problem.
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search
interval in half. The idea of binary search is to use the information that the array is sorted and
reduce the time complexity to O(Log n).
The time complexity of the binary search algorithm is O(log n). The best-case time complexity
would be O(1) when the central index would directly match the desired value.
The root has a path length of zero and the maximum path length in a tree is called the tree's
height. The sum of the path lengths of a tree's internal nodes is called the internal path and the
sum of the path lengths of a tree's external nodes is called the external path.
The sum over all internal (circular) nodes of the paths from the root of an extended binary tree to
each node. For example, in the tree above, the internal path length is 11 (Knuth 1997, pp. 399-
400).
Insertion Sort is preferred for fewer elements. It becomes fast when data is already sorted or
1
CS3401 ALGORITHMS UNIT 3 MEC
Efficiency: Considering average time complexity of both algorithms we can say that Merge Sort is
efficient in terms of time and Insertion Sort is efficient in terms of space.
Where T(n) is the time for DAndC on any input of size n and g(n) is the time to compute
the answer directly for small inputs.
The function f(n) is the time for dividing P and combining the solutions to subproblems.
8. Give the recurrence equation for the worst case behavior of merge sort.
9. Find the number of comparisons made by the sequential search in the worst case and
best case.
Worst case: The algorithm makes the largest number of key comparisons among all
possible
Best Case: The best case inputs will be lists of size n with their first element equal to
search key. Cbest(n)=1
A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-
used orders are numerical order and lexicographical order.
Efficient sorting is important for optimizing the use of other algorithms (such as search and
merge algorithms) that require sorted lists to work correctly;
More formally, the output must satisfy two conditions: The output is in non-decreasing
order (each element is no smaller than the previous element according to the desired total
order)
2
CS3401 ALGORITHMS UNIT 3 MEC
11. What do you meant by Divide and conquer strategy? May 2013
Divide & conquer technique is a top-down approach to solve a problem. The algorithm which
follows divide and conquer technique involves 3 steps:
And merge sort is a method which preserves this kind of ordering. Hence merge sort
is a stable sorting algorithm.
The efficiency of divide and conquer algorithms is given by recurrences of the form.
aT(n/b)+f(n) n>1
Where a and b are known constants. We assume that T(1) is known and n is a power of b ( n=b k).
In each step, the algorithm compares the input key value with the key value of the
middle element of the array.
If the keys match, then a matching element has been found so its index, or position,
3
CS3401 ALGORITHMS UNIT 3 MEC
is returned.
Otherwise, if the sought 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 input key is greater, on the sub-array to the right.
If the remaining array to be searched is reduced to zero, then the key cannot be
found in the array and a special "Not found" indication is returned.
17. What is the difference between quick sort and merge sort? May 2013
BASIS FOR
QUICK SORT MERGE SORT
COMPARISON
4
CS3401 ALGORITHMS UNIT 3 MEC
18. What is the difference between sequential and binary search? Apr 2013
This is the simple technique of searching an This is the efficient technique of searching an
element element
This technique does not require the list to be This technique require the list to be sorted.
sorted Then only this method is applicable
The worst case time complexity of this The worst case time complexity of this
technique is O(n) technique is O(log n)
Every element of the list may get compared Only the mid element of the list is compared
with the key element. with key element.
For the binary search the list should be sorted either in ascending or descending order
20. List out two drawbacks of binary search algorithm. Dec 2007
In binary search the elements have to be arranged either in ascending or descending order
Each time the mid elements has to be computed in order to partition the list in two sub lists
21. Give the control abstraction for divide and conquer. Dec 2012
divide_and_conquer( P )
return solution ( n );
divide_and_conquer( P2 ),
...
5
CS3401 ALGORITHMS UNIT 3 MEC
divide_and_conquer( Pk ) ) );
where f(n) is the time to divide n elements and to combine their solution.
A substitution method is one, in which we guess a bound and then use mathematical
induction to prove our guess correct.
Example 1.
Solution:
Step1: The given recurrence is quite similar with that of MERGESORT, you guess the
solution is
or
6
CS3401 ALGORITHMS UNIT 3 MEC
A feasible solution that maximizes the given objective function is called as optimal solution.
24. What do you mean by divide and conquer strategy? Jun 2013
The divide-and-conquer paradigm is often used to find an optimal solution of a problem. Its basic
idea is to decompose a given problem into two or more similar, but simpler, subproblems, to solve
them in turn, and to compose their solutions to solve the given problem.
Given n inputs form a subset such that it satisfies some given constraints then such a subset
is called feasible solution.
A feasible solution that maximizes the given objective function is called as optimal solution
27. Trace the operation of binary search algorithm for the input – 15, -6, 0, 7, 9, 23, 54, 82,
101.
Input :
7
CS3401 ALGORITHMS UNIT 3 MEC
0 1 2 3 4 5 6 7 8 9 10 11 12 13
Iteration 0:
Left = 0
Right = 13
= (0 + 13) / 2
Mid = 6
Midelement = 54
Search key = 9
Since 9 < 54, search the element 9 in the left of midelement 54.
Iteration 1:
Left = 0
Right = 5
= (0 + 5) / 2
Mid = 2
Midelement = 0
Search key = 9
Iteration 2:
Left = 3
Right = 4
= (3 + 4) / 2
Mid = 3
Midelement = 7
Search key = 9
8
CS3401 ALGORITHMS UNIT 3 MEC
[Link] a brute force algorithm for computing the value of a polynomial. (April/May
2015)
x := x0
p := 0.0
fori := n down to 0 do
power := 1
for j := power * x
p := p + a:= 1 to i do
returnp
Efficiency: (n2)
The worst case includes all arrays that do not contain a search key.
Cworst(1) = 1 -------- ( 2 )
9
CS3401 ALGORITHMS UNIT 3 MEC
Cworst(2k-1) = Cworst(2k-2)+ 1
….
log 2 n = log 2 2k
log 2 n = k. log 2 2
therefore k = log 2 n
Cworst(2k) = 1 + k
As Cworst(n) = log2n + 1
Cworst(n) = Cworst[(n/2)] + 1
10
CS3401 ALGORITHMS UNIT 3 MEC
L.H.S
Cworst(n) = log2n + 1
= log2(2i )+ 1
= log 2 2 + log 2i + 1
= 1+ log 2i + 1
= 2 + log 2i
Cworst(n) =2 + log 2i
R.H.S
= log 2i + 1
= log 2 2i + 1+ 1
= 2 + log 2i
Cworst(n/2) =2 + log 2i
L.H.S = R.H.S
Hence
Hence
Cworst(n) = Ө(log n )
30. Give the General plan divide and conquer method. Nov/Dec 2017
A divide and conquer algorithm works by recursively breaking down a problem into twoo
r more subproblems of the same (or related) type (divide), until these become simple enou
gh tobe solved directly (conquer).Divideandconquer algorithms work according to the follo
wing general plan:
A problem is divided into several subproblems of the same type, ideally of about equal size
The subproblems are solved (typically recursively, though sometimes a different algorith
m is employed, especially when subproblems become small enough).
If necessary, the solutions to the subproblems are combined to get a solution to the origi
nal
problem.
11
CS3401 ALGORITHMS UNIT 3 MEC
Example: Merge sort, Quick sort, Binary search, Multiplication of Large Integers
31. Devise an algorithm to make for 1655 using the Greedy strategy. The coins available
are {1000,500,100,50,20,10,5}.
Algorithm:
grab the largest remaining coin; // selection procedure if(adding the coin makes the change
exceed the amount owed )
else
The disadvantage of the insertion sort is that it does not perform as well as other, better
sorting algorithms.
With n-squared steps required for every n element to be sorted, the insertion sort does not
deal well with a huge list.
Therefore, the insertion sort is particularly useful only when sorting a list of few items.
34What are the differences between dynamic programming and divide and
12
CS3401 ALGORITHMS UNIT 3 MEC
Both techniques split their input into parts, find sub solutions to the parts, and synthesize
larger solutions from smaller ones.
Divide and conquer splits input at pre-specified deterministic points (eg., always in the middle)
Dynamic programming splits its every possible split rather than at pre-specified points. After
trying all split points, it determines which split point is optimal.
// representing a pattern
// unsuccessful
fori ← 0 to n – m do
j←0
j←j+1
if j = m return i
return -1
13
CS3401 ALGORITHMS UNIT 3 MEC
38. Write the difference between Greedy method and Dynamic programming. May 2011
Makes the locally optimal choice at each Solves subproblems recursively and combines their solutions to solve the main
step, hoping for a globally optimal problem optimally.
solution.
Relies on the fact that a local choice leads Uses optimal solutions to subproblems to build the overall optimal solution.
to a global optimum.
May not always lead to an optimal Always finds the optimal solution if the problem exhibits optimal substructure
solution. and overlapping subproblems.
39. Write algorithm to find shortest path between all pairs of nodes. May 2011
14
CS3401 ALGORITHMS UNIT 3 MEC
46. State ordefine the principle of optimality. Apr/May 2019 Dec 2010,Nov/Dec 2017
The principle of optimality states that an optimal sequence of decisions has the
property that whatever the initial state and decision are, the remaining decisions
must constitute an optimal decision sequence with regard to the state resulting
from the first decision.
15
CS3401 ALGORITHMS UNIT 3 MEC
Multistage Graph
Optimal Binary Search Tree (OBST)
0/1 Knapsack Problem
Travelling Salesman Problem.
All Pair Shortest Path Problem
49. What are optimal binary search trees OBST? May 2010
Let { a1, a2,….an} be a set of identifiers such that a1<a2<a3…let p(i) be the
probability with which we can search for ai is Successful search.
Let , qi be the probability of searching an element x such that
ai<x<ai+1 where 0≤i≤ n is unsuccessful search . thus p(i) is
probability of successful search and q(i) is the probability of
unsuccessful search.
Then a tree which is build with optimum cost from
𝑛
𝑛
∑ p(i) ∑𝑖=1 q(i)is called optimal binary search tree
𝑖=1
16
CS3401 ALGORITHMS UNIT 3 MEC
Greedy method is comparatively efficient than divide and conquer but there is no as
such guarantee of getting optimum solution
In Greedy method , the optimum selection is without revising previously generated
solutions
54. Write control abstraction for the ordering paradigm. May 2012
Optimal substructure:
The dynamic programming technique makes use principle of optimality to find the
optimal solution from sub problems.
Overlapping Sub-problems:
57. Give the commonly used designing steps for dynamic programming algorithm.
17
CS3401 ALGORITHMS UNIT 3 MEC
o Both the divide and conquer and dynamic programming solve the problem by
breaking it into number of sub-problems.
o In both these methods solutions from sub-problems are collected together to
form a solution to given problem.
59. Define Catalan number.
nthcatalan number.
C(0) = 1
18
CS3401 ALGORITHMS UNIT 3 MEC
sub problems.
63. Write down the optimization techniques used for warshall’s algorithm. state the rules
and assumption which are implied behind that.(AU April/may 2015)
Dynamic programming algorithms are used for optimization (for example, finding the
shortest path between two points, or the fastest way to multiply many matrices).. The
alternatives are many, such as using a greedy algorithm, which picks the locally optimal
choice at each branch in the road.
The locally optimal choice may be a poor choice for the overall solution. While a greedy
algorithm does not guarantee an optimal solution, it is often faster to calculate. Fortunately,
some greedy algorithms (such as minimum spanning trees) are proven to lead to the
optimal solution.
Dijkstra’s algorithm solves the single source shortest path problem of finding shortest paths
from a given vertex( the source), to all the other vertices of a weighted graph or digraph.
Dijkstra’s algorithm provides a correct solution for a graph with non negative weights.
65. State Assignment problem.
There are n people who need to be assigned to execute n jobs, one person per job. (That is,each
person is assigned to exactly one job and each job is assigned to exactly one person.) The cost
that would accrue if the ith person is assigned to the jth job is a known quantity
19
CS3401 ALGORITHMS UNIT 3 MEC
𝑖, 𝑖 = 1, 2, . . .
1. The time efficiency of Dijkstra’s algorithm depends on the structure used for
implementing the priority queue and for representing as input graph.
2. The efficiency is ϴ(|V|2) for graphs represented by their weight matrix and the
priority queue implemented as an unordered array.
3. The efficiency is ϴ(|E|log|V|) for graphs represented by the adjacency linked list
and the priority queue implemented as a min heap.
4. Better efficiency can be achieved if priority queue is implemented using a
sophisticated data structure called the Fibonacci Heap.
C(n,0)= 1
C(n, n)=1
68. What is best algorithm suited to identity the topology for a graph? Mention its
efficiency factors.
An alternative algorithm for topological sorting is based on depth-first search. The algorithm
loops through each node of the graph, in an arbitrary order, initiating a depth-first search that
terminates when it hits any node that has already been visited since the beginning of the
topological sort or the node has no outgoing edges (i.e. a leaf node):
The usual algorithms for topological sorting have running time linear in the number of nodes
plus the number of edges, asymptotically, O(|V|+|E|)
20
CS3401 ALGORITHMS UNIT 3 MEC
Problem description:
A multistage graph G=(V,E) is a directed graph in which the vertices are portioned into K> 2
disjoint sets Vi, 1<i<=K.
if (u,v) is an edge in E, then u E Vi and VEVi+1 for some i., 1< = i< =K.
The sets V1 and Vk are such that (V1)= VK/=1, Let S and t respectively the vertex in b1 and bk.
The vertex S is the source, and t is the sin R. Let C (i, j) be the cost of edge (i,j)
The cost of a path from S to t is the sum of the cost of edges on the path.
Every path from S to t starts in stage 1, goes to stage 2, then to stage 3, then to stage 4, etc., and
finally terminates in stage K.
The idea:
Compute the solutions to the sub-problems once and store the solutions in a table, so that
they can be reused (repeatedly)later
Structure
Principle of Optimality
Bottom-up computation
Construction of optimal solution
71. Define transitive closure of a directed graph. APR-2018
Transitive closure of a graph. Given a directed graph, find out if a vertex j is reachable
from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that
there is a path from vertex i to j. The reach-ability matrix is called transitive closure of a
graph.
72. What is the constraint of for binary search tree insertion? April/May 2019
A binary search tree is a tree with one additional constraint — it keeps the elements in
the tree in a particular order. Formally each node in the BST has two children (if any are
missing we consider it a nil node), a left child and a right child.
73. Define Brute Force. Or what is brute force method? Nov/Dec 2019
21
CS3401 ALGORITHMS UNIT 3 MEC
A binary search tree (BST), also known as an ordered binary tree, is a node-based data
structure in which each node has no more than two child nodes. Each child must either be a
leaf node or the root of another binary search tree. The left sub-tree contains only nodes
with keys less than the parent node; the right sub-tree contains only nodes with keys
greater than the parent node.
The BST data structure is the basis for a number of highly efficient sorting and searching
algorithms, and it can be used to construct more abstract data structures including sets,
multisets, and associative arrays.
The greedy strategy is a problem-solving approach that follows a simple, intuitive process:
make the locally optimal choice at each step, hoping that these local solutions will lead to a
globally optimal solution. Here are the main elements that define a greedy strategy:
76. what kind of problem can be solved using divide and conquer method Apr/May 2024
1. Sorting Problems
Merge Sort: Divides the array into halves, sorts them recursively, and merges.
Quick Sort: Partitions the array, recursively sorts smaller partitions.
2. Searching Problems
Binary Search: Repeatedly divides the search space into halves until the target is found.
22
CS3401 ALGORITHMS UNIT 3 MEC
PART-B
Combine the solutions of these sub problems to get the solution of original problem.
Algorithm DC(p)
Return solution of P.
Else{
DC( p2)….Dc(pn));
}}
23
CS3401 ALGORITHMS UNIT 3 MEC
Example: To compute sum of n numbers then by divide and conquer we can solve the problem as
(a0 + ….an-1)
Solution 1 Solution 2
(a0 + ….an-1)
If we want to divide a problem of size n in to a size of n /b taking f(n) time to divide and
combine , then we can set up recurrence relation for obtaining time for size n is
T(n/b) = Time for size n/b time required for dividing the problem in to sub
problem.
The above equation is called general divide and conquer recurrence. The order of growth of
T(n) depends upon the constants a, b and order of growth function f(n).
Binary search
Quick sort
Merge sort
Example 1 :
Consider the problem of computing the sum of number a 0 …… [Link] n > 1, the
problem is divided into two instances of the same problem.
They are
Once the two instances are computed, add their values to get the sum of original problem.
24
CS3401 ALGORITHMS UNIT 3 MEC
where, f(n) is a function that accounts for the time spent on dividing the problem into
smaller ones and on combining their solutions.
The order of growth of T(n) depends on the values of the constants ‘a’ and ‘b’ and the order
of growth of the function f(n).
For example, the recurrence equation for the number of additions is
a(n) = 2a(n/2) + 1
Applications
1. As the name suggests, ‘Divide and Conquer is a strategy in which a given problem is split
into a set of sub problems.
2. Each sub-problem is then handled/solved individually.
3. Once all the sub-problems are solved, we combine the sub-solutions of these sub
problems and find the final solution.
2. Explain the Finding maximum and minimum algorithm with the help of illustrative
Example.
Divide and Conquer (DAC) approach has three steps at each level of recursion:
Divide and Conquer (DAC) approach has three steps at each level of recursion:
Combine the solutions of all the sub-problems into a solution for the original
problem.
25
CS3401 ALGORITHMS UNIT 3 MEC
The problem is to find the maximum and minimum value in a set of ‘n’ elements.
Hence, the time is determined mainly by the total cost of the element comparison.
Explanation:
a. Straight MaxMin requires 2(n-1) element comparisons in the best, average & worst cases.
c. Hence we can replace the contents of the for loop by, If (a [i]> Max) then Max = a [i]; Else
if (a [i]< 2(n-1)
d. On the average a[i] is > max half the time, and so, the avg. no. of comparison is 3n/2-1.
A Divide and Conquer Algorithm for this problem would proceed as follows:
a. Let P = (n, a [i],……,a [j]) denote an arbitrary instance of the problem.
b. Here ‘n’ is the no. of elements in the list (a [i],….,a[j]) and we are interested in finding the
maximum and minimum of the list.
c. If the list has more than 2 elements, P has to be divided into smaller instances.
d. For example, we might divide ‘P’ into the 2 instances, P1=([n/2],a[1],……..a[n/2]) & P2= (
n-[n/2], a[[n/2]+1],….., a[n]) After having divided ‘P’ into 2 smaller sub problems, we can
solve them by recursively invoking the same divide-and-conquer algorithm.
Algorithm:
26
CS3401 ALGORITHMS UNIT 3 MEC
Example:
A 1 2 3 4 5 6 7 8 9
Values 22 13 -5 -8 15 60 17 31 47
Tree Diagram:
i. In this Algorithm, each node has 4 items of information: i, j, max & min.
ii. In root node contains 1 & 9 as the values of i& j corresponding to the initial call to
MaxMin.
iii. This execution produces 2 new calls to MaxMin, where i& j have the values 1, 5 & 6, 9
respectively & thus split the set into 2 subsets of approximately the same size.
iv. Maximum depth of recursion is 4.
Complexity:
If T(n) represents this no., then the resulting recurrence relations is
T (n)=T([n/2]+T[n/2]+2 n>2
1 n=2
1 n=1
When ‘n’ is a power of 2, n=2k for some positive integer ‘k’, then
T (n) = 2T(n/2) +2
= 2(2T(n/4)+2)+2
27
CS3401 ALGORITHMS UNIT 3 MEC
= 4T(n/4)+4+2
*
*
= 2k-1 T (2) + Σ 1 ≤ I ≤ k-1 ≤ 2i
= 2k-1+ 2k - 2
T(n) = (3n/2) – 2
Note that (3n/2) - 2 is the best-average and worst-case no. of comparisons when ‘n’ is a
power of 2.
3. Explain the Merge Sort algorithm with the help of illustrative Example.
Dec2013/14/15/16OR Explain the working of Merge Sort Algorithm with an example.
Nov/Dec 2017. (APR/MAY 2023)
The merge sort is a sorting algorithm that uses the divide and conquer strategy.
Division is dynamically carried out.
Merging is the process of combining two or more files into a new sorted file.
Merge sort on an input array with n elements consists of three steps:
Divide: partition array into two sub lists s1 and s2 with n/2 elements each Conquer: then
sort sub list s1 and sub list s2.
Merge sort is a perfect example of a successful application of the divide and conquer
technique.
It sorts a given array A[0…..n − 1] by dividing it into two halves A[0…..[n/2]−1] and
A[[n/2]…..n − 1].
It sorts each half separately by using recursive procedure, and Then, merging the
Steps to be followed
The first step of the merge sort is to chop the list into two.
If the list has even length, split the list into two equal sub lists.
If the list has odd length, divide the list in two by making the first sub list one entry
greater than the second sub list.
Then split both the sub lists into two and go on until each of the sub lists are of size
one.
Finally, start merging the individual sub lists to obtain a sorted list.
Example:
The operation of the algorithm for the array of element (8,3,2,9,7,1,5,4) is explained in the figure
28
CS3401 ALGORITHMS UNIT 3 MEC
given below.
ALGORITHM
If n > 1
Mergesort(C[0..[n/2] − 1])
Then the remaining elements of the other array are copied to the end of the next array.
29
CS3401 ALGORITHMS UNIT 3 MEC
i ← 0; j ← 0; k ← 0
if B[i] ≤ C[j ]
A[k]← B[i];
i←i+1
else
A[k]← C[j ];
j←j+1
k←k+1
ifi = p
else
In merge sort algorithm the two recursive calls are made. Each recursive call focuses on
n/2 elements of the list .
After two recursive calls one call is made to combine two sub list i.e to merge all n
elements.
30
CS3401 ALGORITHMS UNIT 3 MEC
The time complexity of merge sort can be calculated using two methods
Master theorem
Substitution method
Master theorem
let
T(1) = 0 ----------- (2 )
T(n) = Θ (n d long n ) if a = b
As equation ( 1),
i.e 2 = 2`
Hence the average and worst case time complexity of merge sort is
Substitution method
T(1) = 0 -------(4)
Assume n=2k
T(n) = 2T(n/2) + cn
31
CS3401 ALGORITHMS UNIT 3 MEC
If k = k-1 then,
…..….
T(2k) = 2k .0 +. k. c . 2k
T(2k) = k. c . 2k
i.e. log 2 n = k
Hence the average and worst case time complexity of merge sort is
32
CS3401 ALGORITHMS UNIT 3 MEC
Sorting
Tape Sorting
Data Processing
Demerit
4. Explain the Quick Sort algorithm with the help of illustrative example Or Explain the
time complexity of quick sort method in detail OR Write the algorithm for Quick Sort and
write its time complexity with example list are 5, 3, 1, 9, 8, 2, 4, 7. Apr/May 2017
Write the algorithm for quick sort. Provide a complete analysis of quick sort
for the given set of numbers 12, 33, 23, 43, 44, 55, 64, 77 and 76. (13) Nov/Dec
2018Or Write the quick sort algorithm and explain it example. Derive the worst
case and average case time complexity April/May 2019
Quick sort is a sorting algorithm that uses the divide and conquers strategy.
The three steps of quick sort are as follows:
Divide:
Split the array into two sub arrays that each element in the left sub array
is less thanor equal the middle element and each element in the right sub array is
greater than the middle element .
The splitting of the array into two sub array is based on pivot element. All the
elements that are less than pivot should be in left sub array and all the elements that
are more than pivot should be in right sub array
Conquer: Recursively sort the two sub arrays.
Combine: Combine all the sorted elements in a group to form a list of sorted elements
Quick sort is also referred as Partition Exchange sort.
The problem of sorting a set is reduced to the problem of sorting two smaller
subsets.
Quick sort divides input elements according to their position in the [Link] also
divides the input elements according to the value of element.
To achieve the partition, quick sort rearrange the given array element a[0,..n-1]
It is a situation where all the elements before the position ‘S’ are smaller than or
equal to a[s] and all the elements after position ‘s’ are greater than or equal to a[s].
33
CS3401 ALGORITHMS UNIT 3 MEC
After partitioning, a[s] will be in its final position in the sorted array.
Then sorting of element of two sum arrays preceding and following a[s] can be done
independently.
After both scans stop, three situations may arise, depending on whether or not the
scanning indices have crossed.
1. If scanning indices i and j have not crossed, i.e., i< j, we simply xchange A[i] and A[j ] and
resume the scans by incrementing i and decrementing j, respectively:
2. If the scanning indices have crossed over, i.e., i> j, we will have partitioned the Sub array after
exchanging the pivot with A[j].
3. Finally, if the scanning indices stop while pointing to the same element, i.e.,i = j, the value they
are pointing to must be equal to p.
Thus, we have the sub array partitioned, with the split position s= i=j:
Combine the last case with the case of crossed-over indices (i>j ) by exchanging the pivot with A[j]
whenever i ≥ j .
Example
5 3 1 9 8 2 4 7
34
CS3401 ALGORITHMS UNIT 3 MEC
P i j
5 3 1 9 8 2 4 7
P i j
5 3 1 9 8 2 4 7
P i j
5 3 1 9 8 2 4 7
P i j
5 3 1 4 8 2 9 7
Now also exchange a[i] and a[j], the resultant array becomes,
P i j
5 3 1 4 2 8 9 7
Now the scanning indices i and j have not crossed (ie) i< j, simply exchange i and j.
P j i
5 3 1 4 2 8 9 7
The result is
2 3 1 4 5 8 9 7
Now, the array has been sub divided into sub array with pivot element as middle.
Sub array 1
2 3 1 4
P i j
2 3 1 4
35
CS3401 ALGORITHMS UNIT 3 MEC
P i j
2 3 1 4
P i j
2 1 3 4
P j i
2 1 3 4
P i j
1 2 3 4
Sub array 3
3 4
P ij
3 4
j j
3 4
Sub array 2
8 9 7
P i j
8 9 7
36
CS3401 ALGORITHMS UNIT 3 MEC
P i j
8 7 9
It becomes
P j i
8 7 9
7 8 9
1 2 3 4 5 7 8 9
RecursiveCalls Tree
Tree of recursive calls to Quicksort with input values l and r of subarray bounds and split position
s of a partition obtained.
ALGORITHM Quicksort(A[l..r])
37
CS3401 ALGORITHMS UNIT 3 MEC
if l<r
Quicksort(A[l..s − 1])
Quicksort(A[s + 1..r])
//Input: Subarray of array A[0..n − 1], defined by its left and //right indices l and r (l < r)
//Output: Partition of A[l..r], with the split position returned //as this function’s value
p ← A[l]
i ← l; j ← r + 1
repeat
swap(A[i], A[j ])
untili ≥ j
swap(A[l], A[j ])
return j
The number of key comparisons made before a partition is achieved is n + 1 if the scanning
indices i and j cross over.
If the array is always partitioned at the mid , then it brings the best case efficiency of an
algorithm
The number of key comparisons in the best case satisfies the recurrence
38
CS3401 ALGORITHMS UNIT 3 MEC
If f(n) ∈Θ (n d ) then
T(n) = Θ (n d) if a <bd
T(n) = Θ (n d log n ) if a = bd
T(n) = Θ (n log ba ) if a> b bd
C(n) = 2 C(n/2) +n
Now , a = 2 and b = 2
We get ,
Cbest(n) = Θ (n log n)
C(n) = 2C (n/2) +n
Assume n = 2K since each time the list is divide into two equal halves .then equation becomes,
C(2K) = 2C(2k-1) + 2k
39
CS3401 ALGORITHMS UNIT 3 MEC
----
C(1) = 0
C( n) = n.0 + log 2 n . n
isΘ (n log n)
The worst case for quick sort occurs when the pivot is a minimum or maximum of all the
elements in the list .
For example,
40
CS3401 ALGORITHMS UNIT 3 MEC
Cworst(n) = (n -1) + n
But as we know
1 + 2+ 3 +---- + n = n (n + 1)/2 = ½ n2
Cworst(n) ∈ θ(n2)
Let Cavg(n) be the average number of key comparison made by Quick Sort.
The partition split can be happen in each position S (0≤S≤n-1) with the probability 1/n.
Thus, on the average case, Quick Sort makes 38% more comparison the best case.
Hence average case time complexity of quick sort is Θ ( n log n)
Application
To improve the efficiency of the Quick sort various methods are used to choose the pivot
element.
One such method is called, median of three partitioning that uses the pivot element as the
median of left most, right most and the middle element of the array.
41
CS3401 ALGORITHMS UNIT 3 MEC
5. Define dynamic programming and explain the problems that can be solved using
dynamic Programming.
Synopsis:
Introduction
Problems that can be solved using dynamic programming
Principle of optimality
Computing a Binomial Coefficient
Example
Introduction:
A dynamic-programming algorithm solves each sub problem just once and then
saves its answer in a table, thereby avoiding the work of recomputing the answer
every time it solves each sub problem.
42
CS3401 ALGORITHMS UNIT 3 MEC
C(n,0)= 1
C(n, n)=1
Solution:
n=4, k=2
C(4,2) = C(n-1,k-1)+C(n-1,k)
C(2, 0) = 1
C( 2,1) = C( 1, 0) + C( 1,1)
= 1 +1
C(2,1) = 2 ------------------(3)
C(3,1) = 1 +2
C(3,1) = 3 -------------------(4)
C( 3,2) = C( 2, 1) + C( 2,2)
But as C(n,n) = C( 2,2) = 1 , we will put values of C(2, 1) obtained in equation (3)
C( 3,2) = C( 2, 1) + C( 2,2)
= 2+ 1
C( 3,2) = 3 --------------------(5)
44
CS3401 ALGORITHMS UNIT 3 MEC
C( 4,2) = C( 3, 1) + C( 3,2)
C( 4,2) = 3 + 3
To compute the value of C(n,k), the table of figure is filled by row , starting with row 0 and
ending with row n.
Each row i(0≤ i ≤ n) is filled left to right, starting with 1 because C(n,0)=1.
Rows 0 through k also end with 1 on the table’s main diagonal (ie)
C(i,i)=1for 0≤ i ≤ k
The other entries of the table is computed by using the formula C(n,k)=C(n-1,k-1)+C(n-1,k),
for n>k>0 adding the contents of the cells in the preceding row and the previous column in
the preceding row and the same column.
Algorithm
Algorithm Binomial(n,k)
for i←0 to n do
45
CS3401 ALGORITHMS UNIT 3 MEC
for j ←0 to min(i,k) do
if j=0 or j=k
C[i,j] ← 1
else
return C[n,k]
Analysis:
Two main properties of a problem suggest that the given problem can be solved using
Dynamic Programming.
These properties are
Overlapping sub-problems
46
CS3401 ALGORITHMS UNIT 3 MEC
Optimal substructure.
Overlapping Sub-Problems
Similar to Divide-and-Conquer approach, Dynamic Programming also combines solutions
to sub-problems. It is mainly used where the solution of one sub-problem is needed
repeatedly. The computed solutions are stored in a table, so that these don’t have to be re-
computed. Hence, this technique is needed where overlapping sub-problem exists.
For example, Binary Search does not have overlapping sub-problem. Whereas recursive
program of Fibonacci numbers have many overlapping sub-problems.
Fibonacci series
F(n)=F(n-1)+F(n-2),for n>1…………………1
F(0)=0
F(1)=1
ax(n)+bx(n-1)+cx(n-2)=0 ……………(2)
Where,
a,b,c are fixed real numbers called the coefficients of recurrence and a≠0
Ar2+br+c=0 ………………….(3)
F(n)-F(n-1)-F(n-2)=0 ………….(4)
47
CS3401 ALGORITHMS UNIT 3 MEC
r2-r-1=0
R1,2=
R1,2=
R1=
R2=
X(n)=αr1n+βr2n ……..(5)
By solving equation (7) and (8),the linear equation in two unknown α and β
α+ β=0
(11)-(10) gives
( ) β-( ) β=-1
48
CS3401 ALGORITHMS UNIT 3 MEC
𝛃 √𝟓 𝛃 √𝟓
+ β- 𝟐 + β = -1
𝟐 𝟐 𝟐
√𝟓
𝟐 β = -1
𝟐
√𝟓
β=-𝟐
√5
Substitute β = - 2 in (9)
α+β=0
𝟏
α- =0
√𝟓
𝟏 √𝟓
α= β=-
√𝟓 𝟐
𝟏
F(n) = ⟦𝝓𝐧 − 𝝓^𝐧⟧
√𝟓
Where
𝟏+√𝟓
Φ= 𝟐
Φ = 1.61803
1
Φ^ =- Φ
Φ^ = - 0.61803
When n goes to infinity, Φ^ gets infinitely small value. So, it can be omitted.
Therefore
𝟏
F(n) = Φn (13)
√𝟓
𝟏
So, for every non negative n, F(n) = Φ n is rounded to the nearest integer.
√𝟓
First method
49
CS3401 ALGORITHMS UNIT 3 MEC
Algorithm F(n)
if n<1
return n
Else
return F(n-1)+(n-2)
Let A(n) is the number of additions performed by the algorithm to compute F(n).
The number of additions needed to compute F(n-1) is A(n-1) and the number of
additions needed to compute F(n-2) is A(n-2).
The algorithm needs one more addition to compute the sum of A(n-1) and A(n-2).
A(1)=0
A(n)+1]-[A(n-1)+1]-[A(n-2)+1]=0 (14)
Now substitute,
B(n)=A(n)+1
B(n)-B(n-1)-B(n-2)=0
50
CS3401 ALGORITHMS UNIT 3 MEC
B(0)=0
B(1)=1
Here
B(n)=F(n+1)
Since
B(n)=A(n)+1
B(n-1)=A(n)
So A(n)=B(n)-1
We know that
F(n)=
F(n+1)= ………(16)
A(n)= -1
Hence
A(n)€
The poor efficiency class of algorithm could be anticipated from the class of
recurrence
The reason behind the algorithm inefficiency can be traced by looking at the tree of
recursive calls n=6
The same values of the function are evaluated again and again which is extremely
inefficiently.
51
CS3401 ALGORITHMS UNIT 3 MEC
F(6)
F(5) F(4)
F(3) F(2)
F(4) F(3)
F(1) F(0)
F2) F(1) F(2) F(1)
F(3) F(2)
F(2) F(1)
F(0)
F(1)
Fig Tree of recursive calls for computing the Fibonacci number for n = 6
Optimal Sub-Structure
A given problem has Optimal Substructure Property, if the optimal solution of the
given problem can be obtained using optimal solutions of its sub-problems.
For example, the Shortest Path problem, A rod Cutting problem has the following
optimal substructure property −
If a node x lies in the shortest path from a source node u to destination node v, then
the shortest path from u to v is the combination of the shortest path from u to x, and
the shortest path from x to v.
The standard All Pair Shortest Path algorithms like Floyd-Warshall and Bellman-
Ford are typical examples of Dynamic Programming.
Example of rod Cutting problem:
A rod is given of length n. Another table is also provided, which contains different size and
price for each size. Determine the maximum price by cutting the rod and selling them in
the market.
To get the best price by making a cut at different positions and comparing the prices after
cutting the rod.
Let the f(n) will return the max possible price after cutting a row with length n. We can
simply write the function f(n) like this.
f(n) := maximum value from price[i]+f(n – i – 1), where i is in range 0 to (n – 1).
52
CS3401 ALGORITHMS UNIT 3 MEC
Output:
Maximum profit after selling is 22.
Cut the rod in length 2 and 6. The profit is 5 + 17 = 22
Algorithm
rodCutting(price, n)
Input: Price list, number of different prices on the list.
Output: Maximum profit by cutting rods.
Begin
define profit array of size n +1
profit[0] := 0
for i := 1 to n, do
maxProfit := - ∞
for j := 0 to i-1, do
maxProfit := maximum of maxProfit and (price[j] + profit[i-j-1])
done
profit[i] := maxProfit
done
return maxProfit
End
[Link] the Matrix chain multiplication problem with an example.(Apr/may 2023,
2024) Aprl/May 2024
Matrix chain multiplication (or Matrix Chain Ordering Problem, MCOP) is an optimization
problem that to find the most efficient way to multiply a given sequence of matrices. The
53
CS3401 ALGORITHMS UNIT 3 MEC
problem is not actually to perform the multiplications but merely to decide the sequence of
the matrix multiplications involved.
Following is the recursive algorithm to find the minimum cost:
Example: Given the sequence {4, 10, 3, 12, 20, and 7}. The matrices have size 4 x 10, 10 x 3,
3 x 12, 12 x 20, 20 x 7. We need to compute M [i,j], 0 ≤ i, j≤ 5. We know M [i, i] = 0 for all i.
Let us proceed with working away from the diagonal. We compute the optimal solution for
the product of 2 matrices.
We have to sort out all the combination but the minimum output combination is taken into
consideration.
54
CS3401 ALGORITHMS UNIT 3 MEC
1. m (1,2) = m1 x m2
= 4 x 10 x 10 x 3
= 4 x 10 x 3 = 120
2. m (2, 3) = m2 x m3
= 10 x 3 x 3 x 12
= 10 x 3 x 12 = 360
3. m (3, 4) = m3 x m4
= 3 x 12 x 12 x 20
= 3 x 12 x 20 = 720
4. m (4,5) = m4 x m5
= 12 x 20 x 20 x 7
= 12 x 20 x 7 = 1680
o We initialize the diagonal element with equal i,j value with '0'.
o After that second diagonal is sorted out and we get all the values corresponded to it
Now the third diagonal will be solved out in the same way.
M [1, 3] = M1 M2 M3
1. There are two cases by which we can solve this multiplication: ( M1 x M2) + M3,
M1+ (M2x M3)
2. After solving both cases we choose the case in which minimum output is there.
M [1, 3] =264
As Comparing both output 264 is minimum in both cases so we insert 264 in table and (
M1 x M2) + M3 this combination is chosen for the output making.
M [2, 4] = M2 M3 M4
1. There are two cases by which we can solve this multiplication: (M2x M3)+M4,
M2+(M3 x M4)
55
CS3401 ALGORITHMS UNIT 3 MEC
2. After solving both cases we choose the case in which minimum output is there.
M [2, 4] = 1320
As Comparing both output 1320 is minimum in both cases so we insert 1320 in table and
M2+(M3 x M4) this combination is chosen for the output making.
M [3, 5] = M3 M4 M5
1. There are two cases by which we can solve this multiplication: ( M3 x M4) + M5,
M3+ ( M4xM5)
2. After solving both cases we choose the case in which minimum output is there.
M [3, 5] = 1140
As Comparing both output 1140 is minimum in both cases so we insert 1140 in table and (
M3 x M4) + M5this combination is chosen for the output making.
M [1, 4] = M1 M2 M3 M4
1. ( M1 x M2 x M3) M4
2. M1 x(M2 x M3 x M4)
3. (M1 xM2) x ( M3 x M4)
After solving these cases we choose the case in which minimum output is there
56
CS3401 ALGORITHMS UNIT 3 MEC
M [1, 4] =1080
As comparing the output of different cases then '1080' is minimum output, so we insert
1080 in the table and (M1 xM2) x (M3 x M4) combination is taken out in output making,
M [2, 5] = M2 M3 M4 M5
1. (M2 x M3 x M4)x M5
2. M2 x( M3 x M4 x M5)
3. (M2 x M3)x ( M4 x M5)
After solving these cases we choose the case in which minimum output is there
M [2, 5] = 1350
As comparing the output of different cases then '1350' is minimum output, so we insert
1350 in the table and M2 x( M3 x M4 xM5)combination is taken out in output making.
M [1, 5] = M1 M2 M3 M4 M5
1. (M1 x M2 xM3 x M4 )x M5
2. M1 x( M2 xM3 x M4 xM5)
3. (M1 x M2 xM3)x M4 xM5
4. M1 x M2x(M3 x M4 xM5)
After solving these cases we choose the case in which minimum output is there
57
CS3401 ALGORITHMS UNIT 3 MEC
M [1, 5] = 1344
As comparing the output of different cases then '1344' is minimum output, so we insert
1344 in the table and M1 x M2 x(M3 x M4 x M5)combination is taken out in output making.
let us assume that matrix Ai has dimension pi-1x pi for i=1, 2, 3....n.
The input is a sequence (p0,p1,......pn) where length [p] = n+1.
The procedure uses an auxiliary table m [1....n, 1.....n] for storing m [i, j] costs an
auxiliary table s [1.....n, 1.....n] that record which index of k achieved the optimal
costs in computing m [i, j].
The algorithm first computes m [i, j] ← 0 for i=1, 2, 3.....n, the minimum costs for the
chain of length 1
MATRIX-CHAIN-ORDER (p)
1. n length[p]-1
2. for i ← 1 to n
3. do m [i, i] ← 0
4. for l ← 2 to n // l is the chain length
5. do for i ← 1 to n-l + 1
6. do j ← i+ l -1
7. m[i,j] ← ∞
8. for k ← i to j-1
9. do q ← m [i, k] + m [k + 1, j] + pi-1 pk pj
10. If q < m [i,j]
11. then m [i,j] ← q
12. s [i,j] ← k
13. return m and s.
58
CS3401 ALGORITHMS UNIT 3 MEC
PRINT-OPTIMAL-PARENS (s, i, j)
1. if i=j
2. then print "A"
3. else print "("
4. PRINT-OPTIMAL-PARENS (s, i, s [i, j])
5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j)
6. print ")"
Analysis: There are three nested loops. Each loop executes a maximum n times.
9. using dynamic approach programming, solve the following Multistage Graph using
the forward and backward approach. (APRIL/MAY 2011)
Multistage Graph:-
Concept:
Problem description:
59
CS3401 ALGORITHMS UNIT 3 MEC
l€ Vi+1
(j,l) €E
Cost ( 1,s)
Example:
Find the shortest distance between source ‘s’ and sink ‘t’.
= Min{(6+4), 5+2)}
= Min {10,7}
60
CS3401 ALGORITHMS UNIT 3 MEC
Cost (3,6) =7
= Min {( 8,5)}
Cost (3,7) =5
= Min (7,11)
Cost (3,8) = 7
= Min (11,7,8)
Cost (2,2) =7
= Min ( 18)
Cost (2,4) = 18
61
CS3401 ALGORITHMS UNIT 3 MEC
1. Cost (1,1) = Min ( 9+ Cost (2,2) 7+ Cot (2,3),3+ Cost (2,4) 2+ Cost
(2,5))
= Min (9+7, 7+9, 3+18, 2+15)
= Min (16,16,21,17)
Cost (1,1) = 16
Program:-
D[j] = r;
P[1] = 1
P[k] = n;
for(j=2,j<K-1; j+1)
P[j]=d(P[j-1]];
62
CS3401 ALGORITHMS UNIT 3 MEC
v2 =d(1,1)=2
v3 =d(2,D(1,1))
v3 =d(2,2)=7
=d(3,d(2,d(1,1)))
=d(3,7)
=10
(l,j)€E
bcost(2,2)=min{c(1,2)}
=9
bcost(2,3)=min{c(1,3)}
=7
bcost(2,4)=min{c(1,4)}
=3
bcost(2,5)=min{c(1,5)}
=2
63
CS3401 ALGORITHMS UNIT 3 MEC
= min {13,9}
=9
= min {11,14,13)
=11
= min {10,14,10)
=10
= min {15,15}
=15
bcost(3,8)+c(8,10)}}
= min {(9+5),(11+3), (10+5)}
= min {14,14,15}
=14
= min {16}
=16
64
CS3401 ALGORITHMS UNIT 3 MEC
bcost(4,11)+c(11,12)}
= min {(15+4), (14+2),(16+5)}
= min {19,16,21}
=16
// minimum
Bcost[j] = bcost[r]+C[r,j];
D[j]=r;
P[1] =1;
P[k]=n;
for(j=k-1,j>=2,j--)
P[j]=d[P[j+1]];
Time complexity:
65
CS3401 ALGORITHMS UNIT 3 MEC
Finding the minimum cost for each and every stage – θ(|V|+|E|)
Space complexity:
Communication networks.
10. Write a pseudo code to find Optimal binary search trees using dynamic
programming(OBST) May 2008/2011 & Dec 2013 may 2015Or Obtain a optimal binary
search tree for following nodes (do, if ,int , while) with following probabilities ( 0.1, 0.2 , 0.4,
0.3)Or(i) outline dynamic programming approach to solve the optimal binary search tree
problem and analyse its time complexity
(ii) Construct the optimal binary search tree for the following 5 keys with probabilities
asindicated. Nov/Dec 2019
I 0 1 2 3 4 5
A binary search tree is one of the most important data structures in computer
science.
66
CS3401 ALGORITHMS UNIT 3 MEC
Figure depicts two out of 14 possible binary search trees containing these keys.
The average number of comparisons in a successful search in the first of these trees is
0. 1+ 0.2 .2 + 0.4 .3+ 0.3 .4 = 2.9,
Definition
Let {a1, a2,….an} be a set of identifiers such that a1<a2<a3…let , p(i) be the
probability with which we can search for ai is Successful search.
Let qi be the probability of searching an element x such that ai<x<ai+1 where 0≤i≤ n
is unsuccessful search.
Thus p(i) is probability of successful search and q(i) is the probability of
unsuccessful search.
𝑛
𝑛
Then a tree which is build with optimum cost from ∑ p(i) ∑𝑖=1 q(i) is called
𝑖=1
optimal binary search tree.
67
CS3401 ALGORITHMS UNIT 3 MEC
1. For such a binary search tree , the root contains key ak, the left sub tree Tik -1
contains keys ai, . . . , ak−1 optimally arranged, and the right subtree Tjk+1 contains
keys ak+1, . . . , ajalso optimally arranged.
2. If we count tree levels starting with 1 to make the comparison numbers equal the
keys’ levels, the following recurrence relation is obtained:
Table of the dynamic programming algorithm for constructing an optimal binary search
tree.
68
CS3401 ALGORITHMS UNIT 3 MEC
EXAMPLE
Obtain a optimal binary search tree for following nodes (do, if ,int ,while) with
following probabilities ( 0.1, 0.2 , 0.4, 0.3)
Hence n = 4
69
CS3401 ALGORITHMS UNIT 3 MEC
70
CS3401 ALGORITHMS UNIT 3 MEC
71
CS3401 ALGORITHMS UNIT 3 MEC
72
CS3401 ALGORITHMS UNIT 3 MEC
Cost Table : 0 1 2 3 4
73
CS3401 ALGORITHMS UNIT 3 MEC
1
0 0.1
2
3 0 0.2
4
0 0.4
5
0 0.3
Root Table 0 1 2 3
1 1
2
2
3
4 3
Cost Table 4
C[ 1, 0] = 0
C[ 2, 1] = 0
C[ 3, 2] = 0 using formulae C[ i, i – 1] =0 and C[ n + 1,n] =0
C[ 4, 3] = 0
C[ 5, 4] = 0
C[ 1, 1] = 0.1
C[ 3, 3] = 0.4
C[ 4, 4] = 0.3
74
CS3401 ALGORITHMS UNIT 3 MEC
R[1, 1] =1
R[3, 3] =3
R[4, 4] =4
- -- (1)
Compute C[ 1, 2 ]
k= 1
= 0.5
k=2
Compute C[2, 3]
k=2
=1.0
75
CS3401 ALGORITHMS UNIT 3 MEC
k=3
Compute C[3, 4]
k=3
k=4
Therefore in cost table C[3,4] = 1.0 and R[3,4]=3The table contains values
obtained upto this calculations
Cost Table 0 1 2 3 4
0 0.1 0.4
1
0 0.2 0.8
2
0 0.4 1.0
3
4 0 0.3
0
5
76
CS3401 ALGORITHMS UNIT 3 MEC
Root Table
0 1 2 3
1 1 2
2
2 3
3
3 3
4
Compute C[1,3] 4
The value of k can be 1,2 or 3
k=1
= 1.5
k =2
= 1.2
k =3
Compute C [2,4]
77
CS3401 ALGORITHMS UNIT 3 MEC
k=2
= 1.9
k =3
k =4
= 1.7
Cost Table
0 1 2 3 4
3
0 0.4 1.0
4
5
0 0.3
78
CS3401 ALGORITHMS UNIT 3 MEC
Root Table
0 1 2 3
1 2 3
1
2 2 3 3
3
3 3
4
4
Compute C[1,4]
k=1
= 2.4
k =2
= 2.1
k =3
k=4
79
CS3401 ALGORITHMS UNIT 3 MEC
Cost Table 0 1 2 3 4
3
0 0.4 1.0
4
5
0 0.3
0
Root Table
0 1 2 3
1 2 3 3
1
2 2 3 3
3
3 3
4
1 2 3 4
The tree is
80
CS3401 ALGORITHMS UNIT 3 MEC
Tk Value of key
T[i, k-1]
T[k + 1, j]
R[1,4]
=3
R[1,2]= R[4,4]
2 =4
R[1,1]
=1
int
if while
do
ALGORITHM
81
CS3401 ALGORITHMS UNIT 3 MEC
//optimal BST and table R of sub trees’ roots in the optimal //BST
fori←1 to ndo
C[i, i− 1]←0
C[i, i]←P[i]
R[i, i]←I
C[n + 1, n]←0
fori←1 to n − d do
j←i+ d
minval←∞
fork←ito j do
kmin←k
R[i, j ]←kmin
sum←P[i];
fors ←i+ 1 to j do
sum←sum+ P[s]
82
CS3401 ALGORITHMS UNIT 3 MEC
returnC[1, n], R
Analysis:
The basic operation in above algorithm is computation of C[i,j] by finding the minimum
valued k.
This operation is located within three nested for loops hence the time complexity C(n) can
be
The greedy method uses the subset paradigm or ordering paradigm to obtain the
solution.
In subset paradigm, at each stage the decision is made based on whether a
particular input is in optimal solution or not .
83
CS3401 ALGORITHMS UNIT 3 MEC
o Candidate set: A solution that is created from the set is known as a candidate set.
o Selection function: This function is used to choose the candidate or subset which
can be added in the solution.
o Feasibility function: A function that is used to determine whether the candidate or
subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution or the
partial solution.
o Solution function: This function is used to intimate whether the complete function
has been reached or not.
The above is the greedy algorithm. Initially, the solution is assigned with zero value. We
pass the array and number of elements in the greedy algorithm. Inside the for loop, we
select the element one by one and checks whether the solution is feasible or not. If the
solution is feasible, then we perform the union.
Knapsack problem
Prim’s algorithm for minimum spanning tree
Kruskal’s algorithm for minimum spanning tree
Finding shortest path
Job sequence with deadlines
Optimal storage on tapes
For solving all above problems, a set of feasible solutions is obtained. From this
solution, optimum solution is selected.
This optimum solution then becomes the final solution for given problem.
84
CS3401 ALGORITHMS UNIT 3 MEC
Greedy method is used for obtaining Dynamic Programming is also for obtaining
optimum solution optimum solution
85
CS3401 ALGORITHMS UNIT 3 MEC
For each decision point in the algorithm, the choice that seems best at the moment is
chosen. This heuristic strategy does not always produce an optimal solution, but as we saw
in the activity-selection problem, sometimes it does.
The process that we followed in to develop a greedy algorithm was a bit more involved
than is typical. We went through the following steps:
1. Determine the optimal substructure of the problem.
2. Develop a recursive solution.
3. Prove that at any stage of the recursion, one of the optimal choices is the greedy
choice. Thus, it is always safe to make the greedy choice.
4. Show that all but one of the sub problems induced by having made the greedy choice
are empty.
5. Develop a recursive algorithm that implements the greedy strategy.
6. Convert the recursive algorithm to an iterative algorithm.
In practice, however, we usually streamline the above steps when designing a greedy
algorithm.
We develop our substructure with an eye toward making a greedy choice that leaves just
one sub problem to solve optimally.
For example, in the activity-selection problem, we first defined the sub problems Sij, where
both i and j varied. We then found that if we always made the greedy choice, we could
restrict the sub problems to be of the form Si.n+1.
Alternatively, we could have fashioned our optimal substructure with a greedy choice in
mind. That is, we could have dropped the second subscript and defined sub problems of the
form Si = {ak € S : fi ≤ sk}.
86
CS3401 ALGORITHMS UNIT 3 MEC
Then, we could have proven that a greedy choice (the first activity am to finish in Si),
combined with an optimal solution to the remaining set Sm of compatible activities, yields
an optimal solution to Si.
More generally, we design greedy algorithms according to the following sequence of steps:
1. Cast the optimization problem as one in which we make a choice and are left with
one subproblem to solve.
2. Prove that there is always an optimal solution to the original problem that makes the
greedy choice, so that the greedy choice is always safe.
3. Demonstrate that, having made the greedy choice, what remains is a subproblem
with the property that if we combine an optimal solution to the subproblem with the
greedy choice we have made, we arrive at an optimal solution to the original
problem.
How can one tell if a greedy algorithm will solve a particular optimization problem? There
is no way in general, but the greedy-choice property and optimal sub-structure are the two
key ingredients. If we can demonstrate that the problem has these properties, then we are
well on the way to developing a greedy algorithm for it.
Greedy-choice property
The first key ingredient is the greedy-choice property: a globally optimal solution can be
arrived at by making a locally optimal (greedy) choice. In other words, when we are
considering which choice to make, we make the choice that looks best in the current
problem, without considering results from subproblems.
Optimal substructure
Given this optimal substructure, we argued that if we knew which activity to use as ak, we
could construct an optimal solution to Sij by selecting ak along with all activities in optimal
solutions to the subproblems Sik and Skj. Based on this observation of optimal
substructure.
use a more direct approach regarding optimal substructure when applying it to greedy
algorithms. As mentioned above, we have the luxury of assuming that we arrived at a
subproblem by having made the greedy choice in the original problem. All we really need
to do is argue that an optimal solution to the subproblem, combined with the greedy choice
already made, yields an optimal solution to the original problem.
This scheme implicitly uses induction on the subproblems to prove that making the greedy
choice at every step produces an optimal solution.
87
CS3401 ALGORITHMS UNIT 3 MEC
Because the optimal-substructure property is exploited by both the greedy and dynamic-
programming strategies, one might be tempted to generate a dynamic-programming
solution to a problem when a greedy solution suffices, or one might mistakenly think that a
greedy solution works when in fact a dynamic-programming solution is required.
To illustrate the subtleties between the two techniques, let us investigate two variants of a
classical optimization problem.
The 0-1 knapsack problem is posed as follows. A thief robbing a store finds n items; the ith
item is worth vi dollars and weighs wi pounds, where vi and wi are integers. He wants to
take as valuable a load as possible, but he can carry at most W pounds in his knapsack for
some integer W.
Which items should he take? (This is called the 0-1 knapsack problem because each item
must either be taken or left behind; the thief cannot take a fractional amount of an item or
take an item more than once.)
In the fractional knapsack problem, the setup is the same, but the thief can take fractions of
items, rather than having to make a binary (0-1) choice for each item.
Both knapsack problems exhibit the optimal-substructure property. For the 0-1 problem,
consider the most valuable load that weighs at most W pounds.
13. Explain in detail about Activity-selection problem with an example. Apr/May 2024
The Activity Selection Problem is an optimization problem which deals with the selection of
non-conflicting activities that needs to be executed by a single person or machine in a given
time frame.
Each activity is marked by a start and finish time. Greedy technique is used for finding the
solution since this is an optimization problem.
Let's consider that you have n activities with their start and finish times, the objective is to
find solution set having maximum number of non-conflicting activities that can be executed
in a single time frame, assuming that only one person or machine is available for execution.
It might not be possible to complete all the activities, since their timings can collapse.
88
CS3401 ALGORITHMS UNIT 3 MEC
Greedy approach can be used to find the solution since we want to maximize the count of
activities that can be executed. This approach will greedily choose an activity with earliest
finish time at every step, thus yielding an optimal solution.
sol[] array referring to the solution set containing the maximum number of non-
conflicting activities.
Following are the steps we will be following to solve the activity selection problem,
Step 1: Sort the given activities in ascending order according to their finishing time.
Step 2: Select the first activity from sorted array act[] and add it to sol[] array.
Step 4: If the start time of the currently selected activity is greater than or equal to the
finish time of previously selected activity, then add it to the sol[] array.
In the table below, we have 6 activities with corresponding start and end time, the
objective is to compute an execution schedule having maximum number of non-conflicting
activities:
89
CS3401 ALGORITHMS UNIT 3 MEC
Step 1: Sort the given activities in ascending order according to their finishing time.
Step 2: Select the first activity from sorted array act[] and add it to the sol[] array, thus sol =
{a2}.
Step 3: Repeat the steps 4 and 5 for the remaining activities in act[].
Step 4: If the start time of the currently selected activity is greater than or equal to the
finish time of the previously selected activity, then add it to sol[].
A. Select activity a3. Since the start time of a3 is greater than the finish time
of a2 (i.e. s(a3) > f(a2)), we add a3 to the solution set. Thus sol = {a2, a3}.
B. Select a4. Since s(a4) < f(a3), it is not added to the solution set.
C. Select a5. Since s(a5) > f(a3), a5 gets added to solution set. Thus sol = {a2, a3, a5}
D. Select a1. Since s(a1) < f(a5), a1 is not added to the solution set.
90
CS3401 ALGORITHMS UNIT 3 MEC
E. Select a6. a6 is added to the solution set since s(a6) > f(a5). Thus sol = {a2, a3, a5,
a6}.
(1,2)
(3,4)
(5,7)
(8,9)
In the above diagram, the selected activities have been highlighted in grey.
91
CS3401 ALGORITHMS UNIT 3 MEC
Following are the scenarios for computing the time complexity of Activity Selection
Algorithm:
Case 1: When a given set of activities are already sorted according to their finishing
time, then there is no sorting mechanism involved, in such a case the complexity of
the algorithm will be O(n)
Case 2: When a given set of activities is unsorted, then we will have to use
the sort() method defined in bits/stdc++ header file for sorting the activities list.
The time complexity of this method will be O(nlogn), which also defines complexity
of the algorithm.
Scheduling multiple competing events in a room, such that each event has its own
start and end time.
Scheduling manufacturing of multiple products on the same machine, such that each
product has its own production timelines.
Optimal merge pattern is a pattern that relates to the merging of two or more sorted files
in a single sorted file. This type of merging can be done by the two-way merging method.
If we have two sorted files containing n and m records respectively then they could be
merged together, to obtain one sorted file in time O (n+m).
There are many ways in which pair wise merge can be done to get a single sorted file.
Different pairings require a different amount of computing time. The main thing is to pair
wise merge the n sorted files so that the number of comparisons will be less.
n
∑f(i)d(i)
i=1
92
CS3401 ALGORITHMS UNIT 3 MEC
Where, f (i) represents the number of records in each file and d (i) represents the depth
An optimal merge pattern corresponds to a binary merge tree with minimum weighted
external path length. The function tree algorithm uses the greedy rule to get a two- way
merge tree for n files.
The algorithm contains an input list of n trees. There are three field child, rchild, and
weight in each node of the tree. Initially, each tree in a list contains just one node. This
external node has lchildand rchild field zero whereas weight is the length of one of the n
files to be merged.
For any tree in the list with root node t, t = it represents the weight that gives the length of
the merged file. There are two functions least (list) and insert (list, t) in a function tree.
Least (list) obtains a tree in lists whose root has the least weight and return a pointer to
this tree. This tree is deleted from the list. Function insert (list, t) inserts the tree with
root t into the list.
The main for loop in this algorithm is executed in n-1 times. If the list is kept in increasing
order according to the weight value in the roots, then least (list) needs only O(1) time
and insert (list, t) can be performed in O(n) time. Hence, the total time taken is O (n2).
If the list is represented as a minheap in which the root value is less than or equal to the
values of its children, then least (list) and insert (list, t) can be done in O (log n) time. In this
condition, the computing time for the tree is O (n log n).
Example:
93
CS3401 ALGORITHMS UNIT 3 MEC
94
CS3401 ALGORITHMS UNIT 3 MEC
[Link] in detail about Huffman Trees. Or Write the Huffmans’ algorithm. Construct.
The Huffmans’ tree for the following data and obtain its Huffmans’ code. Nov/Dec 2017 or
(i)write the Huffman code algorithm and derive its time complexity(5+2)
(ii)generate the Huffman code for the following data comprising of alphabet and their
frequency.(6)
a:1, b :1 ,c :2, d :3, e :5, f: 8,g : 13,h : 21 Apr/May 2019, (APR/MAY 2023)
A Huffman tree is a binary tree that minimizes the weighted path length from the
root to the leaves containing a set of predefined weights.
The most important application of Huffman trees are Huffman codes.
A Huffman code is a optimal prefix tree variable length encoding scheme that
assigns bit strings to characters based on their frequencies in a given text.
This is accomplished by a greedy construction of a binary tree whose leaves
represent the alphabet characters and whose edges are labeled with 0’s and 1’s.
To encode a text that comprises n characters from some alphabet by assigning to
each of the text’s characters some sequence of bit called the code word.
Types of encoding
Fixed length encoding
Variable length encoding
Fixed length encoding
It assigns to each character a bit string of the some length m (m>=log 2n)
95
CS3401 ALGORITHMS UNIT 3 MEC
Step 1
Initialize n one node trees and label them with the characters of the alphabet.
Record the frequency of each character in its tree’s root to indicate the tree’s weight.
The weight of a tree will be equal to the sum of the frequencies in the tree’s leaves.
Step 2
Character A B C D -
96
CS3401 ALGORITHMS UNIT 3 MEC
97
CS3401 ALGORITHMS UNIT 3 MEC
Character A B C D -
Bits 2 3 2 2 3
D A D DAD
01 11 01 011101
B A D _ A D BAD_AD
With the occurrence probabilities given and the codeword lengths obtained, the expected
number of bits per character in this code is calculated as,Sum of the multiplications of
probability of characters and number of bits in the code word.
(i.e) =0.35*2+0.1*3+0.2*2+0.2*2+0.15*3
= 0.7+0.3+0.4+0.4+0.45
=2.25
In fixed length encoding, minimum three bits are used per characters.
Compression Ratio
(3-2.25)/3*100=0.75/3*100
= 0.25*100
=25%
So, Huffman encoding of a text will use 25%less memory than its fixed length encoding.
98
CS3401 ALGORITHMS UNIT 3 MEC
I=1
Where, li is the length of the simple path from the root to the ithleaf.
wi is the length of the frequency.
In coding application,
o li is the length of the codeword.
o wi is the length of the frequency.
Huffman algorithm is used to construct a binary tree with a minimum weighted path
length.
Example:
99
CS3401 ALGORITHMS UNIT 3 MEC
n>2
No Yes
n>1 n>3
No Yes No Yes
n=3 n=4
No Yes
n=2 n=3
No Yes
n=1 n=2
The chosen the root to a leaf in a decision tree number represented by the leaf.
I=1
Where, li is the length of the path from the root Pi is probability.
The sum indicates the average number of question needed to guess the chosen number.
Application of Huffman trees:
100
CS3401 ALGORITHMS UNIT 3 MEC
16. Demonstrate divide and conquer approach by Performing quick sort on the following values. 44,
33, 11, 55, 77, 90, 40, 60, 99, 22, 88 Apr/may 2024
QuickSort is a sorting algorithm that follows the divide and conquer strategy. It works as
follows:
1. Divide: Select a pivot element and partition the array such that elements smaller than the
pivot go to the left, and elements larger go to the right.
2. Conquer: Recursively apply QuickSort to the left and right subarrays.
3. Combine: The sorted left and right subarrays are combined (implicitly by recursion).
Given List:
44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88
Step-by-Step Execution
Elements smaller than 88: 44, 33, 11, 55, 77, 40, 60, 22
Pivot: 88
Elements greater than 88: 90, 99
New order: [44, 33, 11, 55, 77, 40, 60, 22] 88 [90, 99]
Step 2: Sorting Left Subarray [44, 33, 11, 55, 77, 40, 60, 22] (Pivot = 22)
Step 3: Sorting [44, 33, 11, 55, 77, 40, 60] (Pivot = 60)
101
CS3401 ALGORITHMS UNIT 3 MEC
[11, 22, 33, 40, 44, 55, 60, 77, 88, 90, 99]
1. Divide: Recursively divide the array into two halves until each sub-array contains a single
element.
2. Conquer: Merge the divided sub-arrays in a sorted manner.
3. Combine: Combine all sub-arrays into one sorted array.
40, 25, 69, 65, 31, 53, 86, 24, 55, 57, 19, 21, 16
We'll start by sorting this set using the Merge Sort algorithm. I'll break down the steps for you.
less
Copy
Left Half: [40, 25, 69, 65, 31, 53, 86]
Right Half: [24, 55, 57, 19, 21, 16]
2. Recursive division of the left half ([40, 25, 69, 65, 31, 53, 86]):
less
Copy
102
CS3401 ALGORITHMS UNIT 3 MEC
Further divide:
less
Copy
Left: [40, 25] Right: [69]
Left: [65, 31] Right: [53, 86]
3. Recursive division of the right half ([24, 55, 57, 19, 21, 16]):
less
Copy
Left: [24, 55] Right: [57, 19]
Left: [21, 16]
4. Merge the sub-arrays in sorted order: After recursively merging the arrays, you'll get
the sorted array.
[16, 19, 21, 24, 25, 31, 40, 53, 55, 57, 65, 69, 86]
103
CS3401 ALGORITHMS UNIT 3 MEC
This consistency in time complexity makes Merge Sort an efficient sorting algorithm, especially
for large data sets.
18. Produce Huffman tree for the following data and encode the data abbcddeef. Apr/May
2024 , Nov/Dec2024
Character Frequency
a 5
b 9
c 12
d 13
e 16
f 45
OR
A character-coding problem. A data file of 100,000 characters contains only the characters
a-f, with the frequencies indicated as below
a b c d ef
Frequency (in thousands) 45 13 12 16 9 5
104
CS3401 ALGORITHMS UNIT 3 MEC
Solution:
Step 1. Build a min heap that contain 6 nodes where each node represents root of a tree with
single node.
Step2 . Extract two minimum frequency nodes from min heap. add a new internal node with
frequency 5+9 =14
Now minheap contains 5 nodes where 4 nodes are roots of trees with single element each , and
one heap is root of tree with 3 elements
character Frequency
c 12
d 13
Internal Node 14
e 16
f 45
Step 3: Extract two minimum frequency nodes from heap .Add a new internal node with
frequency 12+13 =25
Now minheap contains 4 nodes where 2 nodes are roots of trees with single element each,, and
two heap nodes are root of tree with more than one nodes
character Frequency
Internal Node 14
e 16
Internal Node 25
f 45
Step 4. extract two minimum frequency nodes. add a new internal node with frequency 14+16
=30
105
CS3401 ALGORITHMS UNIT 3 MEC
character Frequency
Internal Node 100
Since the heap contains only one node, the algorithm stops here.
Steps to print codes from Huffman tree:
Travers the tree formed starting from the root. maintain an auxiliary arry. While moving to the
left child write 0 to the array. while moving 106
to the child, write 1 to the array.
CS3401 ALGORITHMS UNIT 3 MEC
19. Consider the given set of numbers (65,70,75,80,60,55,40,45) Apply quick sort by using
Step-by-Step Execution:
1. Initial array:
After partitioning:
After partitioning:
After partitioning:
107
CS3401 ALGORITHMS UNIT 3 MEC
After partitioning:
After partitioning:
[75, 80]
Step-by-Step Execution:
1. Initial array:
108
CS3401 ALGORITHMS UNIT 3 MEC
o We move elements smaller than 75 to the left and elements larger than 75 to the
right.
After partitioning:
After partitioning:
After partitioning:
After partitioning:
[45, 55]
109
CS3401 ALGORITHMS UNIT 3 MEC
After partitioning:
[65, 70]
IMPORTANT QUESTIONS
Part A
2. Give the recurrence equation for the worst case behavior of merge sort? Dec 2010
4. Give the time efficiency and drawback of merge sort algorithm? Dec 2005
5. What is the difference between quick sort and merge sort? May 2013
6. Give the control abstraction for divide and conquer. Dec 2012
14. What is the difference between quick sort and merge sort?
PART-B
1. Construct the optimal binary search tree for the following 5 keys with probabilities as
110
CS3401 ALGORITHMS UNIT 3 MEC
indicated.
i 0 1 2 3 4 5
2. Write the Huffman code algorithm and derive its time complexity
3. Generate the Huffman code for the following data comprising of alphabet and their
frequency.(6)
a:1, b :1 ,c :2, d :3, e :5, f: 8,g : 13,h : 21
4. What is divide and conquer strategy and explain the binary search with suitable example
problem.
5. Trace the steps of merge sort algorithm for the elements 122, 25, 70, 175, 89, 90, 95, 102, 123
and also compute its time complexity. Dec 2012
6. Explain merge sort problem using divide and conquer technique example. Apr2010
7. Write a pseudo code using divide and conquer technique for finding the position of the
8. Sort the following set of elements using merge sort :12,2,8,71,4,23, 6, 89, 56 Jun14
9. Distinguish between quick sort and merge sort and arrange the following numbers in
increasing order using merge sort (18, 29,68, 32, 43, 37, 87, 24, 47, 50). Jun13
[Link] the algorithm for Quick Sort and write its time complexity with example list are 5, 3, 1, 9,
8, 2, 4, 7.
April/May 2024
PART A
1. what kind of problem can be solved using divide and conquer method Apr/May 2024 [Link] 22, [Link] 76
2. List the elements of Greedy strategy. Apr/May 2024 [Link] 22, [Link] 75
PART B
1. Demonstrate divide and conquer approach by Performing quick sort on the following values. 44, 33, 11, 55,
77, 90, 40, 60, 99, 22, 88 Apr/may 2024 [Link] 101 [Link] 17
111
CS3401 ALGORITHMS UNIT 3 MEC
3. Explain in detail about Activity-selection problem with an example. Apr/May 2024 Pg .no
88 [Link] 14
a b c d ef
Frequency (in thousands) 45 13 12 16 9 5
Show the steps in constructing the final Huffman tree representing the optimal prefix
code. Apr/May 2024 Pg .no 104 [Link] 19
Nov/Decc 2024
PART- A
[Link] Divide and Conquer approach.([Link] 1)
[Link] the elements of Greedy strategy.([Link] 75)
PART- B
PART- C
1. Consider the given set of numbers (65,70,75,80,60,55,40,45) Apply quick sort by using
112
CS3401 ALGORITHMS UNIT 4 MEC
UNIT IV
STATE SPACE SEARCH ALGORITHMS
PART-A
1. What is knapsack?
The knapsack problem, another well-known NP-hard problem.
The Knapsack problem is, given n items of known weights w1, . . . , wn and values v1, . . . , vn
and a knapsack of weight capacity W, find the most valuable subset of the items that fits
into the knapsack.
2. What are the factors that influence the efficiency of the backtracking algorithm?
8. List down the examples of backtracking. Or what are the applications of backtracking.
They are,
1. The 8 - Queens problem
2. Hamiltonian cycles
3. Sum of Subsets
4. Graph Coloring
5. Knapsack Problem.
13. How can you represent the solution for 2 queen’s problem?
There is no solution for 2 Queen’s problem since however the queens are arranged
both queens would be in same diagonal or column.
14. How can you represent the solution for 8 queen’s problem?
All solutions represented as 8-tuples (x1, x2,…, x8) where xi is the column on which
queen “i” is placed.
Constraints are,
Explicit constraints
Si = {1, 2, 3, 4, 5, 6, 7, 8}
Implicit constraints
No two xi‘s can be the same column or row.
No two queens can be on the same diagonal.
16. Define sum of subsets problem? OR Describe the sum of subsets problem.
May-13,Dec-2018
In the Sum-of-Subsets problem, there are n positive integers (weights) wi and a positive
integer W.
The goal is to find all subsets of the integers that sum to W.
For example, n = 4, w = (11, 13, 24, 7), and m = 31, the desired subsets are
(11, 13, 7) and (24, 7)
The solution vectors can also be represented by the indices of the numbers as
(1, 2, 4) and (3, 4).
All solutions are k-tuples, 1 ≤ k ≤ n
Divide and Conquer: The algorithm repeatedly divides the search interval in half by
comparing the target value to the middle element.
27. State the equation which is used to represent 2 queens are in same diagonal.
Let the diagonals be (i, j) and (k, l)
The two queens lie on the same diagonal if and only if | j - l |=| i – k |
30. Draw a graph with a cycle but no Hamiltonian cycle. (April/May 2011)
A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an
edge (in the graph) from the last vertex to the first vertex of the Hamiltonian Path.
A B
C D
31. Explain briefly branch and bound technique for solving problems. (April/May 2008)
It is an algorithm that enhances the idea of generating a state space tree with the idea of
estimating the best value obtainable from a current node of the decision tree.
It refers to all state space search methods in which all children of an E-node are generated
before any other live node can become the E-node.
32. Define the term live node, E-node and dead node. AU : May -10
Live node: It is a node that has been generated but whose children have not been
generated.
E-node: It is a live node whose children are currently being explored. In other words an E-
node is node currently being explored.
Dead node: It is a generated node that is not to expanded or explored any further. All
children of a death node have already been explored.
34. State the principle of backtracking OR Explain the idea behind the backtracking.
Apr/May 2023
A space state tree is a tree that represents all of the possible states of the problem, from
the root as an initial state to the leaf as a terminal state.
43. What is branch and bound Travelling salesman problem?(Apr/may 2023, 2024)
Given a set of cities and distance between every pair of cities, the problem is to find the
shortest possible tour that visits every city exactly once and returns to the starting point.
The following are possible solutions to the problems: (x,y,z), (x,z,y), (y,x,z), (y,z,x),
(z,x,y) (z,y,x).
Nonetheless, valid solutions to this problem are those that satisfy the constraint
that keeps only (x,y,z) and (z,y,x) in the final solution set.
51. How do you solve a knapsack problem using branch and bound?
LC branch and bound solution for knapsack problem is derived as follows:
a. Derive state space tree.
b. Compute lower bound. ...
c. If lower bound is greater than upper bound than kill that node.
d. Else select node with minimum lower bound as E-node.
e. Repeat step 3 and 4 until all nodes are examined.
[Link] the time complexity for solving n-Queens problem. (Nov/Dec 2024)
The time complexity for solving the n-Queens problem depends on the algorithm used. One of
the most common approaches is using backtracking, which explores possible configurations of
queens on the board and backtracks whenever an invalid configuration is encountered.
PART-B
1. What is Backtracking problem? Or With an example explain general method solving problem
using backtracking Or Explain elaborately recursive backtracking algorithm Au: Dec-11,
May-13Or Explain the general method of backtracking Or How do you estimate the efficiency
of backtracking? Au: dec-13 Apr/May 2024
Introduction
Backtracking and Branch and bound are two algorithm design techniques for solving problems
in which the number of choices grows atleast exponentially with their instances [Link]
techniques construct a solution one component at a time, trying to terminate the process as soon
as one can ascentain that no solution can be obtained as a result of the choices already made.
This approach makes it possible to solve many large instances of NP hard problems in an
acceptable amount of time.
The techniques branch and bound and backtracking are base on the construction of a state space
tree.
A state space tree is a rooted tree whose nodes represent partially constructed solutions to the
problems.
Both techniques terminate a node as soon as it can be guaranteed that no solution to the problem
can be obtained by considering choices that correspond to the node’s descendants.
Difference between Branch and bound and Backtracking
The techniques differ in the nature of problems they can apply to. Branch and bound is
applicable only to optimization problems. Backtracking is applied to non optimization
problems.
The other difference between backtracking and branch and bound lies in the order in which
nodes of the state space tree are generated.
In backtracking technique, the state space tree is developed using depth first which is similar to
DFS.
In branch and bound the nodes of a state space tree is generated using best first rule.
Backtracking
Backtracking is a more intelligent variation of this approach.
The principal idea is to construct solutions one component at a time and evaluate such partially
constructed candidates as follows.
If a partially constructed solution can be developed further without violating the problem’s
constraints, it is done by taking the first remaining legitimate option for the next component. If
there is no legitimate option for the next component, no alternatives for any remaining
component need to be considered. In this case, the algorithm backtracks to replace the last
component of the partially constructed solution with its next option.
It is convenient to implement this kind of processing by constructing a tree of choices being
made, called the state-space tree.
Its root represents an initial state before the search for a solution [Link] nodes of the
first level in the tree represent the choices made for the first component of a solution; the
nodes of the second level represent the choices for the second component, and so on.
1 2 3 4
1 Q
2 Q
3
4
Step 4This proves to be a dead end because there is no acceptable position for queen 3. So, the
algorithm backtracks and puts queen 2 in the next possible position at (2, 4).
1 2 3 4
1 Q
2 Q
3
4
Step 5Now queen 3 is placed at position (3,2), which is acceptable position. Now the
chessboard is
1 2 3 4
1 Q
2 Q
3 Q
4
Step 6Then queen 3 is placed at (3, 2), which proves to be another dead end. The algorithm then
backtracks all the way to queen 1 and moves the queen 1 from (1,1) to (1, 2).
1 2 3 4
1 Q
2
3
4
Step 8Now queen 3 is placed at the position (3, 1), which is acceptable position. Now the board
becomes
1 2 3 4
1 Q
2 Q
3 Q
4
Step 9Finally the queen 4 to (4, 3), which is a solution to the problem, which is e required
solution to the problem. Now the board for four queens is
1 2 3 4
1 Q
2 Q
3 Q
4 Q
The state-space tree of this search is shown in Figure. If other solutions need to be found (how
many of them are there for the four queens problem?), the algorithm can simply resume its
operations at the leaf at which it stopped. Alternatively, we can use the board’s symmetry for
this purpose.
Finally, it should be pointed out that a single solution to the n-queens problem for any n ≥ 4 can
be found in linear time. In fact, over the last 150 years mathematicians have discovered several
alternative formulas for non attacking positions of n queens. Such positions can also be found
by applying some general algorithm design strategies.
3. Write down and explain the procedure for tackling the 8 queens problem using backtracking
Approach or Describe the Backtracking solution to solve 8-Queen problem. Apr/May 2017
8 Queens problem
The is to successfully place 8 queens on a 8 × 8 chess board such that no two queens attack each
other. Two queens are said to be in the attack state if they are.
1. Placed in the same row
2. Placed in the same column
3. Placed along the same diagonal
Initially when 8 queens have to be placed on the (8 × 8) chess board,
si = { 1,2,3,4,5,6,7,8} ie. xi should have any of these positions.
1st queen position x1 can have any of these 8 values.
2nd queen position x2 can have any of these 8 values.
:
8th queen position x8 can have any of these 8 values.
The solution space will have 8 tuples. When these 88 tuples are bound by the implicit conditions (
ie) the xi , s should be related such that they cannot have the same value since no two queens are
allowed to be placed on the same row or column , or along the same diagonal, and hence the
solution tuple can only be a permutation of si { 1,2,…8}. Hence the solution space reduces to 8!
From 88
We have test whether two queens are on the same diagonal, it must satisfy the following
conditions.
• The chessboard squares being numbered as the indices of the two-
dimensional array a[1:8,1:8]
• Every element on the same diagonal that runs from the upper left to the
lower right has the same row-column value.
8-Queens problem
Explanation:
• Place(k, i) returns a Boolean value that is true if the kth queen can be placed
in column i. it tests both whether i is distinct from all previous values
x[1],…..x[k-1] and whether there is no other queen on the same diagonal.
• Its computing time is O(k-1)
All solutions to the n-queens problem:
Algorithm Place(k,i)
// This algorithm returns true if a queen can be placed in kth row and ith column. Otherwise, it
returns false.
// x[] is a global array whose first(k-1) values have been set.
// Abs(r) returns the absolute value of r.
{
for j = 1 to k-1 do
if ((x[j] = i) // Checks whether two Queens are in the same column
or (Abs(x[j] - i) = Abs(j - k))) // Checks whether they are in the same diagonal
then
return false;
return true;
}
Algorithm NQueens(k, n)
// Using backtracking, this procedure prints all
//possible placements of n queens on an n x n
// chessboard so that they are non attacking.
{
for i:=1 to n do
{
if Place(k, i) then
{
x[k]:=i;
if (k==n) then write (x[1:n]);
else NQueens(k+1, n);
}} }
4. Using backtracking enumerate how can you solve the following problem Hamiltonian
Circuit Problem Au: Dec-10 , 08,09,11,May-14, (APR/MAY 2023)
Definition
Given an undirected connected graph and two graph and two nodes x and y then find a path
from x to y visiting each node in the graph exactly once
V1, V2…… Vn and the Vi are distinct except for V1, and Vn+1, which are equal.
The next example let us consider the problem of finding a Hamiltonian circuit in the graph in
Figure 4.2.
Figure 4.2
Without loss of generality, we can assume that if a Hamiltonian circuit exists, it starts at vertex
a. Accordingly, we make vertex a the root of the state-space tree.
If solution exist for a Hamiltonian circuit problem, the first component of our future solution, if
it exists, is a first intermediate vertex of a Hamiltonian circuit to be constructed.
Using the alphabet order to break the three-way tie among the vertices adjacent to a, we select
vertex b. From b, the algorithm proceeds to c, then to d, then to e, and finally to f, which proves
to be a dead end.
So the algorithm backtracks from f to e, then to d, and then to c, which provides the first
alternative for the algorithm to pursue.
Going from c to e eventually proves useless, and the algorithm has to backtrack from e to c and
then to b as shown in FIGURE 4.3
From there, it goes to the vertices f , e, c, and d, from which it can legitimately return to a,
yielding the Hamiltonian circuit a, b, f , e, c, d, a. Hence the solution is obtained. If we wanted
to find another Hamiltonian circuit, we could continue this process by backtracking from the
leaf of the solution found.
FIGURE 4.3 State-space tree for finding a Hamiltonian circuit. The numbers above the
nodes of the tree indicate the order in which the nodes are generated.
Example 2:Definition
Given an undirected connected graph and two graph and two nodes x and y then find a path
from x to y visiting each node in the graph exactly once
Then the Hamiltonian cycle A-B-D-E-C-F-A. this problem can be solved using backtracking
approach. The state space tree is generated in order to find all the
Hamiltonian cycle in the graph as shown in Fig4.4 (a).
Only distinct cycles are output of this algorithm. The Hamiltonian cycle can be identified as
follows fig 4.4 (b).
fig 4.4 (b) clearly the backtrack approach is adopted. For instance A-B –D- F- C- E; here we get
stuck. For returning to A we have to revisit atleast one vertex.
Hence we backtracked and from D node another path is chosen A- B- D- E-C-F-A which is
Hamiltonian cycle.
[Link] Subset-Sum Problem and discuss the possible solution strategies using backtracking
or write an algorithm for subset sum and explain with an example.(13.m) Aprl/May 2019
The subset sum problem is used to find a subset of a given set. A = {a1, . . . , an} of n positive
integers whose sum is equal to a given positive integer d. It always convenient to sort the sets
elements in ascending order. That is,
A1 ≤ A2 ≤ ….≤An
Let us first write a general algorithm for sum of subset problem
Algorithm:
Let , S be a set of elements and d is the expected sum of subset. Then
Step 1: start with an empty set
Step 2: add to the subset, the next element from the list
Step 3: if the subset is having sum d then stop with the subset as solution.
Step 4: if the subset is not feasible or if we have reached the end of the set then
Backtrack through the subset until we find the most suitable value.
Step 5: if the subset is feasible then repeat step 2
Step 6: if we have visited all the elements without finding a suitable subset and if no
backtracking is possible then stop without solution as shown in Table 4.1
For example 1, for A = {1, 2, 5, 6, 8} and d = 9, there are two solutions: They are,
Solution :
Table 4.1 subset
Initially subset = {} Sum = 0
Now add the next
1 1 element
Before finding the subset of a given set, the set’s elements are sorted in increasing order. So,
we will assume that
a1≤a2 ≤ . . . ≤ an.
For subset sun problem, the state space tree is constructed as a binary tree which is
shown in the figure 4.6 below.
Example 2:
A = {3, 5, 6, 7} and d = 15
A = {3, 5, 6, 7} and d = 15
The state-space tree can be constructed as a binary tree like that in Figure 4.7 for the
instance A = {3, 5, 6, 7} and d = 15.
The root of the tree represents the starting point, with no decisions about the given
elements made as yet.
Its left and right children represent, respectively, inclusion and exclusion of a1 in a set
being sought. Similarly, going to the left from a node of the first level corresponds to
inclusion of a2 while going to the right corresponds to its exclusion, and so on.
Thus, a path from the root to a node on the ith level of the tree indicates which of the
first i numbers have been included in the subsets represented by that node. We record the value
of s, the sum of these numbers, in the node.
If s is equal to d, we have a solution to the [Link] can either report this result and
stop or, if all the solutions need to be found, continue by backtracking to the node’s
parent as shown in Table 4.2
If s is not equal to d, we can terminate the node as nonpromising if either of the
following two inequalities holds:
s + ai+1> d (the sum s is too large),
Figure 4.7 Complete state-space tree of the backtracking algorithm applied to the instance A =
{3, 5, 6, 7} and d = 15 of the subset-sum problem.
The number inside a node is the sum of the elements already included in the subsets represented
by the node.
[Link] an algorithm to determine the sum of subsets for a given sum and a set of numbers .
draw the tree representation to solve the subset sum problem given the numbers set as
A = {3, 5, 6, 7 , 2} and with sum = 15 Derive all the subsets Au : Dec -10
solution
The inequality below a leaf indicates the reason for its termination.
A = {3, 5, 6, 7 , 2} and sum = 15
The state-space tree can be constructed as a binary tree like that in Figure 4.8 for
the instance A = {3, 5, 6, 7 , 2} and sum = 15.
Figure 4.8 sum of subsets for a given sum and a set of numbers
Example 4.
Let, w = { 5,7,10,12,15,18,20} and m = 35. Find all possible subset of w whose sum is
equivalent to m. draw the portion of state space tree for this problem. Au : Dec – 12
Solution:
Table 4.4 all possible subset
Depending on the problem, all solution tuples can be of the same length (the n-queens and the
Hamiltonian circuit problem) and of different lengths (the subset-sum problem).
A backtracking algorithm generates, explicitly or implicitly, a state-space tree; its nodes
represent partially constructed tuples with the first i coordinates defined by the earlier actions
of the algorithm.
If such a tuple (x1, x2, . . . , xi) is not a solution, the algorithm finds the next element in Si+1 that
is consistent with the values of (x1, x2, . . . , xi) and the problem’s constraints, and adds it to the
tuple as its (i + 1)st coordinate.
If such an element does not exist, the algorithm backtracks to consider the next value of
xi, and so on. To start a backtracking algorithm, the following pseudocode can be called for i =
0 ; X[1..0] represents the empty tuple.
ALGORITHM Backtrack(X[1..i])
//Gives a template of a generic backtracking algorithm
//Input: X[1..i] specifies first i promising components of a solution
//Output: All the tuples representing the problem’s solutions
if X[1..i] is a solution
write X[1..i]
else //see Problem 9 in this section’s exercises
for each element x ∈ Si+1 consistent with X[1..i] and the constraints do
X[i + 1]←x
Backtrack(X[1..i + 1])
Several tricks that might help reduce the size of a state-space tree
1. One is to exploit the symmetry often present in combinatorial problems.
For example, the board of the n-queens problem has several symmetries so that some
solutions can be obtained from others by reflection or rotation.
2. Another trick is to preassign values to one or more components of a solution, as we did
in the Hamiltonian circuit example.
[Link] the Assignment Problem by the branch and bound algorithm with an example or Find
Optimal solution using Branch and Bound for the following assignment problem.
Nov/Dec 2017
We have to find a lower bound on the cost of an optimal selection without actually solving
the problem.
We can do this by several methods. For example, it is clear that the cost of any
solution, including an optimal one, cannot be smaller than the sum of the smallest elements in
Each of the matrix’s rows. For the instance here, this sum is 2 + 3+ 1+ 4 = 10.
It is important to stressthat this is not the cost of any legitimate selection (3 and 1 came from
the same column of thematrix); it is just a lower bound on the cost of any legitimate selection.
We can and will apply thesame thinking to partially constructed solutions. For example, for a
ny legitimate selection thatselects 9 from the first row, the lower bound will be 9 + 3 + 1+ 4 = 17.
It is sensible to consider a node with the best bound as most promising, although this does
not, of course, preclude the possibility that an optimal solution will ultimately belong to a differen
tbranch of the state-space tree.
This variation of the strategy is called the best-first branch-and-bound.
The lower-bound value for the root, denoted lb, is 10. The nodes on the first level of the tree
correspond to selections of an element in the first row of the matrix, i.e., a job for person a as
shown in Figure 4.10
FIGURE 4.10 Levels 0 and 1 of the state-space tree for the instance of the assignment problem
being solved with the best-first branch-and-bound algorithm. The number above a node shows the
order in which the node was generated. A node’s fields indicate the job number assigned to person
a and the lower bound value, lb, for this node.
FIGURE 4.11 Levels 0, 1, and 2 of the state-space tree for the instance of the assignment problem
being solved with the best-first branch-and-bound algorithm.
Of the six live leaves—nodes 1, 3, 4, 5, 6, and 7—that may contain an optimal solution, we again
choose the one with the smallest lower bound, node 5.
First, we consider selecting the thirdcolumn’s element from c’s row (i.e., assigning person c to job 3)
; this leaves us with no choice but
to select the element from the fourth column of d’s row (assigning person d to job 4). This yields
leaf 8 (Figure 4.12), which corresponds to the feasible solution {a→2, b→1, c→3, d →4} with the
total cost of 13. Its sibling, node 9, corresponds to the feasible solution {a→2, b→1, c→4, d →3}
with the total cost of 25.
Since its cost is larger than the cost of the solution represented by leaf 8,
node 9 is simply terminated. (Of course, if its cost were smaller than 13, we would have to replace
the information about the best solution seen so far with the data provided by this node.)
FIGURE 4.12 Complete state-space tree for the instance of the assignment problem solved with
the best-first branch-and-bound algorithm.
Now, as we inspect each of the live leaves of the last state-space tree—nodes 1, 3, 4, 6, and
7 in Figure 4.12—we discover that their lower-bound values are not smaller than 13, the value of
the best selection seen so far (leaf 8). Hence, we terminate all of them and recognize the solution
represented by leaf 8 as the optimal solution to the problem.
8. Solve the following instance of the knapsack problem by the branch and bound
AU: Dec-06,08,10(APR/MAY 2023)
Knapsack Problem
The branch-and-bound technique is used to solving the knapsack problem.
The Knapsack problem is given n items of known weights wi and values vi , i = 1, 2, . . . , n, and
a knapsack of capacity W, find the most valuable subset of the items that fit in the knapsack.
It is convenient to order the items of a given instance in descending order by their value-to-
weight ratios.
Then the first item gives the best payoff per weight unit and the last one gives the worst payoff
per weight unit, with ties resolved arbitrarily:
v1/w1 ≥ v2/w2 ≥ . . . ≥ vn/wn.
Each node on the ith level of this tree, 0 ≤ i ≤ n, represents all the subsets of n items that include
a particular selection made from the first i ordered items.
This particular selection is uniquely determined by the path from the root to the node.
A branch going to the left indicates the inclusion of the next itemA branch going to the
right indicates its exclusion.
We record the total weight w and the total value v of this selection in the node, along with some
upper bound ub on the value of any subset that can be obtained by adding zero or more items to
this selection.
A simple way to compute the upper bound ub is to add to v, the total value of the items already
selected, the product of the remaining capacity of the knapsack W − w and the best per unit
payoff among the remaining items, which is vi+1/wi+1:
ub = v + (W − w)(vi+1/wi+1)
We will first compute the upper bond by using above given formula
ub = v + (W − w)(vi+1/wi+1)
v = 40 + 25 = 65
w = 4 +5 = 9
The capacity W = 10
The next item would be vi +1/ w i+1 -> item 4
Therefore v4/w4 = 12/3 =4
ub = v + (W − w)(vi+1/wi+1)
= 65 +(10-9)*4
= 65 + 1 *4 ub =69
Computation at node VI
At node VI is an instant at which item 1 is selected , item 2 and item 3 are not selected .
Therefore v= 40 , w = 4
The capacity W = 10
The Next item being selected is item 4
Now vi +1/ w i+1 = v4/w4= 12/3 =4
i.e v4/w4 = 4
ub = v + (W − w)(vi+1/wi+1)
=4 0 +(10-4)*4
= 40 + 6 *4 ub =64
Computation at node VII
At node VII , we consider selection of item 1, item 3, item 4. There is no next item given
problem statement
vi +1/ w i+1=0
w = 4 + 5+ 3 = 12 -> but this is exceeding capacity W = 10
v = 40 + 25 + 12 = 72
W = 10
ub = v + (W − w)(vi+1/wi+1)
= 72 + (10 -12)* 0 ub = 72
But as weight of selected items exceed the capacity W this is not a feasible solution.
Computation at node VIII
At node VIII , we consider selection of item 1and item [Link] is no next item given problem
statement
vi +1/ w i+1=0
w = 4 + 5= 9 -> but this is exceeding capacity W = 10
v = 40 + 25 = 65
W = 10
ub = v + (W − w)(vi+1/wi+1)
= 65 + (10 -9)* 0 ub = 65
The node IX is a node indicating maximum profit of selected items with maximum weight of
item = 9 i.e . <capacity of knapsack ( W=10) as shown in fig 4.13
Thus solution is pick up { item 1, item3 } and gain maximum profit 65$
Fig 4.13 :State-space tree of the best-first branch-and-bound algorithm for the
instance of the knapsack problem.
9. Explain how to solve TSP (Traveling Salesman Problem) using branch and bound Au:Dec -13
Apr/May 2017 Apr-18
Problem statement
The branch-and-bound technique is applied to the instances of the traveling salesman problem. If
there are n cities and cost of travelling from any city to any other city is given then we have to
obtain the cheapest round –trip such that each city is visited exactly once and then returning to
starting city , completes the tour Typically travelling salesman problem is represented by
weighted graph
In this method we consider computing of lower bounds. The lower bound is denoted by LB and
can be obtained using following formula
LB= ⅀v€V ( sum of costs of the two least cost edges adjacent to v)/ 2 or
lb = [s/2]
This method can be well understood with the help of some examples
Consider following graph for solving TSP
Consider node 1 : it says that consider distance a-b in computation of the corresponding
vertices along with one minimum distance.
a= (a-b) + (a-c) = 3 + 1
b = ( a-b) + ( b-c) = 3+ 6
c = ( a-c) + (c-e) = 1+2 -> cannot consider ( a-b) because an edges (a-b) is not adjacent
to c
d = ( d-e) + ( c-d) = 3 +4 -> can not consider (a-b)
e = ( c-e) + ( d-e) = 2 +3 -> can not consider (a-b)
lb =[[(3+ 1) + (3 + 6) + (1+ 2) + (3 + 4) + (2 + 3)]/2]
lb = 28/2lb = 14. Is for node 1.
Consider node 2 : it says that consider distance a-c in computation of the corresponding
vertices along with one minimum distance.
a= (a-b) + (a-c) = 3 + 1
b = ( a-b) + ( b-c) = 3+ 6 -> cannot consider( a-c) because an edges (a-c)
is not adjacent to b
c = ( a-c) + (c-e) = 1+2
d = ( d-e) + ( c-d) = 3 +4 -> can not consider (a-c) here
e = ( c-e) + ( d-e)= 2 +3 -> can not consider (a-c)
To reduce the amount of potential work, two factors are considered. They
1. Without loss of generality, we can consider only tours that start at a.
2. Second, because our graph is undirected, we can generate only tours in which b is visited before
c.
In addition, after visiting n − 1= 4 cities, a tour has no choice but to visit the remaining unvisited city
and return to the starting one. The state-space tree tracing the algorithm’s application is given in Figure
12.9b.
The state space tree of graph in figure for branch and bound technique is shown in figure.
Weakness
Using branch and bound technique, it is impossible to predict which instances will be solvable in a
realistic amount of time and which will not.
Approximation algorithms for np hard problemsApproximation algorithms are often used to find
approximation solutions to difficult problems of combinatorial optimization
The optimization versions of difficult combinational problems such as the traveling salesman problem
and the knapsack problem.
NP-hard problems are problems that are at least as hard as NP-complete problems.
For NP hard problems there is no known polynomial time algorithms.
The notation of an NP hard problem can be defined more formally by extending the notation of
polynomial reducibility to problems that are not necessary in class NP, including optimization
problems.
Many of the approximation algorithms are greedy algorithm based on some problem-specific heuristic.
A heuristic is a common-sense rule drawn from experience rather than from a mathematically proved
assertion.
For example, going to the nearest unvisited city in the traveling salesman problem is a good
illustration of this notion.
Accuracy
The accuracy of an approximate solution sa to a problem of minimizing some function f by the size of
the relative error of this approximation,
re (sa) =
Where S* is an exact solution to the problem.
10. The knight is placed on the first block of an empty board and moving according to the
rules of chess, must visit each square exactly once.
The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies
the constraints.
while there are untried tours
{
generate the next tour
if this tour covers all squares
{
print this path;
}
It it is possible to color all the vertices with the given colors then we have to output the
colored result, otherwise output ‘no solution possible’.
The least possible value of ‘m’ required to color the graph successfully is known as
the chromatic number of the given graph.
Graph Coloring Solution
Using Backtracking Algorithm
The backtracking algorithm makes the process efficient by avoiding many bad decisions made
in naïve approaches.
In this approach, we color a single vertex and then move to its adjacent (connected) vertex to
color it with different color as shown in fig 4.14
After coloring, we again move to another adjacent vertex that is uncolored and repeat the
process until all vertices of the given graph are colored.
In case, we find a vertex that has all adjacent vertices colored and no color is left to
make it color different, we backtrack and change the color of the last colored vertices
and again proceed further.
If by backtracking, we come back to the same vertex from where we started and all
colors were tried on it, then it means the given number of colors (i.e. ‘m’) is insufficient
to color the given graph and we require more colors (i.e. a bigger chromatic number).
The m-colorability optimization problem asks for the smallest integer m for which the
graph G can be colored. This integer is referred to as the chromatic number of the
graph.
For example, the graph of Figure 4.15 can be colored with three colors 1, 2, and 3. The
color of each node is indicated next to it. It can also be seen that three colors are needed to
color this graph and hence this graph's chromatic number is 3.
This problem asks the following question: given any map, can the regions be
colored in such a way that no two adjacent regions have the same color yet only
four colors are needed?
This turns out to be a problem for which graphs are very useful, because a map can
easily be transformed into a graph. Each region of the map becomes a node, and if
two regions are adjacent, then the corresponding nodes are joined by an edge.
Figure 4 . 1 5 shows a map with five regions and its corresponding graph. This
map requires four colors. For many years it was known that five colors were
sufficient to color any map, but no map that required more than four colors had
ever been found.
After several hundred years, this problem was solved by a group of mathematicians
with the help of a computer. They showed that in fact four colors are sufficient. In
this section we consider not only graphs that are produced from maps but all
graphs.
We are interested in determining all the different ways in which a given graph can
be colored using at most m colors.
The underlying state space tree used is a tree of degree m and height
n + l. Each node at level i has m children corresponding to the m
possible assignments to Xi, 1 ::; i ::; n. Nodes at level n + l are leaf
nodes.
Figure 4.17 shows the state space tree when n =3 and m = 3.
Function mColoring is begun by first assigning the graph to its adja- cency matrix,
setting the array x[] to zero, and then invoking the statement m Coloring(l);.
Notice the similarity between this algorithm and the general form of the recursive
backtracking schema of Algorithm 7.1. Function NextValue (Algo- rithm 7.8)
produces the possible colors for xk after x1 through Xk-l have been defined.
The main loop of mColoring repeatedly picks an element from the set of
possibilities, assigns it to xk, and then calls mColoring recursively.
For instance, Figure 4.17 shows a simple graph containing four nodes. Below that is
the tree that is generated by mColoring.
Each path to a leaf repre- sents a coloring using at most three colors. Note that
only 12 solutions exist with exactly three colors.
An upper bound on the computing time of mColoring can be arrived at by noticing that
the number of internal nodes in the state space tree is :
At each internal node, O(mn) time is spent by NextValue to determine the children
corresponding to legal colorings.
Hence the total time is bounded by :
Branch-and-Bound
The term branch-and-bound refers to all state space search methods
in which all children of the E-node are generated before any other
live node can become the E-node.
We have already seen two graph search strategies, BFS and D-
search, in which the exploration of a new node cannot begin until
the node currently being explored is fully explored.
Both of these generalize to branch-and- bound strategies. In branch-
and- bound terminology, a BFS-like state space search will be called
FIFO (First In First Out) search as the list of live nodes is a first-
in-first-out list (or queue).
A D-search-like state space search will
be called LIFO (Last In First Out) search as the list of live nodes
is a last-in-first-out list (or stack).
As in the case of backtracking,
bounding functions are used to help avoid the generation of
subtrees that do not contain an answer node.
Following this move, other moves can be made. Each move creates a new
arrangement of the tiles. These arrangements are called the states of the
puzzle. The initial and goal arrangements are called the initial and goal states.
A state is reachable from the initial state iff there is a sequence of legal
moves from the initial state to this state.
The state space of an initial state consists of all states that can be reached
from the initial state. The most straightforward way to solve the puzzle would
be to search the state space for the goal state and use the path from the
initial state to the goal state as the answer.
It is easy to see that there are 16! (16! :::::: 20.9 x 1012) different arrangements
of the tiles on the frame. Of these only one-half are reachable from any given
initial state. Indeed, the state space for the problem is very large.
Before attempting to search this state space for the goal state, it would be
worthwhile to determine whether the goal state is reachable from the initial
state. There is a very simple way to do this.
Let us number the frame positions 1 to 16. Position i is the frame position containing
tile numbered i in the goal arrangement of Figure 4.18(b). Position 16 is the empty
spot. Let position(i) be the position number in the initial state of the tile numbered i.
Then position(16) will denote the position of the empty spot.
For any state let [Link]( i) be the number of tiles j such that j < i and position(j) >
position(i).
For the state of Figure 4.18 (a) we have, for exam- ple, less(l) = 0, less(4) = 1, and
less(12) = 6.
Let x =1 if in the initial state the empty spot is at one of the shaded positions of
Figure 4.18 (c) and x = 0 if it is at one of the remaining positions. Then, we have the
following theorem:
Theorem 8.1 The goal state of Figure 4 . 1 8 (b) is reachable from the initial state iff :
A depth first state space tree generation will result in the subtree of Figure 8.4
when the next moves are attempted in the order: move the empty space up, right,
down, and left. Successive board configurations reveal that each move gets us
farther from the goal rather than closer.
The search of the state space tree is blind. It will take the leftmost path from the root
regardless of the starting configuration. As a result, an answer node may never be
found ( unless the leftmost path ends in such a node).
In a FIFO search of the tree of Figure 4 . 2 0 , the nodes will be generated in the order
numbered.
A breadth first search will always find a goal node nearest to the root.
However, such a search is also blind in the sense that no matter what the initial
configuration, the algorithm attempts to make the same sequence of moves.
A FIFO search always generates the state space tree by levels
For example, let G = (V, E) where V = 1, 2, 3, 4 and {E = (1, 2),} (2, 3), (2, 4),
{ (3, 4) and suppose that k}=
3. A valid coloring c of G is: c(1) = R, c(2) =
G, c(3) = B, c(4) = R.
Potential solutions
Suppose that V=N Then (c1, c2, ..., cn) is a possible coloring of G where ci is the
color of node i in G. Note that there are kn possible colorings. A coloring is feasible
or validif no two adjacent nodes are given the same color, that is, if (i, j) ∈ E then ci
ƒ= c j .
Consider a graph G = (V, E) where V = {1, 2, 3, 4 }
and E = {( 1, 2), (1, 3),(2, 3), (2, 4), (3, 4)}
and let k = 3. There are six valid colorings of G given in the
following T able 4.4:
node p q r s t u
1 R R G G B B
2 G B B R R G
3 B G R B G R
4 R R G G B B
Note that all these colorings are sort of equivalent. They all share the following
structure:
• The same color is used for both node 1 and node 4. For colorings p and
q, it is R, for colorings r and s, it is G, and for colorings t and u, it is
B.
• Nodes 2 and 3 must have distinct colors different from each other and
from the color used for nodes 1 and 4.
Definition Two colorings are equivalent if one can be transformed into another by permuting
the k colors.
We will use the following strategy to find all valid colorings of a graph
G = (V, E):
Step 1: Choose a color for node 1. It can be one of: R, B or G. Say we choose R.
Step 2: Given partial coloring (R), we choose a color for node 2. It can be one of: G or B.
Say we choose G.
Step 3: Given partial coloring (R, G), we choose a color for node 3. It cannot be either R or
G, so it must be B since k = 3.
Step 4: Given partial coloring (R, G, B), we choose a color for node 4. It cannot be B or G,
so it must be R. This gives the coloring (R, G, B, R) which is coloring p.
We have no more choices of colors in step 4, and in step 3. We have one choice in step
2.
Step 5:Given partial coloring (R), we choose a different color for node [Link] choose B for node 2.
Step 6: Given partial coloring (R, B), we choose a color for node 3. It cannot be R nor B, so
it must be G.
Step 7: Given partial coloring (R, B, G), we choose a color for node 4. It cannot be B or G,
so it must be R. This gives the coloring (R, B, G, R) which is coloring q.
We have no more choices of colors in steps 4, 3 and 2. We go back to step 1.
Step 8: We choose a different color for node 1, say B. This will produce a branch in the
tree equivalent to the first branch where R and B are switched. Thus we will get the
colorings t and u.
If we choose G for node 1 then, we will again get a branch equivalent to the first one
with R and G swapped. This will produce the colorings r and s.
Algorithm
We now give a recursive version of the graph coloring algorithm. Let C[1...j−
1] be a partial coloring for the first j − 1 nodes.
Color(C,j,k,n)
if j = n+1 then
output C
return or
quit
for i = 1 to k
C[j] = i
if valid(C,j,n)
then
Color(C,j+1,k,n
)
where
Valid(C,j,n)
for all neighbors v of j with v <
j if C[v] = C[j] then
return false
return true
Pruning
If we are simply looking for a single solution, we can cut off the equivalent
branches of the tree to save time. For example, the three main branches of the
backtracking tree obtained in section 4.2 all gave equivalent solutions. We
need only consider the first branch if we want a single solution.
The following algorithm prunes the tree to remove equivalent branches. It
uses the following strategy:
ColorP(C,j,last,k,n)
if j = n+1 then
output C
return or quit
for i = 1 to last //try old colors first
C[j] = i
if valid(C,j,n) then
ColorP(C,j+1,last,k,n)
if last < k then
C[j] = last + 1
ColorP(C,j+1,last+1,k,n)
Step 4: Solution
Other possible solutions can be found by exploring different paths, but this is one correct subset.
14. Explain the branching mechanism in the Branch and Bound Strategy to solve 0/1
Knapsack problem. Apr/May 2024
Introduction
Branch and Bound (B&B) is an exhaustive search technique that efficiently finds the optimal
solution by systematically exploring and pruning branches in a search tree.
Each node in the tree represents a partial solution, with the following:
Example of Branching
Weight = 0, Value = 0.
Compute an upper bound (greedy estimation).
Branch into two cases:
o Left child: Include item 1.
o Right child: Exclude item 1.
Weight = 0, Value = 0.
Branch again:
o Left child: Include item 2.
o Right child: Exclude item 2.
Calculate an upper bound on the best possible solution from each node.
Prune (cut off) nodes where the bound is lower than the best solution found so far.
If the bound of a node is less than the current best solution, we prune (discard) the branch.
Conclusion
The branching mechanism systematically explores choices, while the bounding function
prevents unnecessary searches, making the Branch and Bound approach more efficient than
brute force for solving the 0/1 Knapsack problem.
[Link] the following graph. The vertex represents the city and edge represents the cost
between the two vertices. A salesman starts from node1, visit all the cities exactly once and
return to the starting node. Justify that the algorithm that uses optimality principle produces an
optimal tour cost to visit all [Link]/Dec 2024
The graph provided illustrates a problem related to the Traveling Salesman Problem (TSP),
where a salesman must visit all cities (vertices) exactly once and return to the starting point,
minimizing the total cost (edge weights).
An algorithm that follows the optimality principle (e.g., dynamic programming with Bellman-
Held-Karp or greedy heuristics) assumes that optimal solutions to sub-problems lead to an
optimal solution for the entire problem.
Justification
16. Apply backtracking approach and determine whether the given graph can be colored using
4 colors with graph colouring techniques. Nov/Dec 2024
1. Input Representation:
o Represent the graph as an adjacency matrix or adjacency list.
o Each vertex has an index, and edges represent adjacency (connections) between
vertices.
2. Assign Colors:
o Attempt to assign one of 4 colors (e.g., 1, 2, 3, 4) to each vertex.
o Start with vertex 1 and assign a color.
o Move to the next vertex and assign a color that is not used by any of its adjacent
vertices.
3. Backtracking:
o If a vertex cannot be assigned any of the 4 colors due to adjacent vertices already
using them, backtrack to the previous vertex and try a different color.
o Continue this process until all vertices are successfully colored or it is
determined that 4 colors are insufficient.
4. Termination:
o If all vertices are colored, the graph is 4-colorable.
o If not, then 4 colors are insufficient.
We can visualize that the graph has 12 vertices connected by edges. To solve it using
backtracking, we need to:
1. Construct the Adjacency Matrix: Based on the image, create a matrix where:
o A[i][j]=1A[i][j] = 1A[i][j]=1 if there is an edge between vertex iii and vertex jjj,
o A[i][j]=0A[i][j] = 0A[i][j]=0 otherwise.
2. Use Backtracking Algorithm:
o Start with vertex 1, assign a color.
o Move sequentially through vertices, checking constraints.
o Backtrack if needed.
9. Let, w = { 5,7,10,12,15,18,20} and m = 35. Find all possible subset of w whose sum is equivalent
to m. draw the portion of state space tree for this problem. Au : Dec – 12
[Link] the following instance of the knapsack problem by the branch and boundAU: Dec-06,08,10
11. Explain how to solve TSP(Traveling Salesman Problem) using branch and bound Au : Dec –
Aprl/May 2024
UNIT-4
PART A
1. Define Hamiltonian circuit problem. [Link] 4 [Link] 26
2. What is branch and bound Travelling salesman problem?(Apr/may 2023, 2024) [Link] 7 [Link] 43
PART B
1. Write an algorithm for N Queen Problem-Queens Problem or elaborate how backtracking
technique can be used to solve n-queue problem. Explain with an example. Au :Nov/Dec 2019
Apr/may 2024 [Link] 10 [Link] 1
2. Solve the following subset sum problem using back tracking. Let S = \{3, 7, 9, 13, 26, 41\} d(sum) =
51 Apr/May 2024 [Link] 52 [Link] 13
3. Discuss briefly about the general method of branch and Bound approach and state how it differs
from backtracking. Apr/May 2024 [Link] 10 [Link] 1
14. Explain the branching mechanism in the Branch and Bound Strategy to solve 0/1 Knapsack
problem. Apr/May 2024 [Link] 54 [Link] 14
Nov/Dec 2024
PART-A
1. Write the time complexity for solving n-Queens problem. [Link] 53
2. Define optimal binary search. [Link] 20
PART-B
1. Apply backtracking approach and determine whether the given graph can be colored using 4
colors with graph colouring techniques. [Link] 16
2. Consider the following graph. The vertex represents the city and edge represents the cost
between the two vertices. A salesman starts from node1, visit all the cities exactly once and return
to the starting node. Justify that the algorithm that uses optimality principle produces an optimal
tour cost to visit all cities. [Link] 15
UNIT V
NP-COMPLETE AND APPROXIMATION ALGORITHM
Tractable and intractable problems: Polynomial time algorithms – Venn diagram
representation - NP algorithms - NP-hardness and NP-completeness – Bin Packing
problem - Problem reduction: TSP – 3- CNF problem. Approximation Algorithms: TSP -
Randomized Algorithms: concept and application - primality testing - randomized quick
sort - Finding kth smallest number
PART-A
1. What are NP- hard and NP-complete problems?
The problems whose solutions have computing times are bounded by polynomials of
small degree.
2. Define bounding.
Branch-and-bound method searches a state space tree using any search
mechanism in which all children of the E-node are generated before another node
becomes the E-node.
Each answer node x has a cost c(x) and we have to find a minimum-cost answer
node. Common strategies include LC, FIFO, and LIFO.
Use a cost function ˆc(·) such that ˆc(x) c(x) provides lower bound on the
solution obtainable from any node x.
Given an array and a number k where k is smaller than the size of the array, we
need to find the k’th smallest element in the given array. It is given that all array
elements are distinct.
The polynomial time means the complexity of algorithm can be expressed in O(nK).
The nondeterministically polynomial time is the time required by the algorithm to
execute which can not be expressed in O(nK).
Example: Travelling salesperson problem, Knapsack problem.
[Link] any three problems that have polynomial time algorithms. Justify your answer.
The problems that can be solved in polynomial time are called P- class problems.
For example -
1. Binary search - In searching an element using binary search method, the list is
simply divided at the mid and either left or right sub list is searched for key element.
This process is carried out in O(logn).
[Link] the proof which says that a problem 'A' is no harder or no easier than
problem 'B'.
The bin packing algorithm is used to find the most efficient arrangement of
values in a series of finite sized bins. It is an optimization problem in which items of
different sizes must be packed into a finite number of bins or containers, each of a fixed
given capacity, in a way that minimizes the number of bins used. The algorithm is used
in many real-world applications such as loading trucks, meeting weight capacities, and
creating/storing file backups.
Randomized algorithms are used in a wide range of applications. Here are some key
areas where they are particularly effective:
Cryptography:
o Secure key generation
o Random number generation for encryption protocols
Primality Testing:
o Algorithms like the Miller-Rabin test efficiently determine if numbers are
prime.
Monte Carlo Methods:
o Used in simulations, numerical integration, and optimization by
leveraging random sampling.
Randomized Data Structures:
Structures like skip lists and treaps achieve good average-case performance
using randomness.
PART-B
Examples
Towers of Hanoi: we can prove that any algorithm that solves this problem must have a worst-
case running time that is at least 2n − 1.
* List all permutations (all possible orderings) of n numbers.
[Link] the P, NP, and NP Complete problems with suitable example Au: Dec -13 or
Outline the steps to find an approximation algorithm solution to NP-hard optimization
problems using approximation algorithms with an example. Nov/Dec2019,Apr/may
2023
There are several reasons for drawing the intractability line in this [Link], the
entries of Table and their discussion imply that we cannot solve arbitrary instances of
intractable problems in a reasonable amount of time unless such instances are very
small.
Second, although there might be a huge difference between the running times in
O(p(n)) for polynomials of drastically different degrees, there are very few useful
polynomial-time algorithms with the degree of a polynomial higher than three. In
addition, polynomials that bound running times of algorithms do not usually have
extremely large coefficients.
Third, polynomial functions possess many convenient properties; in particular, both
the sum and composition of two polynomials are always polynomials too.
Fourth, the choice of this class has led to a development of an extensive theory
called computational complexity, as shown in fig 5.1 which seeks to classify problems
according to their inherent difficulty. And according to this theory, a problem’s
intractability remains the same for all principal models of computations and all
reasonable input-encoding schemes for the problem under consideration.
Definition of NPIt stands for “non- deterministic polynomial time “. Note that NP does
not stand for “non-polynomial time” is called intractable.
can consider program P as an input to itself and use the output of algorithm A for pair
(P, P) to construct a program Q as follows:
Partition problem
Given n positive integers, determine whether it is possible to partition them into
two disjoint subsets with the same sum.
Bin-packing problem
Given n items whose sizes are positive rational numbers not larger than 1, put
them into the smallest number of bins of size 1.
Graph-coloring problem
For a given graph, find its chromatic number, which is the smallest number of
colors that need to be assigned to the graph’s vertices so that no two adjacent vertices
are assigned the same color.
Nondeterministic algorithm
A nondeterministic algorithm is a two-stage procedure that takes as its input
an instance I of a decision problem and does the following.
Deterministic
Deterministic (“verification”) stage: A deterministic algorithm takes both I and
S as its input and outputs yes if S represents a solution to instance I. (If S is not a
solution to instance I, the algorithm either returns no or is allowed not to halt at all.)
A nondeterministic algorithm solves a decision problem if and only if for every
yes instance of the problem it returns yes on some execution.
In other words, we require a nondeterministic algorithm to be capable of
“guessing” a solution at least once and to be able to verify its validity.
Finally, a nondeterministic algorithm is said to be nondeterministic polynomial
if the time efficiency of its verification stage is polynomial. Now we can define the class
of NP problems.
In the above given nondeterministic algorithm there are three functions used-
1. Choose – arbitrarily choose one of the element from given input set
2. Fail- indicates the unsuccessful completion
3. Success – indicates successful completion
The algorithm is of non deterministic complexity O(1), when A is not ordered then the
Deterministic search algorithm has a complexity Ω(n)
Fig:5.2 NP problems
As shown in Fig 5.2 Notation of an NP complete problem. Polynomial tie reductions of NP
problems to an NP complete problems are shown by arrows.
A decision problem D1 is said to be polynomially reducible to a decision
problem D2, if there exists a function t that transforms instances of D1 to instances of D2
such that:
1. t maps all yes instances of D1 to yes instances of D2 and all no
instances of D1 to no instances of D2
2. t is computable by a polynomial time algorithm
This definition immediately implies that if a problem D1 is polynomially
reducible to some problem D2 that can be solved in polynomial time, then problem D1
can also be solved in polynomial time (why?).
A decision problem D is said to be NP-complete if:
1. It belongs to class NP
2. every problem in NP is polynomially reducible to D
For example, we can prove that the Hamiltonian circuit problem is polynomially
reducible to the decision version of the traveling saleman problem.
Cooks theorem
Nevertheless, this mathematical feat was accomplished independently by
Stephen Cook in the United States and Leonid Levin in the former Soviet Union.2 In his
1971 paper, Cook [Coo71] showed that the so-called CNF-satisfiability problem is
NPcomplete as shown in fig 5.3
The CNF-satisfiability problem deals with boolean expressions.
Each boolean expression can be represented in conjunctive normal form, such as
the following expression involving three boolean variables x1, x2, and x3 and their
negations denoted ¯x1, ¯x2, and ¯x3, respectively:
(x1 ¯x2 ¯x3)&( ¯x1 x2)&( ¯x1¯x2 ¯x3).
The CNF-satisfiability problem asks whether or not one can assign values true
and false to variables of a given boolean expression in its CNF form to make the entire
expression true.
Showing that a decision problem is NP-complete can be done in two steps.
1. First, one needs to show that the problem in question is in NP; i.e., a randomly
generated string can be checked in polynomial time to determine whether or not
it represents a solution to the problem. Typically, this step is easy.
2. The second step is to show that every problem in NP is reducible to the problem
in question in polynomial time.
Table of contents:
1. Mathematical Formulation of Bin Packing
2. A brief outline of Approximate Algorithms
3. Lower Bound on Bins
4. Input Order dependent or Online Algorithms
Next Fit algorithm
First Fit algorithm
Best Fit Algorithm
Worst Fit Algorithm
5. Input Order Independent or Offline Algorithms
First Fit Decreasing
Best Fit Decreasing
6. Applications of Bin-Packing Algorithms
is
We will suppose, as is usual, that the weights Wj are positive integers. Hence, without
loss of generality, we will also assume that c is a positive integer
Wj < c for j belonging to N.
As you can see, we have a broad rule of approximation and not an exact algorithm. Such
algorithms are called NP problems. In fact Bin Packing Problem is a NP-hard problem
Step:2 Assuming the sizes of the items be {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6}.
The most optimal solution (z(I))for this instance I would be
Let us now look at the various optimization algorithms for Bin Packing Problem.
Step:2 Assuming the sizes of the items be {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6}.
The minimum number of bins required would be Ceil ((Total Weight) / (Bin Capacity))=
Celi(3.7/1) = 4 bins.
The Next fit solution (NF(I))for this instance I would be-
Considering 0.5 sized item first, we can place it in the first bin
Step:3 Moving on to the 0.7 sized item, we cannot place it in the first bin. Hence we
place it in a new bin.
Step: 4Moving on to the 0.5 sized item, we cannot place it in the current bin. Hence we
place it in a new bin.
Step:5 Moving on to the 0.2 sized item, we can place it in the current (third bin)
Step:6 Similarly, placing all the other items following the Next-Fit algorithm we get-
Thus we need 6 bins as opposed to the 4 bins of the optimal solution. Thus we can see
that this algorithm is not very efficient.
Step:1 Let us consider the same example as used above and bins of size 1
Step:2 Assuming the sizes of the items be {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6}.
The minimum number of bins required would be Ceil ((Total Weight) / (Bin Capacity))=
Celi(3.7/1) = 4 bins.
The First fit solution (FF(I))for this instance I would be-
Step: 3 Considering 0.5 sized item first, we can place it in the first bin
Step:4 Moving on to the 0.7 sized item, we cannot place it in the first bin. Hence we
place it in a new bin.
Step:5 Moving on to the 0.5 sized item, we can place it in the first bin.
Step:6 Moving on to the 0.2 sized item, we can place it in the first bin, we check with the
second bin and we can place it there.
Step:7 Moving on to the 0.4 sized item, we cannot place it in any existing bin. Hence we
place it in a new bin.
Step:8 Similarly, placing all the other items following the First-Fit algorithm we get-
Thus we need 5 bins as opposed to the 4 bins of the optimal solution but is much more
efficient than Next-Fit algorithm.
It can be seen that the First Fit never uses more than 1.7 * z(I) bins. So First-Fit is better
than Next Fit in terms of upper bound on number of bins.
Complexity
Worst case time complexity: Θ(n*n)
Step:1 Let us consider the same example as used above and bins of size 1
Step:2 Assuming the sizes of the items be {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6}.
The minimum number of bins required would be Ceil ((Total Weight) / (Bin Capacity))=
Ceil(3.7/1) = 4 bins.
The First fit solution (FF(I))for this instance I would be-
Step:2 Considering 0.5 sized item first, we can place it in the first bin
Moving on to the 0.7 sized item, we cannot place it in the first bin. Henc e we place it in a
new bin.
Step:3 Moving on to the 0.5 sized item, we can place it in the first bin tightly.
Step:4 Moving on to the 0.2 sized item, we cannot place it in the first bin but we can
place it in second bin tightly.
Step:5 Moving on to the 0.4 sized item, we cannot place it in any existing bin. Hence we
place it in a new bin.
Step:6 Similarly, placing all the other items following the First-Fit algorithm we get-
Thus we need 5 bins as opposed to the 4 bins of the optimal solution but is much more
efficient than Next-Fit algorithm.
This algorithm involves an idea to places the next item in the least tight spot to even out
the bins. In other words, put it in the bin so that most empty space is left.
Analysis Of upper-bound of Worst-Fit algorithm
Worst Fit can also be implemented in O(n Log n) time using Self-Balancing Binary
Search Trees.
If z(I) is the optimal number of bins , then Worst Fit never uses more than 2 * z(I)-2
bins. So Worst Fit is same as Next Fit in terms of upper bound on number of bins.
Applications of Bin-Packing Algorithms
Loading of containers like trucks.
Placing data on multiple disks.
This is used extensively while transporting goods over ships
PREPARED BY: Mrs.E,INDRA ASP/CSE,[Link] AP/CSE , [Link] PRIYA ,AP/CSE ,
20
CS3401 ALGORITHMS UNIT 5 MEC
Job scheduling.
Step:2 Assuming the sizes of the items be {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6}.
Sorting them we get {0.7, 0.6, 0.5, 0.5, 0.5, 0.4, 0.2, 0.2, 0.1}
The First fit Decreasing solution would be-
We will start with 0.7 and place it in the first bin
Step:3 We then select 0.6 sized item. We cannot place it in bin 1. So, we place it in bin 2
Step:4 We then select 0.5 sized item. We cannot place it in any existing. So, we place it
in bin 3
Thus only 4 bins are required which is the same as the optimal solution.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
void swap(double *xp, double *yp)
{
double temp = *xp;
*xp = *yp;
*yp = temp;
}
int firstFit(double size[], int n, int c)
{
int res = 0;
int bin_rem[n];
for (int i = 0; i < n; i++) {
int j;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= size[i]) {
bin_rem[j] = bin_rem[j] - size[i];
break;
}
}
if (j == res) {
bin_rem[res] = c - size[i];
res++;
}
}
return res;
}
int main()
{
double size[] = {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6};
int c = 1;
int n = sizeof(size) / sizeof(size[0]);
cout << "Number of bins required in First Fit Decreasing : "<< nextFit(size, n, c);
return 0;
}
Step:1 Let us consider the same example as used above and bins of size 1
Step:2Assuming the sizes of the items be {0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.5, 0.1, 0.6}.
Sorting them we get {0.7, 0.6, 0.5, 0.5, 0.5, 0.4, 0.2, 0.2, 0.1}
The Best fit Decreasing solution would be-
We will start with 0.7 and place it in the first bin
Step:2We then select 0.6 sized item. We cannot place it in bin 1. So, we place it in bin 2
Step:3 We then select 0.5 sized item. We cannot place it in any existing. So, we place it
in bin 3
Thus only 4 bins are required which is the same as the optimal solution.
Complexity
Worst case time complexity: Θ(n*n)
Average case time complexity: Θ(n*n)
Best case time complexity (Can be achieved using Self-balancing Binary
trees): Θ(nlogn)
Space complexity: Θ(n)
Applications of Bin-Packing Algorithms
Loading of containers like trucks.
Placing data on multiple disks.
This is used extensively while transporting goods over ships
Job scheduling.
[Link] explain about Problem Reduction.
To prove whether particular problem is NP complete or not we use polynomial
reducibility. That means if
Component design - In this reduction A→B by building special component for input B
that enforce properties required by A.
If L and L₂ are two problems, then problem L reduces to L which can be denoted
as L L2 if and only if there is a way to solve L by deterministic polynomial time
algorithm using a deterministic algorithm that solves L in polynomial time. It
means that if we have polynomial time algorithm for L, then we can solve L, in
polynomial time.
L₁ ∞ L2 and L2∞L3
then L₁ ∞L3
• Two problems P and Q are said polynomially equivalent if and only if P ∞ Q and
Q ∞ P.
If problem P₁ is NP-complete and there is polynomial time reduction of P₁ to P2
then P₂ is NP-complete.
5. Explain NP-completeness.
In this section we will discuss two problems namely Vertex cover and the 3SAT
problem which are actually NP Complete problems. Their proof of NP completeness is
based on reduction technique. That means there are some problems which are already
proved as NP Complete problems and using these problems we will prove that the
vertex cover and the 3SAT problems are NP Complete problems.
Step 4: Now show that the function f can be computed in polynomial time.
Show that the satisfiability of Boolean formulas in 3-conjunctive normal form (3-
CNF) is NP-complete. Apr/May2024
For example
The CNF-SAT is a problem which takes Boolean formula in CNF form and checks
whether any assignment is there to Boolean values so that formula evaluates to 1.
Proof :
1) SAT is NP.
iv) These sets of equations are separated by values and adding final output
variable at the end.
A 3-SAT problem is a problem which takes a Boolean formula S with each clause
having exactly three literals and check is 5 is satisfied or not.
Proof: The language: 3-SAT is a restriction of SAT. We replace each clause C that
represents the SAT problem to a function f by family of De of clauses that represent
satisfiability.
For example say
C =a v b v c v d v e
One can simulate this by
Dc = (a v b v x)(x v e v y)^( v d v e)
where x and y are new variables.
Need to verify:
1) If C is FALSE, then Dc is FALSE; and
2) 2) If C is TRUE, then one can make Dc TRUE.
If f is satisfiable then there is assignment where each clause C is TRUE. This can be
extended to make Dc TRUE
Further if f is evaluated to FALSE, then some clauses say C must be FALSE and thus
corresponding family Dc evaluates to FALSE
This conversion process can be done in polynomial time. Thus we have shown that SAT
reduces to 3-SAT in polynomial time. As we know that SAT is a NP complete problem, so
we must say that 3-SAT is also NP complete problem.
The traveling salesman problem consists of a salesman and a set of cities. The salesman
has to visit each one of the cities starting from a certain one and returning to the same
city. The challenge of the problem is that the traveling salesman wants to minimize the
total length of the trip
Proof:
To prove TSP is NP-Complete, first we have to prove that TSP belongs to NP.
In TSP, we find a tour and check that the tour contains each vertex once. Then
the
total cost of the edges of the tour is calculated. Finally, we check if the cost is
minimum.
This can be completed in polynomial time. Thus TSP belongs to NP.
NP Hard Problem
There are some NP-hard problems that are not NP-complete as shown in fig:5.8 For
example halting problem. The halting problem states that: "Is it possible to determine
whether an algorithm will ever halt or enter in a loop on certain input ?"
In this section we will discuss two important issues namely, "What is NP-hard blem?"
and "How approximation algorithms are used for NP-hard problems 7"" us start
our discussion with the understanding of NP-hard problems. In mutational complexity
theory there are different types of problems. Some problems decision problems for
which answer is yes or no, others are search problems and any others are optimization
problems.
The solvability of problems in polynomial time eternally tested by nondeterministic
Turing machines. Hence the complexity class of blems that are intrinsically harder
than those that can be solved by a deterministic Turing machine in polynomial time are
called NP-hard problems. Let have a formal definition of NP-hard.
Approximation algorithm
Accuracy ratio
It is always necessary to know the accuracy of approximation to the actual optimal
solution. Hence accuracy ratio is defined as
where 5, denotes approximate solution, r(s) denotes accuracy ratio, f(s) is a value of
objective function for solution given by approximation algorithm, f(s) is a value of
objective function. Generally r(s,)>=1. When r(s) reaches close to 1 then is a better
approximate solution
Performance ratio
The best upper bound on accuracy ratio taken over all instances of the problem
is called performance ratio. It is denoted by R. By knowing performance ratio one can
judge quality of approximation algorithm. The approximation algorithms with R value
nearer to 1 is supposed to be a better approximation algorithm.
C-Approximation algorithm
there exists a value c which is >= 1 and r(s) sc for all instances of problem then
algorithm is called c-approximation algorithm. If c value is 1 then corresponding are
good. For a c-approximation algorithm for any instance problem is-
The travelling salesman problem is based on the idea of obtaining optimum tour hen
travelling between many cities. The decision version of this algorithm belongs to a of
NP-complete problem and optimization version of this algorithm belongs to hard class
of problems. There are two approximation algorithms used for TSP: A hard class of
problem and those are
[Link]
The distance from city i to j should be same as distance between city j to i. The
Eudidiean instances satisfy following conditions about the accuracy ratio
Example: Consider the graph as given below and apply the twice-around-the-tree
algorithm.
Step 3 : Record the visited nodes A B CBD-E-D- B - A. Eliminate duplicates then A-B-C-
D-E-A. This basically gives Hamiltonian circuit.
But the tour obtained is not the optimal tour as shown in fig 5.12
In the traveling salesman Problem, a salesman must visits n cities. We can say that salesman
wishes to make a tour or Hamiltonian cycle, visiting each city exactly once and finishing at
the city he starts from. There is a non-negative cost c (i, j) to travel from the city i to city j.
The goal is to find a tour of minimum cost. We assume that every two cities are connected.
Such problems are called Traveling-salesman problem (TSP).
We can model the cities as a complete graph of n vertices, where each vertex represents
a city.
If we assume the cost function c satisfies the triangle inequality, then we can use the
following approximate algorithm.
Triangle inequality
Traveling-salesman Problem
Intuitively, Approx-TSP first makes a full walk of MST T, which visits each edge exactly
two times. To create a Hamiltonian cycle from the full walk, it bypasses some vertices
(which corresponds to making a shortcut) as shown in fig 5.13
3CNF SAT
Concept: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have almost
3 literals or constants
Such as (X+Y+Z) (X+Y+Z) (X+Y+Z)
You can define as (XvYvZ) ᶺ (XvYvZ) ᶺ (XvYvZ)
V=OR operator
^ =AND operator
These all the following points need to be considered in 3CNF SAT.
To prove: -
1. Concept of 3CNF SAT
2. SAT≤ρ 3CNF SAT
3. 3CNF≤ρ SAT
4. 3CNF ϵ NPC
1. CONCEPT: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will
have almost 3 literals or constants.
2. SAT ≤ρ 3CNF SAT:- In which firstly you need to convert a Boolean function
created in SAT into 3CNF either in POS or SOP form within the polynomial time
F=X+YZ
= (X+Y) (X+Z)
= (X+Y+ZZ') (X+YY'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
3. 3CNF ≤p SAT: - From the Boolean Function having three literals we can reduce
the whole function into a shorter one.
F= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
= (X+Y+ZZ') (X+YY'+Z)
= (X+Y) (X+Z)
= X+YZ
4. 3CNF ϵ NPC: - As you know very well, you can get the 3CNF through SAT and
SAT through CIRCUIT SAT that comes from NP.
Proof of NPC:-
1. It shows that you can easily convert a Boolean function of SAT into 3CNF SAT
and satisfied the concept of 3CNF SAT also within polynomial time through
Reduction concept.
2. If you want to verify the output in 3CNF SAT then perform the Reduction and
convert into SAT and CIRCUIT also to check the output
NP-Completeness
A decision problem L is NP-Hard if
L' ≤p L for all L' ϵ NP.
Definition: L is NP-complete if
1. L ϵ NP and
2. L' ≤ p L for some known NP-complete problem L.' Given this formal definition,
the complexity classes are:
P: is the set of decision problems that are solvable in polynomial time.
NP: is the set of decision problems that can be verified in polynomial time.
NP-Hard: L is NP-hard if for all L' ϵ NP, L' ≤p L. Thus if we can solve L in polynomial
time, we can solve all NP problems in polynomial time.
NP-Complete L is NP-complete if
1. L ϵ NP and
2. L is NP-hard
If any NP-complete problem is solvable in polynomial time, then every NP-Complete
problem is also solvable in polynomial time. Conversely, if we can prove that any NP-
Complete problem cannot be solved in polynomial time, every NP-Complete problem
cannot be solvable in polynomial time.
Reductions
Concept: - If the solution of NPC problem does not exist then the conversion from one
NPC problem to another NPC problem within the polynomial time. For this, you need
the concept of reduction. If a solution of the one NPC problem exists within the
polynomial time, then the rest of the problem can also give the solution in polynomial
time (but it's hard to believe). For this, you need the concept of reduction.
Example: - Suppose there are two problems, A and B. You know that it is impossible to
solve problem A in polynomial time. You want to prove that B cannot be solved in
polynomial time. So you can convert the problem A into problem B in polynomial time.
Example of NP-Complete problem
NP problem: - Suppose a DECISION-BASED problem is provided in which a set of
inputs/high inputs you can get high output.
Criteria to come either in NP-hard or NP-complete.
1. The point to be noted here, the output is already given, and you can verify the
output/solution within the polynomial time but can't produce an
output/solution in polynomial time.
2. Here we need the concept of reduction because when you can't produce an
output of the problem according to the given input then in case you have to use
an emphasis on the concept of reduction in which you can convert one problem
into another problem.
Note1:- If you satisfy both points then your problem comes into the category of NP-
complete class
Note2:- If you satisfy the only 2nd points then your problem comes into the category of
NP-hard class
So according to the given decision-based NP problem as shown in fig:5.14 , you can
decide in the form of yes or no. If, yes then you have to do verify and convert into
another problem via reduction concept. If you are being performed, both then decision-
based NP problems are in NP compete.
Here we will emphasize NPC.
For example: Picking up a card from a deck of 52 cards, tossing coin for five times,
choosing a red ball from an urn containing red and white balls, rolling die four times.
Each possible result of such experiment is called sample point. The set of all sample
points is called sample space. The sample space is denoted by S. The sample space S is
finite set. An event E occurs from sample space. For m sample points there are 2m
possible events.
Probability |E|/|S|
For example: Picking up a card from a deck of 52 cards, tossing coin for five times,
choosing a red ball from an urn containing red and white balls, rolling die four times.
Each possible result of such experiment is called sample point. The set of all sample
points is called sample space. The sample space is denoted by S. The sample space S is
finite set. An event E occurs from sample space. For m sample points there are 2m
possible events.
For example: When a coin is tossed, then we may get either head (H) or tail (T).
Suppose, we have tossed four coins together then there are 16 possible outcomes:
HHHH, HHHT HHTH, HHTT, HTHH, HTHT, HTTH, HTTT, THHH, THHT, THTH THIT,
TTHH, TTHT, TTTH, TTTT. For 4 events (HHTH, THTT, TTHH, TTTT), the
probability is 4/16= 1/ 4
Mutual exclusion: Two events A and B are said to be mutually exclusive if they do not
have any common sample point. Hence A cap B= emptyset For example A=(HHTH,
HHTT), B= (HTTT, THHT) are mutually exclusive
Independence: Two events A and B are said to be independent if [A cap B]= P[A] * P[B]
Random variable: The random variable is basically a function that maps elements of
For sample point a S the F. (a) denotes the mapping. If F denotes a finite set of elements
then it is called discrete. Thus the random variables can be discrete random variables.
For example - If we pick up four balls from an urn containing red and white balls
then the number of red balls that get selected is F (RRRW) = 3 or (RWWW) = 1 and so
on.
For example: if we pick up four balls randomly from an Turn containing red and white
balls and F is number of red balls, then F can take on five values 0, 1, 2, 3 and 4 then
Here 1 means presence of Red balls and 0 Means absence of red ball from the four balls
that are picked up as shown in table 5.1
Hence probability distribution of F is given by
P [F = 0]=1/16 i.e. no red ball present.
P [F=2] =6/16 i.e. two red balls present from picked up balls
P[F=4] = 1/16 i.e. when 4 red balls are present from the picked balls.
Binomial distribution:
Suppose an experiment is conducted then the result of such experiment can be either
success or failure.
Let n be number trials or experiments. These experiments are called Bernoulli trial.
The sample space S contains 2" sample points. The random variable F has binomial
distribution with (n, p) which can be given by -
ii) For different inputs there may be different outcomes on each execution.
iii) For same inputs there may be different outcomes on each execution.
Primality Testing
'Deciding whether the given number n is prime or not is a problem of primality testing.
The application of primality testing is cryptology.
Any integer greater than one is said to be prime if it is divisible by 1 or by that number
itself. We consider 1 as non-prime number but 2, 3, 5, 7, 11 and 13 are someprime
numbers. But if a number n is non-prime (or composite) then it must have a divisior
<=[√n] To check whether given number n is prime or not we must check every m
elements from interval 2 to [√n] whether m divides n. If there is no such element which
This equation is from Fermat's theorem. Suppose, we want to test if n is prime, then
we can pick random a's in the interval and see whether equality holds or not. If equality
does hold then that means n is not prime. But even if equality holds then we can say
that n is probably prime. Thus from above algorithm may or may not get correct prime
number.
• To bring improvement over the quick sort choice of pivot is the key factor. Wecan
have following choices of pivot –
*The quick sort works better in average case but its performance is very poor in worst
case.
*Hence from above mentioned three choices randomization is the better choice to
improve the performance of the quick sort in worst case.
In above algorithm we invoke the random() function only if the (high-low) The number
5 is not a magic number but it is observed that it gives best results with this value. The
time complexity of above algorithm is O(nlogn)
Basic concept: An array of elements and value of K is given where K is smaller than size
of array. Find the Kth smallest element in given array. Note that all the elements of
array are distinct.
For example –
Randomized algorithm:
In this algorithm we apply the quick sort method, but we do not apply the quick sort
method completely, but stop the algorithm at the point when pivot itself is Kth smallest
element. The steps for the algorithm are as follows –
Step 4: Else if the index of pivot is greater than K, then scan for the left subarray
recursively, else scan for the right subarray recursively.
Step 5: Repeat this process until the element at index K is not found.
To calculate the time taken to solve, we normally evaluate the number of steps the
procedure takes to solve the problem, assuming each step takes unit time. The
definition of step depends on the model of computation, however we will not go into the
details of this, and suffice ourselves with the assumption that an arithmetic step or a
comparison step taken one unit of time. Thus, for instance, if ever an algorithm requires
the addition of two numbers, we will assume this can be done in unit time, irrespective
of the value of the numbers.
So, coming back to the problem (1||PCj), the size of the input is (n + Pjdlog2 pje)
which is at least n+log2 pmax. An algorithm for (1||PCj) is polynomial time if the
running time is bounded by p(n+log2 pmax), where p() doesn’t depend on the input of
the instance.
An algorithm which runs in time polynomial of the data when the data is
represented in unary is called a pseudo-polynomial time algorithm. Pseudo-polynomial
time algorithms are not polynomial time. An algorithm which runs in time polynomial of
the number of input points, irrespective of the size of the actual data, is called a strongly
polynomial time algorithm. Recall that the algorithm SPT, which orders the jobs in
increasing order of processing time, runs in time O(nlogn) and thus is strongly
polynomial time. (Note that we assume here that the time taken to compare two
numbers is unit even if the numbers are huge).
Polynomial Time Reductions
We have already looked at reduction among scheduling problems. The same can be
extended to any computational problem.
Definition
A computational problem X is polynomial time reducible to a computational problem Y ,
if given an algorithm A for the problem Y with time complexity T(|Y |) (note that T
might or might not be a polynomial), we can solve an instance of X in time (p(|X|) +
q(|X|)T(|X|)). Note that the input to the time function T is the size of X. We denote this
as X E Y or X ≤P Y .
Most often a polynomial time reduction proceeds in the following manner: given an
instance of X, we come up with an instance of Y , and argue that given the solution to
this instance of Y , one can recover, in polynomial time the solution for the instance of X.
We give an example.
Example Consider the following two problems.
Hamiltonian Circuit Problem (HCP): Given a graph G on n vertices and m edges, is there
a Hamiltonian circuit in G?
Travelling Salesman Problem (TSP): Given a graph G on n vertices (cities) with distance
dij between any two cities i and j, find a tour of minimum distance.
Note that HCP ≤P TSP. To see this, given an instance of HCP, construct the instance of
TSP by defining the distance between vertices i and j as follows – dij = 1 is (i,j) is an
edge, and dij = 2 otherwise. It is now not too hard to see that there is a Hamiltonian path
in the graph iff the optimal tour has cost n.
Why are polynomial time reductions useful? Well, if X ≤P Y , and if we have a
polynomial time algorithm for Y , then we have a polynomial time algorithm for X as
well. Thus, these reductions help in classifying the problems into “easy” and “hard”
problems. Furthermore, if there is a reason to believe that the problem X does not have
any polynomial time algorithm, then Y cannot have a polynomial time algorithm either.
This is where reductions come in most handy. Unfortunately, there is not a single
problem for which we can say there are no polynomial time algorithms. However, as we
see in the next section, there is a classification of problems into “easy” and “hard”
problems with the property that if any of the hard problems have a polynomial time
algorithm, then they all do. This is probably the most compelling reason why computer
scientists believe that there can be no polynomial time algorithm for any of them. Pretty
flaky? That is unfortunately the state of affairs!
Every optimization problem X has a decision version X0. For instance, the decision
version of TSP has input the input of TSP and an extra integer B, and the problem is:
”Given an input of TSP, is there a tour of distance at most B?”. Note that this is a decision
problem. Furthermore, TSP0 ≤P TSP, for if we have an algorithm for the optimization
problem, we can surely solve the decision problem. The converse is always not true.
However, in most cases, the solution to the decision problem also comes up with a
solution which can be used for the optimization problem. Lastly, note that since X0 ≤P X,
X is harder than X0.
A decision problem X is said to be in NP, if for every “yes” instance there exists a
polynomial sized “certificate” which can be “verified” in polynomial time. Let us
elucidate. A “yes” instance of the problem X is one in which the answer is “yes”. For
instance, a graph which has a Hamiltonian circuit is a yes-instance for HCP. A
“certificate” for the yes-instance is a proof that the instance is indeed a yes-instance. For
instance, given a graph which has a Hamiltonian circuit, the circuit is the certificate.
The size of the certificate is required to be a polynomial in the size of the input. A
“verifier” is nothing but a polynomial time algorithm which takes input the yes-instance
and the certificate. If for each yes-instance there exists a certificate, and if the yes-
instance can be verified in polynomial time in the size of the input, then the problem is
in NP. Since given a candidate Hamiltonian circuit of the graph, we can verify it is
Hamiltonian by simply checking the existence of the various edges claimed by the
circuit, we get that the problem HCP is in NP.
Let us look at another example. Consider the problem COMPOSITE which given an
input a natural number N, outputs yes if the number is composite, and no if the number
is prime. (What is the size of the input?) We claim that COMPOSITE ∈ NP. Why? Because
for every yes-instance, that is, a composite number N, we can give a certificate, the
factors of the numbers, say a and b, and this can be checked to be a proper certificate by
just multiplying the two numbers and seeing if it gives N or not.
The P in P stands for “polynomial time”. However, NP does not stand for “not
polynomial”. It stands for non-deterministic polynomial time. This is because any
problem in NP can be solved in polynomial time of one could “non-deterministically
guess” the polynomial sized certificate for every yes-instance.
We now give a rigorous definition of the classes. Any decision problem X has two
instances, the yes-instance and the no-instance. A certificate or a proof, y, of an instance
is a string of {0,1} which may depend on x. y is said to have polynomial size if |y| =
poly(|x|). A verifier V takes as input an instance, x, and a proof y, and outputs yes or no.
Definition a polynomial time verifier V such that For every yes instance x ∈ X, there
exists a polysized proof y such that V (x,y) = yes. For every no instance x ∈ X, and for
every proof y, we have V (x,y) = no. What is the relation between the classes P and NP?
Well P ⊆ NP.
Theorem P ⊆ NP.
Proof. Let X be any decision problem in P (the optimization problems can be handled
similarly). Let A be an algorithm to solve the problem. Let x be a yes-instance of X. As a
verifier, one can just run A on x to check it is a yes-instance. Thus, the certificate is
empty and the verifier is just the algorithm A.
Are all decision problems in NP? All the problems we have looked at so far are in NP.
But that doesn’t mean that all problems lie in this class, or at least are not known to lie
in this class.
Example Let us turn the COMPOSITE problem on its head to get the PRIMES problem:
Given a natural number N, decide whether the number N is a prime number or not. Can
you now find a good certificate for yes-instances? That is, given a prime number N, can
you provide some extra proof that N is a prime which can be verified in polynomial
time? It turns that one can, however the answer is not simple and one needs to use
algebra to give this certificate.
We end this section with the following million dollar exercise.
Exercise Prove or disprove: P = NP.
NP-completeness
It is safe to say that most researchers believe that P 6= NP. However, many researchers
also believe we do not have an inkling of an idea how to solve this problem. What
researchers have done however is they can identify the “hardest” problems in NP.
4. Vertex Cover: Given a graph G and a number B, are there at most B vertices such
that each edge in G is adjacent to at least one of these vertices.
In the next lecture or two we will see a list of scheduling problems which are
NPcomplete. The basic schema we will use to prove NP-completeness of a problem X
will be the following:
1. Show X ∈ NP (This is normally easy).
3. Reduce Y ≤P X.
• Thus if Y can solved in polynomial time, one can use the above procedure to
convert an instance of X to an instance of Y , and check if the Y -instance is yes or
no, using the algorithm.
This completes the proof. In fact, it proves the special case of knapsack when weight
of an item equals its profit is also NP-complete.
The PTAS for this problem is based on a technique called list pruning, where we
iteratively maintain a list of potential subset sums while discarding unnecessary
elements to keep computation efficient.
Algorithm Outline
1. Initialization
o Start with an empty subset that sums to 0: L0={0}
2. Iterative List Expansion
o For each element si in the input set S, generate a new list by adding si to
each element in the current list.
o Merge the new sums with the existing list.
3. Pruning Step
o Sort the list of sums in increasing order.
o Remove sums that are "too close" together, meaning if x and y are two
sums and x≤(1+ϵ)x, we remove y.
4. Final Step
o Find the largest value in the pruned list that does not exceed T
Key Properties
Approximation Guarantee: The final solution is at least (1−ϵ) times the optimal
sum.
Polynomial Time Complexity: The algorithm runs in O(n/ϵ) time, which is
polynomial for fixed ϵ
Illustration
Conclusion
This PTAS effectively reduces the number of subset sums considered while ensuring a
near-optimal result. It balances accuracy and efficiency, making it suitable for large
instances where exact algorithms (e.g., dynamic programming) would be too slow.
14. Illustrate the working of Miller-Rabin randomized primality test Aprl/May 2024
Algorithm Overview
The test is based on Fermat’s Little Theorem, which states that if nnn is prime, then
for any integer aaa,
a(n−1)≡1(mod n)
However, some composite numbers (called Carmichael numbers) also satisfy this
condition for many values of a, so we refine the test using strong pseudoprime
checks.
n−1=2s⋅d
where d is odd.
29≡511≡29mod 37
218=(29)2≡292≡4 mod 37
236=(218)2≡42≡16mod 37
o Since this is not ±1n fails the test for a=2 and should be tested with other
bases.
Since 37 is actually prime, another base (e.g., a=3,5,7) would confirm primality.
April/May 2024
PARTA
1. State the difference between tractable and non-tractable problems. [Link] 35, [Link] 7
2. When is a problem said to be NP- hard? Give an example. [Link] 23, [Link] 5
PART-B
2. Show that the satisfiability of Boolean formulas in 3-conjunctive normal form (3-
CNF) is NP-complete. Q.no7
Nov/Dec 2024
PART-A
1. Give example for NP hard and NP complete problem. [Link] 4
2. List some applications of using randomized algorithm. [Link] 37
PART-B
[Link] polynomial time algorithm problems with an example. [Link] 12
[Link] approximation algorithm for travelling salesman problem with suitable
example. [Link] 9