DESIGNAND ANALYSIS OF ALGORITHMS

Suppose a salesman needs to visit 10cities across the country. How does one determine
the order in which cities should be visited such that the total distance travels is
minimized. The brute force solution is simply to calculate the total distance for every
possible route and then select the shortest one. This is not particularly efficient because it
is possible to eliminate many possible routes through clever algorithms. Another
example: 5 digit password, in the worst case scenario would take 10 tries to crack.
The time complcxity of brute force is O(a*m). So, if we were to search for a string of
'n' characters in a string of 'm' characters using brute force, it would take us n *m tries.
Long Answer Type guestions
1. a) Explain the basic concept of a divide-and-conquer algorithm.
[WBUT 2004, 2007]
OR,
What do you mean by Divide and Conquer Strategy? WBUT 2018, 2019]
Answer:
Divide and conquer (D&C) is an important algorithm design paradigm based on multi
branched recursion. Adivide and conquer algorithm works by recursively breaking down
a problem intotwo or more sub-problems of the same type, until these become simple
enough to be solved directly. The solutions to the sub-problems are then combined to
give a solution to the original problem.
In divide -and-conquer technique, the set of numbers are stored in an array. The numbers
may or may not arrange in sorted order. To make these numbers in sorted order, we first
split the array into twoparts. In merge sort and binary search the divided arays are equal
but in quick sort it may or may not be equal. Then we further split the arrays into another
two parts each. In this way, we split the initial array into small parts until all the elements
of that small array are sorted (in sorting technique) or until we get the particular element
in that small array (in searching technique). In sorting technique, we further merge the
smallarray and get the initial array with sorted elements.
Example:
Merge sort Algorithm
b) Prove that the average case time-complexity of quick sort is O(n log n). You
should state clearly the reasons behind the design of the recurrence relation you
use for establishing this complexity. WBUT 2004, 20071
Answer:
We assume that each of the sizes of the left partitions are equaly likely, and hence each
has probability l/n.R
With this assumption, the average value of T(), and hence also of T(n-i-1), is
(T(0)+ T(1) +...+T(n-1))/n
Naturally, our recurrence relation becomes
T(n) = 2(T(0) +T(1) t... + T(n-1))/n +cn
Multiplying both sides by n we find nT(n) =2(T(0) +T(1) + ...+T(n-1)) +cn
Substitution of nbyn-1gives
DAA-47
 POPULAR PUBLICATIONS

(n-1)T(n-l) =2(T(0) +T(1) +... +T(n-2)) + c(n-1

Subtracting the last cquation from the previous one,we get nT(n) - (n-1)T(n-1) =
2T(n-1)+ 2cn -c
Rearranging and ignoring constant c, we arrive at nT(n) = (n+1)T(n-1) +2cn
Division throughout by n(nt1) gives, T(n/(n+1) =T(n-1)/n +2c/(n+1)
Hence, T(n-1/n = T(n-2\(n--1)+ 2c/n
Similarly T(2)/3 = T(1)2 + 2c/3
Thus, T(n)/(n+1) =T(1)2 +2c(1/3+1/4+ ...+ 1/(n+1))
The sum in brackets is about log (nt1) + y- 3/2, where y is Euler's constant,
which is approximately 0.577.
So, T(n)/(n+1) = 0(log 2n) and thus T(n) = O(n log2 n)
2. a) What is dynamic programming? WBUT 2004, 2005, 2007, 2010]
Answer:
Dynamic programming is a method for reducing the runtime of algorithms exhibiting
the properties of overlapping sub problems and optimal substructure. Dynamic
Programming is an approach developed to solve sequential, or multi-stage, decision
problems; hence, the name "dynamic" programming. But, as we shall see, this approach
is equally applicable for decision problems where sequential property is induced solely
for computational convenience.
Dynamic programming is both a mathematical optimization method and a computer
programming method. In both contexts it refers to simplifying a complicated problem by
breaking it down into simpler sub-problems in a recursive manner.
Algorithms which can be solved by Dynamic programming are,
Matrix-chain multiplication,
All pair shortest paths,
Single source shortest path,
Travelling Salesman problem.
b) Consider the evaluation of the product of n matrices: [WBUT 2004, 2013, 2016]
M= M,* M, *......M,
Assuming that the multiplication of a p°q matrix by a qtr matrix require pqr scalar
multiplication; write a dynamic programming algorithm for ordering this
multiplication with minimum cost. Explain the algorithm in brief.
Answer:
Refer to Question No. 7 of ShortAnswer Type Ouestions.
3. Write an algorithm for any one of the
i) Eight queens problem. following problems:
ii) Graph coloring problem WBUT 2004, 2009, 20131
Answer: WBUT 2004, 2008, 2013, 2014, 2016]
i) Eight queens problem:
Now, we discuss the general algorithm for &-queens problem
Zightqueen (k, 8)

DAA-48
 DESIGN AND ANALYSIS OF ALGORITHMS
Step 1 for i 1 to 8 do

Step 1.1 if Place (k, i) then

Step 1.1.1 x[k] i

Step 1.2 if k +8 then

step 1.2.1 write (x (1: 8]);
Step 1.3 else
Step 1.3.1 Eightqueen (k+1, 8)

The algorithm Place) is used to place a queen in k-th row and i-th column.
Place (k, i)

Step 1 for j to k-1 do

Step 1.1if (x [j]= = i ) or ( (x[j]-i) = =j-k|)) then

