MODULE II

ALGORITHM DESIGN TECHNIQUES

1. DIVIDE AND CONQUER

1.1 Binary search

1.2 Strassen’s Matrix Multiplication

1.3 Finding the Maximum and Minimum

2. GREEDY METHOD

2.1 Knapsack Problem

2.2 Minimum Cost Spanning Tree (MCST) Problem

2.2.1 Kruskal’s Algorithm

2.2.2 Prim’s Algorithm

PraveenKumar P K, UIT Kollam

ALGORITHM DESIGN TECHNIQUES

2. DIVIDE AND CONQUER

In divide and conquer approach, the problem in hand, is divided into smaller sub-problems
and then each problem is solved independently. When we keep on dividing the sub-problems
into even smaller sub-problems, we may eventually reach a stage where no more division is
possible. Those "atomic" smallest possible sub-problem (fractions) are solved. The solution
of all sub-problems is finally merged in order to obtain the solution of an original problem. A
divide-and-conquer algorithm as having three parts:
1. Divide/Break the problem into a number of subproblems that are smaller instances of
the same problem.
2. Conquer/Solve the subproblems by solving them recursively. If they are small enough,
solve the subproblems as base cases.
3. Combine/Merge the solutions to the subproblems into the solution for the original
problem.

Examples
The following computer algorithms are based on divide-and-conquer programming approach
 Merge Sort
 Quick Sort
 Binary Search
 Strassen's Matrix Multiplication

PraveenKumar P K, UIT Kollam

  Closest pair (points)
There are various ways available to solve any computer problem, but the mentioned are a
good example of divide and conquer approach.
1.1 Binary search
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search
algorithm works on the principle of divide and conquer. For this algorithm to work properly,
the data collection should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the
collection. If a match occurs, then the index of item is returned. If the middle item is
greater than the item, then the item is searched in the sub-array to the left of the middle
item. Otherwise, the item is searched for in the sub-array to the right of the middle item.
This process continues on the sub-array as well until the size of the sub array reduces to
zero.
How Binary Search Works?
For a binary search to work, it is mandatory for the target array to be sorted. We shall
learn the process of binary search with a pictorial example. The following is our sorted
array and let us assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We
find that the value at location 4 is 27, which is not a match. As the value is greater than 27
and we have a sorted array, so we also know that the target value must be in the upper
portion of the array.

We change our low to mid + 1 and find the new mid value again.

low = mid + 1
mid = low + (high - low) / 2

PraveenKumar P K, UIT Kollam

Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is less than what we are looking for.
So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be
made to very less numbers.

Pseudocode
The pseudocode of binary search algorithms should look like this −

Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound

PraveenKumar P K, UIT Kollam

 EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure

Analysis of Binary search

Let us assume for the moment that the size of the array is a power of 2, say 2 k. Each time
in the while loop, when we examine the middle element, we cut the size of the sub-array into
half. So before the 1st iteration size of the array is 2k. After the 1st iteration size of the
sub-array of our interest is: 2k-1
After the 2nd iteration size of the sub-array of our interest is: 2 k-2
…………………………
………………………..
After kththe .iteration size of the sub-array of our interest is : 2k-k=1
So we stop after the next iteration. Thus we have at most( k+1)= (logn+1)iterations.
Since with each iteration, we perform a constant amount of work: Computing a mid point and
few comparisons. So overall, for an array of size n, we perform
C.(logn+1)=O(logn)comparisions.
1.2 Strassen’s Matrix Multiplication
Given two square matrices A and B of size n x n each, find their multiplication matrix.

Naive Method
Following is a simple way to multiply two matrices.

void multiply(int A[][N], int B[][N], int C[][N])

{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
PraveenKumar P K, UIT Kollam
 }
}
}
}
Time Complexity of above method is O(N3).

Divide and Conquer

Following is simple Divide and Conquer method to multiply two square matrices.
1) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below
diagram.
2) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.

In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4
additions. Addition of two matrices takes O(N 2) time. So the time complexity can be written
as

T(N) = 8T(N/2) + O(N2)

From Master's Theorem, time complexity of above method is O(N 3)
which is unfortunately same as the above naive method.

Strassen’s method

For providing optimality in multiplication of matrices Strassen’s method was published by V.

Strassen in 1969.

In the above divide and conquer method, the main component for high time complexity is 8
recursive calls. The idea of Strassen’s method is to reduce the number of recursive calls to
7. Strassen’s method is similar to above simple divide and conquer method in the sense that
this method also divide matrices to sub-matrices of size N/2 x N/2 as shown in the above
diagram, but in Strassen’s method, the four sub-matrices of result are calculated using
following formulae.

PraveenKumar P K, UIT Kollam

Time Complexity of Strassen’s Method
Addition and Subtraction of two matrices takes O(N 2) time. So time complexity can be
written as

X(n) = 7 X(n/2) for n>1, X(1)=1

Since n = 2k

X(2k) = 7 X(2k-1) = 7[7 X(2k-2)] = ……

=7kX(2k-k) = 7k

Since K =log2n

X(n) = 7log2n = nlog27 = n2.807

Which is less than n3 as required by Naive Method.

Generally Strassen’s Method is not preferred for practical applications for following
reasons.
1) The constants used in Strassen’s method are high and for a typical application Naive
method works better.
2) For Sparse matrices, there are better methods especially designed for them.
3) The submatrices in recursion take extra space.
4) Because of the limited precision of computer arithmetic on noninteger values, larger
errors accumulate in Strassen’s algorithm than in Naive Method
1.3 Finding the Maximum and Minimum

PraveenKumar P K, UIT Kollam

Let us consider another simple problem that can be solved by the divide and conquer
technique. The problem is to find out the maximum and minimum items in a set of n
elements. Following algorithm is a straight forward algorithm to accomplish this.
Algorithm for straight forward maximum and minimum
StraightMaxMin(a,n,max,min)
// set max to the maximum and min to the minimum of a[1:n].
{
max := min := a[1];
for i := 2 to n do
{
if(a[i] > max) then max := a[i];
if(a[i] < min) then min := a[i];
}
}
Analyzing the Straight Forward Method
In analyzing the time complexity of this algorithm, we have to concentrate on the number of
element comparisons. This algorithm requires 2(n-1) element comparisons in the best,
average, and worst cases. An immediate improvement is possible by realizing that the
comparison a[i] < min is necessary only when a[i]>max is false. Hence we can replace the
content of the for loop by
if(a[i] > max) then max := a[i];
else if(a[i] < min) then min := a[i];
Now the Best case occurs when the elements are in increasing order. The number of
element comparisons is n-1. The worst case occurs when the element are in decreasing
order. In this case number of comparisons is 2(n-1). The average number of element
comparisons is less than 2(n-1). On the average, a[i] is greater than max half the time, and
so the average number of comparisons is 3n/2-1.

Finding the Maximum and Minimum using Divide and Conquer strategy
A divide-and-conquer algorithm for this problem would proceed as follows: Let
P=(n,a[i],….,a[j]) denote an arbitrary instance of the problem. Here n is the number of
elements in the list a[i],….,a[j] and we are interested in finding the maximum and minimum of
this list. Let small(P) be true when n ≤ 2. In this case, the maximum and minimum are a[i] if
n= 1. If n = 2, the problem can be solved by making one comparison.
If the list has more than two elements, P has to be divided into smaller instances. For
example, we might divide P into the two instances P1 = (n/2,a[1],….,a[n/2]) and P2 = (n -
n/2,a[n/2 + 1],….,a[n]). After having divided P into two smaller sub problems, we can solve
them by recursively invoking the same divide and conquer algorithm.
Now the question is How can we combine the Solutions for P1 and P2 to obtain the solution
for P? If MAX(P) and MIN(P) are the maximum and minimum of the elements of P, then
MAX(P) is the larger of MAX(P1) and MAX(P2) also MIN(P) is the smaller of MIN(P1) and
MIN(P2).

PraveenKumar P K, UIT Kollam