{
Step 1.1.1 return false;

Step 2 returm true;

In the above algorithm we can find the appropriate positions of each queen in an 8 x 8
chessboard using backtracking. In Place(k, i), we find the proper position of each queen.
The variable k and idenote the position of a queen at k-th row and i-th column. In Step
1.1, the "if condition has two parts:
3. if (xj]==i)then this means that the two queens are in same column.
4. if ((x[i]i) == i-k) means the absolute values of (x]-i) and (j-k) are same. This
corresponds to the placement of two queens on the same diagonal. If one of the above
two conditions is satisfied, then we cannot place k-th queen at row k of column i.
This function is used in Eightqueens(k, 8) algorithm. Here, the value of 8 denotes the
index of the queen. From this algorithm, in Step 1.1, if the return value of Place (k, ) is
true then we can place a queen at i-th column. From Step 1.2, it is evident that if there is
no other queen left, then print the array x[1:8] to show the position of each queen finally.
Otherwise we call the recursive function Eightqueens (kt1, 8), in Step 1.3.1 for next
queen k+1.

ii) Graph coloring problem:

Applying backtracking method we are trying to color all the nodes of a graph in such a
way that two adjacent nodes do not have same color.bs
Suppose, an undirected graph G =(V, E) is having n number of nodes. Now, we can
represent an adjacency matrix C[n:n] such that,
c[i, j]= 1, ifthere is an edge in between node i and node j.
=0, otherwise
DAA-49
 POPULAR PUBLICATIONS

If at most k colors are required to color all the vertices and they are labeled as c1, c.
C3..c. So, asolution of graph coloring problem can be typically represented by n-tuples
(X1, X2,X3..., X,), where x, is the color of node i and 1<x,<k for all i, 1<isn.
The graph G= (V, E) has n number of vertices, i.e. V| =n and there are k number of
colors in an array A[1:k]
Graph_coloring (c)
for i +1 to n o

Nextcolor (c); 1/ insert a new color

i£ (C> k) then 1L there are no new color

print (no color left);

return false;

else if (C==n) then // al11 colors are used

print (A[1,n]); // print the color with respective vertex
else
Graphcoloring (c+1) ; // otherwise search next color
return C;

Nextcolor (c)
while (!False)

A[c] (A[c] +1) mod (k+1); / find next Color

if A[C] -0 then 17 all colors are used.
return 0;
for i -1 to n do 1/ check forall vertices
{
i£ (G[c, i] # 0) and (A[c] = A[i])
1/ if there is an edge then
1of same color..
between c and i but they are
break;
else
returD C;
}
if (i=n+1) then
return 0; //there is no new Color

The least number of color needed to

color a graph is
chromatic number, say X.of acomplete graph G is called its chromatic number. The
a completeX(G)=d+1,
the vertex. So if we consider a graph G is where d is the degree of
graph, i.e.,each node is connected

DAA-50
 DESIGNAND ANALYSIS OF ALGORITHMS

to allother nodes of the graph then total number of colors required to color all the nodes
of thegraph is d+1.e.g.,

G1 G2 G3 G4
Fig: 1
In the above figure Ieach graph like GI,G2, G3 or G4 requires (d+1) colors to color all
the nodes, where d is the degree of each node.
4. Discuss activity selection problem for job sequencing. WBUT 2004, 2006, 2008]
OR,
Discuss the activity selection problem for job sequencing with an example. Prove
that the time complexity of the algorithm is O(nlogn). WBUT 2012]
OR,
Discuss Job Sequencing with Deadlines with an example. WBUT 2016, 2018]
Answer:
1 part:
Suppose we have a set S = {aj, az, . .., a,} of nproposed activities that wish to use a
resource, which can be used by only one activity at a time. Each activity a has a start
time s; and a finish time f, where 0ss;<f<o. If selected, activity a, takes place during
the half-open time interval [s, f). Activities a and a are compatible if the intervals
[Si, f) and [s, f) do not overlap (i.e., a, and a, are compatible if s; > f or s, > f ). The
activity-selection problem is to select a maximum-size subset of mutually compatible
activities. For example, consider the following set Sof activities, which we have sorted in
monotonically increasing order of finish time.
2 3 4 6 7 8 9 10 11
3 3 6 alo 2 12
S;
4 5 6 10 11 12 13 14
For this example, the subset {a3, a9, all} consists of mutually compatible activities. It is
not a maximal subset, however, since the subset {a, as, ds, aii} is larger. In fact, {a, as,
as, ai} is alargest subset of mutually compatible activities; another largest subset is (a,
as, ag, aË1}.
We only consider one choice, the greedy method and that when we make the greedy
method, one of the subproblems is guaranteed to be empty, so that only one nonempty
subproblem remains. Based on these observations, we shall develop a recursive greedy
algorithm to solve the activity-scheduling problem. We shallcomplete the process of
developing a greedy solution by converting the recursive algorithm to an iterative one.

DAA-51
 POPULAR PUBLICATIONS
2nd Part:
Probably wrong question. applying greedy approach to
Because, in job solution of the
find the optimalsequencing with deadline
problem. procedure,
Now, to wetheareoptimal
find solution, our objective
is to choose the next job in such a way that it would be optimized. Let us consider the
e v e Tunction and we have to optimize this function. So, to enter next job into
IEJ

te queue subject to the constraint that the resulting solution J must be a feasible solution
We must assure that it will increase the obiective functionP, maximum. Now, if we
ieJ