Following MaxMin is a recursive algorithm that finds the maximum and minimum of the set
of elements {a(i),a(i+1),…,a(j)}. The situation of set sizes one (i=j) and two (i=j-1) are handled
separately. For sets containing more than two elements, the midpoint is determined and two
new sub problems are generated. When the maxima and minima of this sub problems are
determined, the two maxima are compared and the two minima are compared to achieve the
solution for the entire set.
Algorithm for maximum and minimum using divide-and-conquer
MaxMin(i, j, max, min)
// a[1:n] is a global array. Parameters i and j are integers,
// 1 ≤ i ≤ j ≤ n. The effect is to set max and min to the largest and
// smallest values in a[i:j].
{
if (i=j) then max := min := a[i]; //Small(P)
else if (i=j-1) then // Another case of Small(P)
{
if (a[i] < a[j]) then max := a[j]; min := a[i];
else max := a[i]; min := a[j];
}
else
{
// if P is not small, divide P into sub-problems.
// Find where to split the set.
mid := ( i + j )/2;
// Solve the sub-problems.
MaxMin( i, mid, max, min );
MaxMin( mid+1, j, max1, min1 );
// Combine the solutions.
if (max < max1) then max := max1;
if (min > min1) then min := min1;
}
}
The procedure is initially invoked by the statement MaxMin(1,n,x,y). for this algorithm each
node has four items of information: i, j, max, min.
Suppose we simaulate MaxMin on the following nine elements:
a: [1] [2] [3] [4] [5] [6] [7] [8] [9]
22 13 -5 -8 15 60 17 31 47
A good way of keeping track of recursive calls is to build a tree by adding a node each time
a new call is made. On the array a[ ] above, the following tree is produced.

PraveenKumar P K, UIT Kollam

We see that the root node contains 1 and 9 as the values of i and j corresponding to the
initial call to MaxMin. This execution produces two new call to MaxMin, where i and j have
the values 1, 5 and 6, 9, and thus split the set into two subsets of the same size. From the
tree we can immediately see that the maximum depth of recursion is four (including the
first call).
Complexity
Now what is the number of element comparisons needed for MaxMin? If T(n) represents
this number, then the resulting recurrence relation is

0 n=1
T(n) = 1 n=2
T(n/2) + T(n/2) + 2 n>2

When n is a power of two, n = 2k for some positive integer k, then

T(n) = 2T(n/2) + 2
= 2(2T(n/4) + 2) + 2
= 4T(n/4) + 4 + 2
.
.
.
= 2k-1 T(2) + ∑1 ≤ I ≤ k-1 2i
= 2k-1 + 2k – 2
= 3n/2 – 2 = O(n)
Note that 3n/2 – 2 is the best, average, worst case number of comparison when n is a power
of two.
Comparisons with Straight Forward Method
Compared with the 2n – 2 comparisons for the Straight Forward method, this is a saving of
25% in comparisons. It can be shown that no algorithm based on comparisons uses less than
3n/2 – 2 comparisons.
PraveenKumar P K, UIT Kollam
2. GREEDY METHOD
Greedy algorithms are typically used to solve an optimization problem. An Optimization
problem is one in which, we are given a set of input values, which are required to be either
maximized or minimized w. r. t. some constraints or conditions. Generally an optimization
problem has n inputs (call this set as input domain or Candidate set, C), we are required to
obtain a subset of C (call it solution set, S where S) that satisfies the given constraints or
conditions. Any subset S, which satisfies the given constraints, is called a feasible solution.
We need to find a feasible solution that maximizes or minimizes a given objective function.
The feasible solution that does this is called an optimal solution.

A greedy algorithm proceeds step–by-step, by considering one input at a time. At each

stage, the decision is made regarding whether a particular input (say x) chosen gives an
optimal solution or not. Our choice of selecting input x is being guided by the selection
function (say select). If the inclusion of x gives an optimal solution, then this input x is
added into the partial solution set. On the other hand, if the inclusion of that input x
results in an infeasible solution, then this input x is not added to the partial solution. The
input we tried and rejected is never considered again. When a greedy algorithm works
correctly, the first solution found in this way is always optimal. In brief, at each stage, the
following activities are performed in greedy method:
1. First we select an element, say, from input domain C.
2. Then we check whether the solution set S is feasible or not. That is we check whether x
can be included into the solution set S or not. If yes, then solution set. If no, then this input
x is discarded and not added to the partial solution set S. Initially S is set to empty.
3. Continue until S is filled up (i.e. optimal solution found) or C is exhausted whichever is
earlier.

From the set of feasible solutions, particular solution that satisfies or nearly satisfies the
objective of the function (either maximize or minimize, as the case may be), is called
optimal solution.

Characteristics of greedy algorithm

 Used to solve optimization problem
 Most general, straightforward method to solve a problem.
 Easy to implement, and if exist, are efficient.
 Once any choice of input from C is rejected then it never considered again.
 Do not always yield an optimal solution; but for many problems they do.