arrange the jobs in decreasing order according to their profits pi, then we can assIgn the
jobs sequentially to the job queue without violating the deadlines, i.e. the solution must
be a feasible solution. This is the activity selection problem ofjobs sequencing.
Suppose we have a set S = fa,, a..a.} of n proposed activities that wish to use a
resource, which can be used by only one activity at a time. Each activity a, has a start time
S; and a finish time f, where 0 <s.<f<o. If selected, activity a, takes place during the
nalt-open time interval [s, fI. Activities a, and a; are compatible if the intervals S, f] and
1S» | do not overlap (i.e., a;and a, are compatible if s;> for s;> ). The activity-selection
problem is to select a maximum-size subset of mutually compatible activities. For
example, consider the following set S of activities, which we have sorted in
monotonically increasing order of finish time.
3 6 7 10 11
1 3 0 5 3 2 12
5 6 7 10 11 12 13 14
For this example, the subset {a, ag, du} consists of mutually
not a maximal subset, however, since the subset {a, a4, ag, ai}compatible activities. It is
ag, aii} is a largest subset of mutually compatible activities; is larger. In fact, {a, a,
a4, a, a1}. another largest subset is {a,
We only consider one choice, the greedy method and
method, one of the sub-problems is guaranteed to be that when we make the greedy
sub-problem remains. Based on these observations, weempty, so that only one nonempty
shall develop a recursive greedy
algorithm to solve the activity-scheduling
problemn. We shall complete the process of
developing a greedy solution by
We stillhave to discuss the runningconverting
time
the recursive algorithm to an iterative one.
in time O(n log n), and the first of the algorithm. The initial-sorting can be done
loop takes
body of the second loop in time O(n), so time O(n). It is not hard to implement each
algorithm runs in time O(n'). the total loop takes time On ). So
the total

DAA-52
 DESIGN AND ANALYSIS OF ALGORITHMS

5.a)Find the optimal solution using greedy criteria for a knapsack having capacity
100 kg for the following list of items having values and weights as shown in the
table. WBUT 2007, 2012, 2013, 2019]
Item Value Weight
10 15
20 25
30 35
40 45
1. 50 55
OR,
Given weight vector (15, 25, 35, 45, 55) and the profit vector (10, 20, 30, 40, 50) and
a Knapsack of capacity 100,find at least three feasible solutions including optimal
one for the Knapsack problem of 5 times. [WBUT 2014]
Answer:
To find the optimal solutions we keep those elements whose az, is maximum into the
knapsack, where a, represents the profit for i-th element and z, represents the weight of
the i-th element.
Now,
4_10 20 30
=.85, 40
=88,=50 -=.90
=.66, =.8,
15 25 Z 35 45 55

So, the highest a/ z ratio is i.e. .9

So, we keep one unit of this element in the knapsack.

So, x=1 and zsXs = 55 x 1=55, a_X, = 50xl=50 and M, = M- zsX; = 100-55 = 45
Now, next highest value of a/z; is as/z4
Ifx, =1 then zxX, =45x1=45 and ax=40xl=40
So, M, = M-ZX4=45 45=0
So, the knapsack is full and then maximum profit is
=asXs t ax4
=50+40 =90
Similarly, we may consider that the highest profitable item gives the highest profit. Then
we insert the highest profitable item to the knapsack first and then next highest itemand
SO on.

So, xs > X4 > X; > X, > X|·

First we insert the 5-th element into the knapsack because it is the highest profitable
element.
So, xs = l and zsxs =55 x 1=55, a_Xs = 50xl=50 and M= M-zNs = 100-55 45
Next, we insert the 4-th element into the knapsack because it is the next highest protitable
element.
So, x4 = 1and zx =45x1 = 45 and a,x=40x1=40and M, = M- Z4N 4S - 45 =0
So, the knapsack is fulland then maximum profit is
= asXs t ax4
-50+40 =90
DAA-53
 POPULAR PUBLICATIONS

Similarly, we may consider that the lowest weight item gives the highest profit because,
we can insert more weight to the knapsack. Then we insert the lowest weight item to the
knapsack first and then next highest item and so on.
So, x >X¡ > Xg > x > Xs.
First we insert the x, element into the knapsack because it is the lowest weight element.
So, x l and zX = 15 >x |=15, a,X, = 10x|=10 and M, = M-z,X) = 100-15= 85
weight
Next, we insert the x element into the knapsack because it is the next lowest
element.
-25 = 60
So, X Fland zX, =25xl=25 and aX,=20x1=20 and M, = M-z2X) = 85 weight
Next, we insert the x; element into the knapsack because it is the next lowest
element.
=25
So, Xg =land z;X, =35xl =35 and ax;=30xl=30 and M, = M,-Z3X3 = 60-35 lowest weight
Next, we insert the xË element into the knapsack because it is the next
element.
M4 = M3 -
So, x4 25 745=0.55 and zX =45x25 /45 = 25 and a_x=40x 0.55=22 and
ZXj= 25 -25 =0
So, the knapsack is full and then maximum profit is
=ax t a t t ar, t ar4
= 10+20+30+22=82

b)What is the difference between dynamic programming and greedy method?

WBUT 2007, 2008, 2012, 2017, 2019]
Answer:
Greedy method is an algorithm that always takes the best immediate, or local, solution
while finding an answer. Greedy algorithms find the overall, or globally, optimal solution
for some optimization problems, but may find less-than-optimal solutions for some
instances of other problems.
Sothe di fference between Greedy method and Dynamic Programming are,
Both techniques are optimization techniques, and both build solutions from a
collection of choices of individual elements.
The greedy method computes its solution by making its choices in a serial forward
fashion, never looking back or revising previous choices.
Dynamic programming computes its solution bottom up by synthesizing them from
smaller subsolutions, and by trying many possibilities and choices before it arrives at
the optimal set of choices.
There is no a priori test by which one can tell if the Greedy method will lead to an
optimal solution.
By contrast, there is a prior test for Dynamic Programming, called ThePrinciple of
Optimality(A problem is said to satisfy the Principle of Optimality if the subsolutions
of an optimal solution of the problem are themselves optimal solutions for their
subproblems.), which can say if Dynamic Programming will lead to an optimal
solution.

DAA-54
 DESIGN AND ANALYSIS OF ALGORITHMS

& a) Find the minimum number of operations required for the following matrix
chain multiplication using dynamic programming:
a(0x 20)" B(20xS0)"c(50x)*D(x100) WBUT 2008, 2013, 2015]
Answer:
We can represent A, A;, As, A, in such a way, that,
A

A pN P4
Where, =10, p=20, p: =50, P: =1, py= 100
Now,
ml, 1]= 0
m[ 2, 2] = 0
m3,3] =0
m[ 4,4] = 0
This willhappen when we parenthesize in the following order
(A (A:) (A). (A).
Next, we can find out, that
m[l, 2] = m[1,1]+ m[ 2, 2] +po. P1 P2
=0+ 0+ 10.20.50
= 10000
i.e.the parenthesis is (AjAz)
m[2, 3] = m[2,2]+ m[ 3, 3] +P1 P2 P3
=0+0+ 20.50.1
= 1000
ie. the parenthesis is (Az As).
m[3, 4] = m[3,3] + m[4, 4] +P2· Ps PA
= 0+ 0+ 50.1.100
= 5000
ie. the parenthesis is (AsA4).
Now, we can calculate the following
m[1,1] + m[ 2, 3] + Po P P:
m[l, 3]= min
m[1,2] + m[3, 3] + Po P2 Ps
0+1000+10.20.1
= min
10000 + 0+10.50.1
1200
= min
10500
= 1200
Now, we can parenthesize AA,A, either (A¡AXA)) or ((A)(AA)). But the minimum
scalar multiplication will occur for ((A)(AzA)).

DAA-55
 POPULAR PUBLICATIONS