Examples
In order to better understanding of greedy algorithms, let us consider some examples:
Suppose we are given Indian currency notes of all denominations, e.g.
{1,2,5,10,20,50,100,500,1000}. The problem is to find the minimum number of currency
notes to make the required amount A, for payment. Further, it is assumed that currency
PraveenKumar P K, UIT Kollam
notes of each denomination are available in sufficient numbers, so that one may choose as
many notes of the same denomination as are required for the purpose of using the minimum
number of notes to make the amount A; Now in the following examples we will notice that
for a problem (discussed above) the greedy algorithm provides a solution (see Case-1),
some other cases, greedy algorithm does not provides a solution, even when a solution by
some other method exist (see Case-2) and sometimes greedy algorithm is not provides an
optimal solution Case-3).
Case-1
Solution: Intuitively, to begin with, we pick up a note of denomination D, satisfying the
conditions.
i) D ≤ 289 and
ii) ii) if D1 is another denomination of a note such that D1 ≤ 289, then D1 ≤ D.
In other words, the picked-up note’s denomination D is the largest among all the
denominations satisfying condition (i) above. The above-mentioned step of picking note of
denomination D, satisfying the above two conditions, is repeated till either the amount of
Rs.289/- is formed or we are clear that we can not make an amount or Rs.289/- out of the
given denominations. We apply the above-mentioned intuitive solution as follows: To deliver
Rs. 289 with minimum number of currency notes, the notes of different denominations are
chosen and rejected as shown below:
Chosen-Note-Denomination Total-Value-So far
100 0+100 ≤ 289
100 100+100 ≤ 289
100 200+100 > 289
50 200+50 ≤ 289
50 250+50 > 289
20 250 + 20 ≤ 289
20 270 + 20 > 289
10 270 + 10 ≤ 289
10 280 + 10 > 289
5 280 + 5 ≤ 289
5 285 + 5 > 289
2 285 + 2 < 289
2 287 + 2 = 289
The above sequence of steps based on Greedy technique, constitutes an algorithm to solve
the problem. To summarize, in the above mentioned solution, we have used the strategy of
choosing, at any stage, the maximum denomination note, subject to the condition that the
sum of the denominations of the chosen notes does not exceed the required amount A =
289.
The above strategy is the essence of greedy technique.
Case 2

PraveenKumar P K, UIT Kollam

Next, we consider an example in which for a given amount A and a set of available
denominations, the greedy algorithm does not provide a solution, even when a solution
by some other method exists. Let us consider a hypothetical country in which notes
available are of only the denominations 20, 30 and 50. We are required to collect an amount
of 90. Attempted solution through above-mentioned strategy of greedy technique:
o First, pick up a note of denomination 50, because 50 ≤ 90. The amount obtained
by adding denominations of all notes picked up so far is 50.
o Next, we can not pick up a note of denomination 50 again. However, if we pick
up another note of denomination 50, then the amount of the picked-up notes
becomes 100, which is greater than 90. Therefore, we do not pick up any note
of denomination 50 or above.
o Therefore, we pick up a note of next denomination, viz., of 30. The amount
made up by the sum of the denominations 50 and 30 is 80, which is less then
90. Therefore, we accept a note of denomination 30.
o Again, we cannot pick up another note of denomination 30, because otherwise
the sum of denominations of picked up notes, becomes 80+30=110, which is
more than 90. Therefore, we do not pick up only note of denomination 30 or
above.
o Next, we attempt to pick up a note of next denomination, viz., 20. But, in that
case the sum of the denomination of the picked up notes becomes 80+20=100,
which is again greater than 90. Therefore, we do not pick up only note of
denomination 20 or above.
o Next, we attempt to pick up a note of still next lesser denomination. However,
there are no more lesser denominations available.
Hence greedy algorithm fails to deliver a solution to the problem. However, by some
other technique, we have the following solution to the problem: First pick up a note of
denomination 50 then two notes each of denomination 20. Thus, we get 90 and it can be
easily seen that at least 3 notes are required to make an amount of 90. Another alternative
solution is to pick up 3 notes each of denomination 30.
Case-3
Next, we consider an example, in which the greedy technique, of course, leads to a
solution, but the solution yielded by greedy technique is not optimal. Again, we consider
a hypothetical country in which notes available are of the only denominations 10, 40 and 60.
We are required to collect an amount of 80. Using the greedy technique, to make an amount
of 80, first, we use a note of denomination 60. For the remaining amount of 20, we can
choose note of only denomination 10. And , finally, for the remaining amount, we choose
another note of denomination 10. Thus, greedy technique suggests the following solution
using 3 notes: 80 = 60 + 10 + 10.
However, the following solution uses only two notes: 80 = 40 + 40
Thus, the solutions suggested by Greedy technique may not be optimal.
Formalization of Greedy technique