m[ 2, 4] = min m[ 2, 2] + m[3, 4] + P, -P: P.
m[ 2, 3] + m[ 4, 4] + P, P -Ps
min 0+5000+ 20.50.100
1000 +0 + 20.1.100
min [105000
3000
= 3000
NOW, we can parenthesis A,A,A,
scalar multiplication will occur for either ((A,ANA)) or ((A:XAJA)). But the minimum
Now, we get the final
parenthesis. ((A;A;XA).
m[ 1, 1]+ m[ 2,4] + Po P Pa
m[1,4]= min m[1, 2] +m[ 3, 4] + P. P: P
m[ 1,3] + m[ 4, 4] + Po P, P
0+3000 +10.20.100
min 10000 + 5000 + 10.50.100
1200 + 0 +10.1.100
23000
= min 65000
2200
= 2200
So, The minimum scalar multiplication will occur for ((AA; A,XA,)) and the total
number of scalar multiplication are 2200.
b) Give an algorithm for matrix-chain multiplication.
Answer: WBUT 2008, 2009, 2010]
Refer to Question No. 7 of Short Answer Type Questions.
7. Design a backtracking
Hamiltonian graph. What is thealgorithm to find all the Hamiltonian cycles in a
worst-case time complexity of the algorithm?
Answer: WBUT 2008, 2013]
The following algorithms find
method. Hamiltonian cycles from a graph by applying backtracking
Search node(k)
{
Step 1 while ((x[k] + 1) mod (n+1)!= o):
Step 1.1 if (G[ x[k-1], x[kj ] # 0) then
Step 1.1.1 for j - 1 to k-1 do
DAA-56
 DESIGN AND ANALYSIS OF ALGORITHMS

Step 1.1.1.1 if (x[3] x(k]) then

Step 1.1.1.2 return 0 :
)
Step 1.1.2 i f ( j- k) then
Step 1.1.2.1 if ((k<n) or (k=n) and G[ x(n], x(1) * 0) then
Step 1.1.2.2 return k;

Step 2 else
Step 2.1 return ( " no path");

Hamiltonian(k)
Step 1 while( Search_node( k) != 0)
Step 1.1 if ( x[k]- n )then
Step 1.1.1 return ( x[1: n] ) ;
Step 1.2 else
Step 1.2.1 Hamiltonian (k+1);

Complexity of Hamiltonian cycle algorithm

The time taken to scan n vertices is O(n) and O(n) time to extend all forced degree two
paths. Since the iterations terminate unless a new vertex of degree two is created, at most
n iterations can occur. At most O(m)edges can be deleted.
(O(m) and the next branch is taken. Thus, an easy upper bound on the pruning time for a
node searching from a vertex of degreedis O(d(n'+ m)), but this is overly pessimistie.
Note that along any branch from the root of the search tree to a leaf, at most n vertices
can be converted to degree 2. Also note that along each branch each edge can be deleted
at most once. If the degree is high we seldom take more than a few branches before
succesS.

The implementation is such that when several vertices have two neighbors of degree two
at the beginning of an iteration, all redundant edges are removed in a single pass taking
time proportional ton plus the number of edges removed and checked. In practice, on a
graph G, it typically takes O(n + m) time per search node on simple Hamiltonian
instances.

DAA-S7
 POFULAR PUBLICATIONS

8. Findthe optimalsolution for the fractional Knapsack problem given below:

w{5,10, 20,30,40}
v={30,20,100,90, 160}
The knapsack capacity, W= 60 (WBUT 2008]
Answer:
Here v, is the profit and w; is the weight of the each knapsack elements.
So, according tothe Greedy Knapsack problem,
Vi/W= 30/5 = 6
V/ wË = 20/10=2
V/ W= 100/20 =5
v/ W=90/30 =3
vs/ W; = 160/40 = 4
We consider that somie traction xi, 0 <xsl ofthe object i is kept into the knapsack.
The highest ratio is v1/ wË 6 and insert one unit of w; =5
So, x =l, x W| 5, X|. VË =30 and W= W- X.W, = 605= 55
Next highest ratio is v/ w3 =5and insert one unit of ws =20
So, x3 = l, X3 .W3 = 20, X3 . V3 =100 and W= W-x, .W; = 55 - 20=35
Next highest ratio is vs/ Ws =4 and insert fractional part of ws.
So, xs =35 /40 =7 / 8. So, x,=7/S, N, .W, =40= 35, Xg.Vý =*160 =140 and
W=W- Xs .Ws =35 - 35 =0
So, the knapsack is full and then maximum profit is
= X . VËt x3. V3 t x_. Vs= 30 + 100+ 140 =270
9. a) State the general knapsack problem. Write a greedy algorithm forthis problem
and derive its time complexity. [WBUT 2009, 2016]
Answer:
The Knapsack problem states that we have to fill a knapsack having constant weight,
with some objects having different weights and different profit values. We have to fill up
the knapsack with objects in such a way that the total weight of selected objects does not
cross the limit of the knapsack and we get the maximumn profit.
Suppose,
The capacity of the knapsack is C.
There aren many objects. An individual object is represeated by I
Weight of i-th object is z,, 1sI<n. where i-1,2,...n.
Profit for i-th object is a,, 1 sI<n
We can put maximum one unit of each object in
that object. So, we consider that some the knapsack or some fractional part of
knapsack. fraction X, 0Sx<1 of the object I is kept into the
Now, the weight of the knapsack
define this problem as:
is."z,x, and profit is A=)"ax,. So we can
DAA-58
 DESIGN AND ANALYSIS OF ALGORITHMS

Maximize A="a,x, ...(1)

Subject to 'sC ...(2)
And 0<xs 1, 0<I<n

Algorithm of Knapsackproblem values

To generate an algorithm to solve knapsack problem, first we consider that all the
of a;/ z, of the i-th element are arranged in decreasing order. Two arrays a[l:n] and z[l:n]
are used for maintaining profit and weight of n objects in such a way that ali] / z[ij>
a[i+1]/z[i+1] respectively. M isthe knapsack size and x[1:n] is the solution vector.
Knapsack (M, n)
Step 1for I + 1 to n do

Step 1.1x[i] + 0.0;

Step 2 u - M;
Step 3 for I + to n do

Step 3.1 if z [i] > u then

Step 3.1.1 break;
Step 3.2 elge
Step 3.2.1 x [i] + 1.0,;
Step 3.2.2. u + u - z[il,

Step 4 if ISn then

Step 4.1 x[i] + u/z [i] ;
Step 5 else

Step 5:1 for I 1 to n o

Step 5.1.1 print + x[i];

of the
Time complexity of knapsack problem is O(nW) [W is the maximum weight
knapsack].
15, 7, 6, 18,
b) Given the weight vector (2, 3, 5, 7, 1,4, 1) and the profitvector (10, 5,
solutions including
3) and aknapsack of capacity 15, find at least three feasible WBUT 2009, 2016]
optimal one for the knapsack problem of seven objects.
Answer:
To find the optimal solutions we apply third method among the above, i.e.,
keep those
elements whose a/z; is maximum into the knapsack.
[Here a=value andz= weight]

DAA-59
 POPULAR PUBLICATIONS
10
Now, 40s. 4 9.5-;
==3, Z 3
-=1.67, Z 5
3
B_4.5,==3
Z4 as6, 1
Z6
So, the highest a, /z ratio is as ie. 6
4 1

So, we keep one unit of this element in the knapsack.

DO, Xs=I and z_X, =1 x1l=1. a-X, = 6xl=6 and M, = M-Z_Xs = 13-1= 14
Now, next highest value of a/z, isa/z1
Ifx = 1 then zX =2×1=2 and a,x=10xl=10
So, M, = M-zX = 142= 12
Next highest value of a/z, is açlz,
If x, = 1 then z6X7 =4x1=4 and aXs = 18xl=18and
M3 = M,-Z7Xç 124 =8
Thenext highest value of a: / z: is aal Za or a, /Z, both are same. So we can choose any
one. Suppose we choose a,/z, for knapsack.
If x, = l then z,.X, = 1xl=l and ax, =3xl=3 and
M4 = M3 - Z;X,.=8-1=7
The next highest value is a3/ Z3
If x, = l then z3X3 = 5x1 =5and aX, = 15xl = 15 and Ms =M-Z,X3 =7-5 =2.
The next highest value is a,/z
If x, = 1l then z,x,= 3x1 =3 which exceeds the value of knapsack. So, we have to put the
fractional part of X, to the knapsack, i.e., remaining part of knapsack is 2.
So, X, =Now, zX, =3 x=2, a,x, =5x=3.33 and M6 = Ms- Z,X,
3 3 3 =2-2=0
So, the knapsack is full and then maximum profit is.
=a_Xs + ajx1taçxG + ajx, + asX3 t
a,X2-6+10+18+3+15+3.33 =55.33
10. Apply backtracking technique to solve the
following graph. 3-colouring problem for the
WBUT 2009, 2011, 2016]

Fig: 1
Answer:
In the graph of figure 1, the
number of vertices is nS and suppose we
using three colors i.e., k=3 have to color it
Let us denote three colors by cl, c2, c3.

DAA-60
 DESIGNAND ANALYSIS OF ALGORITHMS

Suppose allcolors of five nodes 1, 2, 3,4, 5store in an array A[]. The index of each aray
element shows the vertex number and content of each array element denotes the
respective color of the node. So the index of A[i] i.e., Irepresents the vertex of graph G.
We start the assigning color to the first node of the graph. Applying backtracking method
we can use difYerent color for different nodes. So, we get

AU]-c1
A(0]

AA-c2/ A]-C3 A-c1/ AZ-c3

AB-C3 AB]-C3 AB]= C1