PraveenKumar P K, UIT Kollam

In order to solve optimization problem using greedy technique, we need the following data
structures and functions:
1) A candidate set from which a solution is created. It may be set of nodes, edges in
a graph etc. call this set as: C: Set of given values or set of candidates
2) A solution set S (where S subset of C, in which we build up a solution. This
structure contains those candidate values, which are considered and chosen by the greedy
technique to reach a solution. Call this set as: S: Set of selected candidates (or input)
which is used to give optimal solution.
3) A function (say solution) to test whether a given set of candidates give a solution
(not necessarily optimal).
4) A selection function (say select) which chooses the best candidate form C to be
added to the solution set S,
5) A function (say feasible) to test if a set S can be extended to a solution (not
necessarily optimal) and
6) An objective function (say ObjF) which assigns a value to a solution, or a partial
solution.

To better understanding of all above mentioned data structure and functions, consider the
minimum number of notes problem of example1. In that problem:
1) C={1, 2, 5, 10,50,100,500,1000}, which is a list of available notes (in rupees). Here
the set C is a multi-set, rather than set, where the values are repeated.
2) Suppose we want to collect an amount of Rs. 283 (with minimum no. of notes). If we
allow a multi-set rather than set in the sense that values may be repeated, then
S={100,100,50,20,10,2,1}
3) A function solution checks whether a solution is reached or not. However this
function does not check for the optimality of the obtained solution. In case of minimum
number of notes problem, the function solution finds the sum of all values in the multi-set S
and compares with the fixed amount, say Rs. 283. If at any stage S={100,100, 50}, then sum
of the values in the S is 250, which does not equal to the 283, then the function solution
returns “solution not reached”. However, at the later stage, when S={100,100,50,20,10,2,1},
then the sum of values in S equals to the required amount, hence the function solution
returns the message of the form “solution reached”.
4) A function select finds the “best” candidate value (say x) from C, then this value x
are tried to add to the set S. At any stage, value x is added to the set S, if its addition
leads to a partial (feasible) solution. Otherwise, x is rejected. For example, In case of
minimum number of notes problem, for collecting Rs. 283, at the stage when S={100,
100,50}, then first the function select try to add the Rs 50 to S. But by using a function
solution, we can found that the addition of Rs. 50 to S will lead us a infeasible solution,
since the total value now becomes 300 which exceeds Rs. 283. So the value 50 is rejected.
Next, the function select attempts the next lower denomination 20. The value 20 is added
to the set S, since after adding 20, total sum in S is 270, which is less than Rs. 283. Hence,
the value 20 is returned by the function select.

PraveenKumar P K, UIT Kollam

 5) When we select a new value (say x) using select function from set C, then before
adding x to S we check its feasibility. If its addition gives a partial solution, then this value
is added to S. Otherwise it is rejected. The feasibility checking of new selected value is
done by the function feasible. For example, In case of minimum number of notes problem,
for collecting Rs. 283, at the stage when S={100, 100,50}, then first the function select try
to add the Rs 50 to S. But by using a function solution, we can found that the addition of Rs.
50 to S will lead us an infeasible solution, since the total value now becomes 300 which
exceeds Rs. 283. So the value 50 is rejected. Next, the function select attempts the next
lower denomination 20. The value 20 is added to the set S, since after adding 20, total sum
in S is 270, which is less than Rs. 283. Hence feasible.
6) The objective function (say ObjF), gives the value of the solution. For example, In
case of minimum number of notes problem, for collecting Rs. 283; and when
S={100,100,50,20,10,2,1}, then the sum of values in S equals to the required amount 283;
the function ObjF returns the number of notes in S, i.e., the number 7.
A general form for greedy technique can be illustrated as:

PraveenKumar P K, UIT Kollam

2.1 Knapsack Problem
The fractional knapsack problem is defined as:
 Given a list of n objects say {I1,I2,…In} and a Knapsack (or bag).
 Capacity of Knapsack is M.
 Each object Ii has a weight wi and a profit of .
 If a fraction xi (where xi ε {0…1} of an object Ii is placed into a knapsack then a profit
of pixi is earned.
The problem (or Objective) is to fill a knapsack (up to its maximum capacity M) which
maximizes the total profit earned.
Mathematically:

Note that the value of xi will be any value between 0 and 1 (inclusive). If any object Ii is
completely placed into a knapsack then its value is 1 (ie. xi = 1), if we do not pick (or select)
that object to fill into a knapsack then its value is 0 (ie. x i = 1),. Otherwise if we take a
fraction of any object then its value will be any value between 0 and 1.
To understand this problem, consider the following instance of a knapsack problem:
Number object n = 3
Capacity of Knapsack; M=20
(p1, p2, p3)= (25, 24, 15)
(w1, w2, w3)= (18, 15, 10)
To solve this problem, Greedy method may apply any one of the following strategies:
Approach 1: From the remaining objects, select the object with maximum profit that fit
into the knapsack.
Approach 2: From the remaining objects, select the object that has minimum weight and
also fits into knapsack.
Approach 3: From the remaining objects, select the object with maximum pi/wi that fits
into the knapsack.
Let us apply all above 3 approaches on the given knapsack instance:
Approach 1: (selection of object in decreasing order of profit)
In this approach, we select those object first which has maximum profit, then next
maximum profit and so on. Thus we select 1st object (since its profit is 25, which is maximum
among all profits) first to fill into a knapsack, now after filling this object (w 1=18) into
knapsack remaining capacity is now 2 (i.e. 20-18=2). Next we select the 2 ndobject, but its
weight w2 =15, so we take a fraction of this object (i.e. x2=2/15). Now knapsack is full (i.e.

PraveenKumar P K, UIT Kollam

Σi=1 to 3 wixi =20 ) so 3rdobject is not selected. Hence we get total profit Σi=1 to 3 p ixi = 28
units and the solution set (x1, x2, x3) = (1, 2/15, 0)
Approach 2: (Selection of object in increasing order of weights).
In this approach, we select those object first which has minimum weight, then next
minimum weight and so on. Thus we select objects in the sequence 2nd then 3rd then 1st. In
this approach we have total profit Σi=1 to 3 pixi = 31.0 units and the solution set (x1, x2, x3)
= (0, 2/3, 1).
Approach 3: (Selection of object in decreasing order of the ratio p i/wi).
In this approach, we select those object first which has maximum value of p i/wi, that is we
select those object first which has maximum profit per unit weight . Since (p 1/w1, p2/w2,
p3/w3)=(1.3, 1.6, 1.5). Thus we select 2nd object first , then 3rd object then 1st object. In
this approach we have total profit Σi=1 to 3 pixi = 31.5 units and the solution set (x1, x2, x3)
= (0, 1, ½).

Thus from above all 3 approaches, it may be noticed that

 Greedy approaches do not always yield an optimal solution. In such cases the greedy
method is frequently the basis of a heuristic approach.
 Approach3 (Selection of object in decreasing order of the ratio p i/wi) gives a optimal
solution for knapsack problem.
A pseudo-code for solving knapsack problem using greedy approach is
Greedy Fractional-Knapsack (P[1..n], W[1..n], X [1..n], M)
/* P[1..n] and W[1..n] contains the profit and weight of the n-objects ordered such that
X[1..n] is a solution set and M is the capacity of KnapSack*/
{
1: For i ← 1 to n do
2: X[i] ← 0
3: profit ← 0 //Total profit of item filled in Knapsack
4: weight ← 0 // Total weight of items packed in KnapSack
5: i←1
6: While (Weight < M) // M is the Knapsack Capacity
{
7: if (weight + W[i] ≤ M)

PraveenKumar P K, UIT Kollam

8: X[i] = 1
9: weight = weight + W[i]
10: else
11: X[i] = (M-weight)/W[i]
12: weight = M
13: profit = profit = profit + P[i]*X[i]
14: i++;
}//end of while
}//end of Algorithm

Running time of Knapsack (fractional) problem is O(n log n)

Q) Find an optimal solution for the knapsack instance n=7 and M=15,
(p1, p2, p3, p4, p5, p6, p7) = (10, 5, 15, 7, 6, 18, 3)
(w1, w2, w3, w4, w5, w6, w7) = (2, 3, 5, 7, 1, 4, 1)
Solution:
Greedy algorithm gives a optimal solution for knapsack problem if you select the object in
decreasing order of the ratio pi/wi. That is we select those object first which has maximum
value of the ratio pi/wi, for all i= 1, 2, … 7. This ratio is also called profit per unit weight .
Since (p1/w1, p2/w2,…. P7/w7)=(5, 1.67, 3, 1, 6, 4.5, 3). Thus we select 5th object first , then
1st object, then 3rd (or 7th ) object, and so on.