AB]-C2

A[4 A[4 A(4-C3 A[4

A[4-C3 -C1 A(4-C -C/ C2
A4-c -C2

A) A(
AJ]-C2 A]-C2| =C3 -C3
AS]-C1 A(S]=C1 -C3 =3

A[!]
=C3

AA-C1 A- c

AB]-c2 A(33-C1

A(4 A(4
A(4-C2 A(4-C "C3

A ASI
A]-C1 A(J]=C1 -C2 C2

DAA-61
 POPULAR PUBLICATIONS
11. Write the worst case and
algorithm
case time comnplexities of Quick sort. Find the best case,
of this algorithm.
average
WBUT 2009, 2013, 20141
Answer:
The following
procedures form the quick.sort algorithm.
QuickSort
{ (A, p, r) together
i£ p < r then
q+ Partition (A, p,
Quick Sort (A, p, )ir);
Quick Sort (A, g + 1, r)i

Algorithm for partition

Partition (A, p, r)
initialize x + A[p];
i + p-1, j+ rt1;
while (i < j)
while (A[--j] > x)
while (A[++i] <x)
{
if (i < j) then,
Exchange (A[il, A[j]);

return j;

Exchange(A, I, i)
p + A[il;
A[i] A[j];
A[j] Pi
}
Partition selects the first key x Ap] as a pivot key about
which the
Ifx <Apl, A[p] willmove towards the left of the pivot, otherwise ifarray
x
is partitioned.
move towards the right of the pivot key x. >ADl, Alpl] will
Complexity Analysis
Best case
In the best case, the pivot is in the
middle
To simplify the equations, we assume thatposition of the
the two sub array.
half the length of the original one. So, we arrays are each.exactly
(independent of n) and n 2 with T(1) =1get T(n) = 2T(n/2) +cn, C>0 constant
DAA-62
 DESIGN AND ANALYSIS OF ALGORITHMS

This is very similar tothe formula for Merge sort, and a similar analysis leads to
Tn) =cn log,n +n which is O(n log2 n).
Average case: We assume that each of the sizes of the left partitions are equally
likely, and hence each has probability 1/n.
With this assumption, the average value of T(i), and hence also of T(n-i-1), is
(T(0) + T(1)+ ... +T(n-1)/n
Naturally, our recurrence relation becomes
T(n) =2(T(0) + T(1) + ... + T(n-1)/n + cn
Multiplying both sides by nwe find nT(n)=2(T(0) +T(1)+... + T(n-1) + cn
Substitution of n by n-1 gives
(n-1)T(n-1) = 2(T(0)+ T(1) +.. +T(n-2)) t c(n-1)
Subtracting the last equation from the previous one, we get nT(n) - (n-1)T(n-1)
= 2T(n-1) + 2cn - c
Rearranging and ignoring constant c, we arrive at nT(n)=(n+1)T(n-1) +2cn
Division through out by n(nt1) gives
T(n)/(n+1) =T(n-1)/n +2c/(n+1)
Hence, T(n-1 )/n = T(n-2)(n-1 ) + 2c/n
Similarly T(2)/3 =T(1y2 + 2c/3
Thus
T(n)/(n+1) =T(1)/2+2c(1/3 + +..+1/(n+1))
The sumn in brackets is about log (n+1) + y - 3/2, where y is Euler's constant,
which is approximately 0.577.
So, T(n)/(n+1)= 0(log 2n) and thus T(n)=0(n log 2n)
Worst case: In quick sort technique, the worst case condition arises when the
elements of the array are already sorted.
If the pivot is always the smallest element, then always I =0
We ignore the term T0)=1, so the recurrence relation is T(n) =Tn-1) + cn
So, T(n-1)-T(-2)+c(n-1)and so on until we get T(2)-T(I )+(2)
Substituting backwards, we get T(n) =T(1) +c(n +...+2) =0(n)
It may be noted that this case happens if we always take the pivot to be the first element
in the array and the array is already sorted.
12. What is Heap property? Write an algorithm to make a Heap containing
elements. Then, show that how can you insert an element into a Heap. Then, write
the algorithm of Heap sort and find the running time of this algorithm. Write an
algorithm to find the existence of an element into a Heap. WBUT 2010]
OR,
a) What is Heap property?
b) Write an algorithm of Heap Sort.
c) Find the running time of this algorithm. WBUT 2018,2019]
Answer:
Heap: Aheap is a complete binary tree with the following properties:
1. Ifit isa max heap then the value of each node is greater than the value of its children.
2. If it is a min heap then the value of each node is less than the value of its children.
DAA-63
 POPULAR PUBLICATIONS
BUILD HEAP
Algorithm ) algorithm
to make a Heap constructs acomplete heap tree where each node of the tree
is present at its proper position with the help of Heapify () algorithm. BUILD HEAP ()
breaks the total length of the aray intotwo equal parts. So, the elements in the sub arrays

A[l, ...[n/2|] and Afl n/2 +1..n] are all leaf nodes. Now it compares each no
from length [AV2 down to I with the help of Heapify ). The bottom-up order of
sub tree rooted at each of the children are heap, before
processing guarantees that the
Heapify0 is run at their parent node.
BUILD HEAP(A, length)
heap-size (A) - length [AJ
fori- length[A]/2 downto Ido
Heapify (A, i);

Heapify (A, i)
{
I-let [ij
r+right
ifl< heap-size [A] and A[] >Ai] then
largest -l
else
largest -i
ifr <heap-size [A]and A[r]> A[largest] then
largest r
if largest#i then
exchange A(i] A[largest]
Heapify (A, largest)

This Heapify ) algorithm is totally based on the

array which has already been discussed earlier. procedure to arrange a heap in a l-D
Heapify) algorithm set each node to its appropriate Ifposition.
the above rule is violated, then
Insert an element into the Heap
Suppose we have a heap as follows

Max hep
Fig: 1
DAA-64
 DESIGN AND ANALYSIS OF ALGORITHMS

1. First, we add the

Suppose, we warnt to add a node with key 15 in to the heap in figure This is to ensure
node to the tree at the next spot available at the lowest level of the tree.
that the tree remains complete. Thus the configuration becomes,
20

Insert element lS to the he ap

Fig: 2
However, after inserting element 15, as shown in figure 2, we find that the heap property
is not maintained any more. To ensure the heap property preserved, we have perform a
in
few steps to convert it into a max heap. We interchange elements 15 and 8 as evident
figure 3.
20

Interchange between 15 and 8

Fig: 3
Next, another swap is required with respect to elements 14 and 15 in figure 3 to obtain a
situation shown in figure 4. This is for preservation of the heap property.

Interchange between 15 and 14

Fig: 4
Now we have completed aheap tree and placed 1Sin its appropriate position. Nofurther
move is required because 15< 20. But note that the left child having value 1, is less than
right child having value 8, of the sub-tree rooted at the node containing value 14. In our
subsequent discussion, we shall see how we can sort out this problem.

DAA-65
 PUBLICATIONS
POPULAR
a
BUILD-HEAP)to build atmax heap
Heap Sort algorithm using
procedure
of the arrayis stored the root
starts by element (the last
The heap sort algorithm Since the
maximum exchanging it with A[n]
elements
on the input array A[1..
n].
correct final position by then the remaining can
A[|), it can be put
into its heap
node n from the may violatethe heap property.
So it
now discard
element in A). If we new element atthe root
heap. The
be converted into further.
necessary to restore the heap property
IS HEAPSORT (A)

BUILD_HEAP (4);
down to 2 do
for i -length (4)
exchange A[1] A[]
1
heap-size[4]- heap-size [4]-
Heapify (A, 1);

Çomplexity at most O (n log 2 n). Since the call to

procedure takes time takes time O
The HEAPSORT 0 time O (n) and each of the n -1 calls to Heapify ()complexity of
BUILD HEAP ()takes discussed earlier, so the worst case time
already
(log n) which we have
heap sort is O (n log2 n).
coloring problem and write the algorithm. [WBUT 2011]
13.a) Explain the graph
Answer:
Type Questions.
Refer to QuestionNo. 3(i) of Long Answer
single source shortest path problem for the following graph
b) Solve the
Dijkstra's algorithm. [WBUT 2011]
considering 1' as the source vertex using

10

13
A

3
2

Answer:
Initially: Vertex 1is the source vertex and we have to find out the shortest distance froml
vertex 1 to all the remaining vertices.
So, the distances from vertex 1to all other vertices are given below
S= {1},D[2] = 5, D[3] =2, D(4]= 10 D[S] =6

DAA-66
 DESIGNAND ANALYSIS OF ALGORITHMS

Iteration 1:Now, vertex 1to vertex 3 is the shortest distance and the distance is 3. Now,
we have to find out the shortest distance of the other vertices.
Select w=3, so that S ={1, 3}
D[2] = min(5, D[3]+ C[3, 2]) =min( 1, 2+13) =5
D[4]= min(10, D[3]+ C[3, 4]) = min( 1, 2+9)= 10
D[S] = min(6, D[3]+ C[3, 5]) = min(6, 2+3)= 5
Iteration 2: Select w= 5, so that S={1, 3, 5}
D[2] = min(5, D[S]+ C[5, 2]) = min(5, 5to)5
D[4]= min(10, D[5] + C[5, 4]) =min(10, 5+4) =9
Iteration3: Select w=4, so that S={1,3, 5, 4}
D[2] = min(5, D[4]+ C[4, 2|) = min(5, 9+5) =5
Iteration4: Select w=2, so that S={1, 2}
D[2] =5
So, the shortest distances from vertex 1 to other vertices are given below.
i) DI2] =5. i.e. the shortest distance from vertex 1 to vertex 2 is 1 and the path is 1 ’2
ii) DI3]=2 i.e. the shortest distance from vertex 1to vertex 3 is 2 and the path is 1 ’ 3
iii) D[4] =9 i.e. the shortest distance from vertex 1to vertex 4 is 1 and the path is
1’3’ 5’ 4
iv) D[5] =5 i.e. the shortest distance from vertex 1 to vertex 5 is 5 and the path is
1’35

14. Solve the following Knapsack problem with the given conditions: n=3 weight
of the Knapsack M=20 ) Profits (PiPz»P)=(25,24,15) and weight
(",, W,, w,)=(18,15,10). WBUT 2011, 2015]
Answer:
To find the optimal solutions we apply third method among the above, i.e., keep those
elements whose p/w;is maximum into the knapsack.
[Here p, = profit value and z = weight]
P 25 P 24-=1.6, P_15
Now, =1.38, -=1.5
18 W 15 W, 10
So, the highest p;/ w; ratio is 1.6
So, we keep one unit of this element in the knapsack.
So, X, =land wa"X) = 15 xl=1,p2X, -24xl=24 and M, = M- W,"X)=20-15 =5
Now, next highest value is 1.5
If x, = 1 then w;x3= 10x1 = 10which exceeds the weight of the knapsack. So, we have to
put the fractional part of x, to the knapsack, i.e., remaining part of knapsack is 5.
So, x, ==0.5
10