Q) Find an optimal solution for the knapsack instance n=4 and M=8,
(p1, p2, p3, p4) = (3, 5, 6, 10)
(w1, w2, w3, w4) = (2, 3, 4, 5)
Approach 1: Selection of object in decreasing order of profit
Approach 2: Selection of object in decreasing order of ratio p i/wi
Approach (x1, x2, x3, x4) Σi=1 to 4 wixi Σi=1 to 4 pixi
1 (0, 0, ¾, 1) 8 14.5
2 (0, 1, 0, 1) 8 15

2.2 Minimum Cost Spanning Tree (MCST) Problem

Definition: (Spanning tree): Let G=(V,E) be an undirected connected graph. A sub graph
T=(V,E’) of G is a spanning tree of G if and only if T is a tree (i.e. no cycle exist in T) and
contains all the vertices of G.

PraveenKumar P K, UIT Kollam

Definition: (Minimum cost Spanning tree): Suppose G is a weighted connected graph. A
weighted graph is one in which every edge of G is assigned some positive weight (or length).
A graph G is having several spanning tree.
In general, a complete graph (each vertex in G is connected to every other vertices) with n
vertices has total nn-2spanning tree. For example, if n=4 then total number of spanning tree
is 16.
A minimum cost spanning tree (MCST) of a weighted connected graph G is that spanning
tree whose sum of length (or weight) of all its edges is minimum, among all the possible
spanning tree of G.
For example: consider the following weighted connected graph G (as shown in figure-1).
There are so many spanning trees are possible for G. Out of all possible spanning trees, four
spanning trees and of G are shown in figure a to figure d.

A sum of the weights of the edges in a, b, c and d is: 41, 37, 36 and 34 (some other spanning
trees are also possible).
Application of spanning tree
 Designing an efficient network
 Designing of efficient routing algorithm.
To find a MCST of a given graph G, one of the following algorithms is used:
1. Kruskal’s algorithm
2. Prim’s algorithm
These two algorithms use Greedy approach. A greedy algorithm selects the edges one-by-
one in some given order. The next edge to include is chosen according to some optimization
criteria. The simplest such criteria would be to choose an edge (u, v) that results in a
minimum increase in the sum of the costs (or weights) of the edges so for included.
2.2.1 Kruskal’s Algorithm
Let G(V, E) is a connected, weighted graph. Kruskal’s algorithm finds a minimum-cost
spanning tree (MCST) of a given graph G. It uses a greedy approach to find MCST, because
at each step it adds an edge of least possible weight to the set A. In this algorithm,
 First we examine the edges of G in order of increasing weight.
 Then we select an edge (u, v) ε E of minimum weight and checks whether its end
points belongs to same component or different connected components.
 If u and v belongs to different connected components then we add it to set A,
otherwise it is rejected because it create a cycle.

PraveenKumar P K, UIT Kollam

  The algorithm stops, when only one connected components remains (i.e. all the
vertices of G have been reached).
Following pseudo-code is used to constructing a MCST, using Kruskal’s algorithm:

Kruskal’s algorithm works as follows:

 First, we sorts the edges of E in order of increasing weight
 We build a set A of edges that contains the edges of the MCST. Initially A is empty.
 At line 3-4, the function MAKE_SET(v), make a new set {v} for all vertices of G. For
a graph with n vertices, it makes n components of disjoint set such as {1},{2},… and so
on.
 In line 5-8: An edge (u, v)ε E, of minimum weight is added to the set A, if and only if
it joins two nodes which belongs to different components (to check this we use a
FIND_SET() function, which returns a same integer value, if u and v belongs to same
components (In this case adding (u,v) to A creates a cycle), otherwise it returns a
different integer value)
 If an edge added to A then the two components containing its end points are merged
into a single component.
 Finally the algorithm stops, when there is just a single component.
Analysis of Kruskal’s algorithm
Let E = number of edges, V is number of vertices then total time for Kruskal’s algorithm is
O(E log V)
Q) Apply Kruskal’s algorithm on the following graph to find Minimum-Cost-Spanning – Tree
(MCST).
Solution: First, we sorts the edges of G=(V,E) in order of increasing weights as:

PraveenKumar P K, UIT Kollam

The kruskal’s Algorithm proceeds as follows

Total Cost of Spanning tree, T = 2+3+5+4+5+4=23

PraveenKumar P K, UIT Kollam
2.2.2 Prim’s Algorithm
PRIM’s algorithm has the property that the edges in the set A (this set A contains the
edges of the minimum spanning tree, when algorithm proceed step-by step) always form a
single tree, i.e. at each step we have only one connected component.
 We begin with one starting vertex (say v) of a given graph G(V,E).
 Then, in each iteration, we choose a minimum weight edge (u, v) connecting a vertex v
in the set A to the vertices in the set V-A. That is, we always find an edge (u, v) of
minimum weight such that v ε A and u ε V-A. Then we modify the set A by adding u i.e.
A = A U {u}
 This process is repeated until A Not equal to V, i.e. until all the vertices are not in the
set A.
Following pseudo-code is used to constructing a MCST, using PRIM’s algorithm

PRIM’s algorithm works as follows

1) Initially the set A of nodes contains a single arbitrary node (i.e. starting vertex) and
the set T of edges are empty.
2) At each step PRIM’s algorithm looks for the shortest possible edge (u, v) such that
u ε V-A and v ε A
3) In this way the edges in T form at any instance a minimal spanning tree for the
nodes in A. We repeat this process until A not equal to v.
Time complexity of PRIM’s algorithm is O(n2)
Q) Apply PRIM’s algorithm on the following graph to find minimum-cost-spanning – tree
(MCST).

PraveenKumar P K, UIT Kollam

Solution: In PRIM’s, First we select an arbitrary member of V as a starting vertex (say 1),
then the algorithm proceeds as follows

Total Cost of the minimum spanning tree = 2+3+5+4+5+4 = 23

Q) Differentiate between Kruskal’s and Prim’s algorithm to find a Minimum cost of a
spanning tree of a graph G
Main difference between kruskal’s and Prim’s algorithm to solve MCST problem is that the
order in which the edges are selected.

Kruskal’s Algorithm Prim’s algorithm

Kruskal’s algorithm always selects an edge (u, Prim’s algorithm always selects a vertex (say,
v) of minimum weight to find MCST. v) to find MCST.
In kruskal’s algorithm for getting MCST, it is In Prim’s algorithm for getting MCST, it is
not necessary to choose adjacent vertices of necessary to select an adjacent vertex of
already selected vertices (in any successive already selected vertices (in any successive
steps). Thus steps). Thus
At intermediate step of algorithm, there are At intermediate step of algorithm, there will
may be more than one connected components be only one connected components are
PraveenKumar P K, UIT Kollam
are possible. possible
Time complexity: O(E log V) Time complexity: O(n2) or O(V2)
Exercise
Q) Find the optimal solution to the knapsack instance n=5, M=10,
(p1, p2,… p5) = (12, 32, 40, 30, 50)
(w1, w2,… w5) = (4, 8, 2, 6, 1)
Q) Let S={a, b, c, d, e, f, g} be a collection of objects with Profit-Weight values as follows:
a:(12,4), b:(10,6), c:(8,5), d:(11,7), e:(14,3), f:(7,1) and g:(9,6). What is the optimal solution to
the fractional knapsack problem for S, assuming we have a knapsack that can hold objects
with total weight 18?
Q) Apply Kruskal’s, PRIM’s algorithm on the following graph to find Minimum-Cost-Spanning –
Tree (MCST).

8 7
1 2 3
4 9
2
4
0 11 8 14 4
7
6
8 10
7 6 5
1 4

PraveenKumar P K, UIT Kollam