DAA-67
 POPULAR PUBLICATIONS
=5-5 =0
=15x=7.5 and M,=M,-W;X,
Now, W3"Xy =10x =5,p,x, 10 = 24+7.5 =33.5
10
then maximum profit is =P:Xgt P3X3
So, the knapsack is full and
to solve the following graph-coloring problem
15. a) Apply backtracking technique WBUT 2013]
and also generate the state space tree:

Answer:
the graph such
Here the chromatic number is 4. i.e. 4 different colors are required to colorconsidered four
that no two adjacency vertices are same color. In the figure 1, we have
different colors are cl, c2, c3, c4 and five vertices of the graph is represented by A[1].
A[2], A(3], A[4] and A[5].

A(I]=C1

AP]-C2
C4

Ap-C3 C2

AKFC4
C3

C3
AB]-C cA

Fig 1: State space tree of the

graph
[Try todraw the remaining three parts of the treel

DAA-68
 ALGORITHMS
DESIGN AND ANALYSIS OF

problem. Find its time-complexity and explain

n-queen's
b)Write an algorithm for
example.
WBUT 2013]
the algorithm using an
Answer: Questions.
Part: Refer to Question No. 15 of ShortAnswer Type
1
2nd Part:
n-queen problem, which happens to be NP-complete (which
Our simple example is the On an n xn chessboard, a queen can move any number of
means computationally hard). and digonally. Fig: 1(a) illustrates a possible
squares up, down, to the right, to the left, "safe" positions for n
move for a queen for a case of n =5. The problem is to determine n
position means that none of the queens can move to a square occupied by
queens. A safe
move. Obvously there must be one and only one queen in each
another queen in only one are in a row or column, then one would
be
two or more queens
row and column. (If or coloumn, there must be a row or
column
another, if no queens are in a row
attacked by each
more than one queen.) Similarly, there must be at most one queen in
that has diagonal direction). Fig: (b) is a
diagonal direction (since there can be no queen in a
unique for a specific value of n.
solution for n =5; generally, a solution is not

3 3

2 2

2 3 4 1 2 3 4 5

(a) (b)
Fig: 1The n-queen problem illustration for n=5.
(a) A possible move of a queen. (b) A solution

16. Solve the APSP problem using Floyd-Warshall's algorithm for the following
graph: WBUT 2013]
3
A

Answer: 6

The sequence of matrices D and IT* computed by the Floyd-Warshall's algorithm for
the graph isgiven below.
DAA-69
POPULAR PUBLICATIONS
O NIL 1 1 NIL
NIL NIL NIL 2 2
80 3 8
28 1 7 3 NIL NIL
0 I°= NIL
w - NIL -
-
p =| o 4 0 0 4 NIL - 4 NIL
NIL
o 8oo 8-5 0 NIL NIL NIL NIL
co 6 0 1 1 NIL
NIL
80 3 8 4 NIL NL NIL 2 2
8 1
I = NIL 3 NIL NIL NIL
D =N
o 4
82 5 o8
-5 0 -2
4 -4 NIL
NIL NIL NIL
o 6 0 NIL)
o 84 -4 NIL 1 1 2
80 3
78 1 7 NIL NIL NIL 2 2
0
D = 4 0 5 1l II) = IL 3 NIL 2 2
o
2 85 -5
8 0 -2 4
NIL NIL
1
-NIL4 NIL
o 6 0 5 NIL)
80 3 8 4 -4) (NIL 1 2
8o 0 0 1 7 NIL NIL NIL 2 2
D =o 4 0 5 11 IT = NIL 3 NIL 2 2
82 -1 -5 0 -2 4 3 4 NIL 1
06 0 MIL NIL NIL 5 NIL)
(0 3 -1 4 -4
NIL 1 4 2 1
3 0 4 1 -1
D =7 4 4. NIL 4 2 1
0. 5 3 II = 4 3 NIL 2 1
2 -1 -5 0 -2
4 3 4 NIL 1
8 S 1 6 0 4 3 4 5 NIL)
(0 1 3 2
3 0 -4 1 -1 (NIL 3 4 5
DS) =7 4 0 5 3
4 NIL 4 2 1
2 -1 -5 0 4 3 NIL 2
-2
|8 5 1 6 0 4 3 4 NIL 1
4 3 4 5 NIL)

DAA-70
 DESIGN AND ANALYSIS OF ALGORITHMS

17. a) Perform the PARTITION operation once (one time) on the following array as
per the requirement of the quicksort algorithm, assuming the last element of the
array to be the pivot element. Clearly mention the steps.
arr[]= (2, 8, 7, 1,3, 5, 6,4} [WBUT 2014]
Answer:
i pJ
(a) 287| 135 64
p.i j
(b) 28713|56|4

(c) 28713|5|64
p.i
(d) 287 13564

pi
(e) 2173B564
()

(g) 2 1 3 87 564

(h) 2 1|3875|64
p
)
2|134|5|6|9
The operation of PARTITION on a sample array. Lightly shaded array elements are all in
the first partition with values no greater than x. Heavily shaded elements are in the
second partition with values greater than x. The un-shaded elements have not yet been
put in one of the first two partitions, and the final white element is the pivot. (a) The
initial array and variable setings. None of the elements have been placed in either of the
first two partitions. (b) The value 2 is "swapped with itself" and put in the partition of
smaller. values. (cd) The values 8 and 7 are added to the partition of larger values.
(e) The values 1and 8are swapped, and the smaller partition grows. () The values 3 and
7 are swapped, and the smaller partition grows. (gh) The larger partition grows to
include 5 and 6 and the loop terminates. (i) In lines 7-8, the pivot element is Swapped sO
that it lies between the two partitions.

DAA-71