1

UNIT - I
Define the term: Algorithm
The algorithm is a set of rules defined in specific order to do certain
computation and carry out some predefined task. It is a step by step procedure
to solve the problem
State the properties of Algorithm
Following are the properties of algorithm:
 Input
 Output
 Definiteness
 Finiteness
 Effectiveness
Define the term: Time Complexity
The amount of time required to solve the given problem is called the time
complexity of that algorithm
Define the term: Space Complexity
The amount of memory required to solve the given problem is called the space
complexity of that algorithm
Enlist few problem solving strategies
Following are some of the popular problem solving strategies:
 String matching algorithms
 Number theory and numerical algorithms
 Divide and conquer
 Linear programming
 Dynamic programming
 Greedy methods
 Sorting
What is Asymptotic Analysis?
Asymptotic notations are the mathematical tools that can be used to determine
the time or space complexity of an algorithm without having to implement it in
a programming language. This measure is unaffected by machine-specific
constants. It is a way of describing a significant part of the cost of the
algorithm.
The asymptotic notations examine algorithms that are not affected by any of
these factors.
Finding minimum element from an array of size n takes maximum n
comparisons.
This algorithm’s asymptotic complexity is linear (in order of n). The primary
term in the complexity formula is this linear behavior.
The primitive operation is the most frequent operation appearing in the
algorithm and it depends on the problem. The primitive operation is the major
component of cost.
The fundamental process for sorting and searching problems is a comparison.
The primitive operation for adding arrays or matrices is addition. The primitive
operation for the factorial problem is multiplication.
 2

The order of function growth is critical in evaluating the algorithm’s

performance. Assume the running times of two algorithms A and B are f(n) and
g(n), respectively.
f(n) = 2n2 + 5
g(n) = 10n
Here, n represents the size of the problem, while polynomials f(n) and g(n)
represent the number of basic operations performed by algorithms A and B,
respectively. Running time of both the functions for different input size is
shown in following table:

n 1 2 3 4 5 6 7

f(n) 7 13 23 37 55 77 103

g(n
10 20 30 40 50 60 70
)

Algorithm A may outperform algorithm B for small input sizes, however when
input sizes become sufficiently big (in this example n = 5), f(n) always runs
slower (performs more steps) than g(n). As a result, understanding the growth
rate of functions is critical.
Asymptotic notations describe the function’s limiting behavior. For example, if
the function f(n) = 8n2 + 4n – 32, then the term 4n – 32 becomes insignificant
as n increases. As a result, the n2 term limits the growth of f(n).
When doing complexity analysis, the following assumptions are assumed.
Assumptions:
 The actual cost of operation is not considered.
 Abstract cost c is ignored : O(c. n 2) reduces to O(n2)
 Only leading term of a polynomial is considered : O(n 3 + n) reduces to
O(n3)
 Drop multiplicative or divisive constant if any : O(2n 2) and O(n2/2) both
reduces to O(n2).
Types of Asymptotic Notations
Various notations like Big Oh (Ο), Big Omega (Ω), Big Theta (Θ), Little Oh (ο),
Little Omega (ω) are used to describe the asymptotic running time of the
algorithm
 3

Big Oh Notation (Ο)

This notation is denoted by ‘O’, and it is pronounced as “Big Oh”. Big Oh
notation defines upper bound for the algorithm, it means the running time of
algorithm cannot be more than it’s asymptotic upper bound for any random
sequence of data.
Let f(n) and g(n) are two nonnegative functions indicating the running time of
two algorithms. We say, g(n) is upper bound of f(n) if there exist some positive
constants c and n0 such that 0 ≤ f(n) ≤ c.g(n) for all n ≥ n 0. It is denoted as
f(n) = Ο(g(n)).
In following figure, Horizontal axis represents problem size and the vertical axis
represents growth order (steps required to solve the problem of size n) of
functions

For small input size, there may be many cross overs between the growth rate
of f(n) and c.g(n), but once n becomes significantly large, f(n) grows always
slower than c.g(n). This value of n is called crossover point and is denoted as
n0.
Big Omega Notation (Ω)
This notation is denoted by ‘Ω’, and it is pronounced as “Big Omega”. Big
Omega notation defines lower bound for the algorithm. It means the running
 4

time of algorithm cannot be less than its asymptotic lower bound for any
random sequence of data.

Let f(n) and g(n) are two nonnegative functions indicating the running time of
two algorithms. We say the function g(n) is lower bound of function f(n) if there
exist some positive constants c and n 0 such that 0 c.g(n) ≤ f(n) for all n ≥ n 0.
It is denoted as f(n) = Ω (g(n)).
Big Theta Notation (Θ)
This notation is denoted by ‘Θ’, and it is pronounced as “Big Theta”. Big
Theta notation defines tight bound for the algorithm. It means the running
time of algorithm cannot be less than or greater than it’s asymptotic tight
bound for any random sequence of data

Let f(n) and g(n) are two nonnegative functions indicating running time of two
algorithms. We say the function g(n) is tight bound of function f(n) if there exist
some positive constants c1, c2, and n0 such that 0 ≤ c1× g(n) ≤ f(n) ≤ c2× g(n)
for all n ≥ n0. It is denoted as f(n) = Θ (g(n)).
For big oh, big omega and big theta, g(n) is not a single function but it’s a set
of functions which always grow quickly, slowly or at the same rate of f(n)
respectively for n ≥ n0.
Properties of Asymptotic Notations
Asymptotic notations satisfy the following properties
Correlation:
f(n) = Ο(g(n) ) → f ≤ g
 5

f(n) = ο(g(n) ) → f < g

f(n) = Θ(g(n) ) → f = g
f(n) = Ω(g(n) ) → f ≥ g
f(n) = ω(g(n) ) → f > g
Reflexivity:
f(n) = Θ(f(n) ) = Ο(f(n) ) = Ω(f(n) )
Symmetry:
f(n) = Θ(g(n) ) if and only if g(n) = Θ(f(n))
Transpose symmetry:
f(n) = Ο(g(n)) if and only if g(n) = Ω(f(n))
f(n) = ο(g(n)) if and only if g(n) = ω(f(n))
Transitivity:
f(n) = Ο(g(n) ) and g(n) = Ο(h(n) ) ≈ f(n) = Ο(h(n) )
f(n) = Ω(g(n) ) and g(n) = Ω(h(n)) ≈ f(n) = Ω(h(n))
f(n) = Θ(g(n) ) and g(n) = Θ(h(n) ) ≈ f(n) = Θ(h(n) )
f(n) = ο(g(n) ) and g(n) = ο(h(n) ) ≈ f(n) = ο(h(n) )
f(n) = ω(g(n) ) and g(n) = ω(h(n) ) ≈ f(n) = ω(h(n))
Manipulation
c.Ο(f(n) ) = Ο(f(n) )
Ο(Ο(f(n))) = Ο(f(n) )
Ο(f(n)).Ο(g(n))) = Ο(f(n) × g(n))
Ο(f(n)+ g(n)) = Ο(max (f(n),g(n))

Binary Search
The binary search method is more efficient than the linear search method. The
array must be sorted for binary search, which is not necessary for linear search.
Binary search is a search strategy based on divide and conquer. The method
divides the list into two halves at each step and checks weather the element to
be searched is on the top or lower side of the array. If the element is located in
the center, the algorithm returns.
Let us assign minimum and maximum index of the array to variables low and
high, respectively. The middle index is computed as (low + high)/2.

In every iteration, the algorithm compares the middle element of the array with
a key to be searched. Initial range of search is A[0] to A[n – 1]. When the key is
compared with A [mid], there are three possibilities :
1. The array is already sorted, so if key < A[mid] then key cannot be
present in the bottom half of the array. Search space of problem will be
reduced by setting the high index to (mid – 1). New search range would
be A[low] to A[mid – 1].
2. If key > A[mid] then the key cannot be present in the upper half of the
array. Search space of problem will be reduced by moving the low index
to (mid + 1). New search range would be A[mid + 1] to A[high]
3. If key = A[mid], the search is successful and algorithm halts.
This process is repeated till index low is less than high or element is found.
 6

Algorithm BINARY_SEARCH(A, Key)

// Description : Perform a binary search on array A
// Input : Sorted array A of size n and Key to be searched
// Output : Success / Failure

low ← 1
high ← n
whilelow < high do
mid ← (low + high) / 2
ifA[mid] == key then
return mid
else if A[mid] < key then
low ← mid + 1
else
high ← mid – 1
end
end
return0
Binary search reduces search space by half in every iteration. In a linear
search, the search space was reduced by one only.
If there are n elements in an array, binary search, and linear search have to
search among (n / 2) and (n – 1) elements respectively in the second iteration.
In the third iteration, the binary search has to scan only (n / 4) elements,
whereas linear search has to scan (n – 2) elements. This shows that a binary
search would hit the bottom very quickly.
The complexity of linear search and binary search for all three cases is
compared in the following table.

Best Average Worst

case case case

Binary Search O(1) O(log2n) O(log2n)

Linear Search O(1) O(n) O(n)

Example of Binary Search

Example: Find element 33 from array A {11, 22, 33, 44, 55, 66, 77, 88}
using binary search.
Solution:
The array is already sorted, so we can directly apply binary search on A. Here
Key = 33.
Iteration 1: Initial search space
 7

low = 1, high = 8,
mid = low + high) / 2 = (1 + 8)/ 2 = 9/2 = 4
A[mid] = A[4] = 44
As Key <A[4], update high
high = mid – 1 = 4 – 1 = 3
Iteration 2 :New search space

low = 1, high = 3,
mid = (low + high) / 2 = (1 + 3)/ 2= 4/2 = 2
A[mid] = A[2] = 22
As Key >A[2], update low
low = mid + 1= 2 + 1 = 3
Iteration 3 :New search space

low = 3, high = 3,
mid = (low + high) / 2 = (3 + 3)/ 2= 6/2 = 3
A[mid] = A[3] = 33
Key = A[3], An element found, so return mid

Quick Sort
Quick sort is a sorting technique that has the ability to break a massive data
array into smaller ones in order to save time. Here, in the case of the quick sort
algorithm, an extensive array is divided into two arrays, one of which has
 8

values less than the specified value, say pivot. The pivot value is bigger than
the other.
Working of Quick Sort Algorithm
Now, it’s time to see the working of a quick sort algorithm, and for that, we
need to take an unsorted array.
Let the components of the array are –

Here,
L= Left
R = Right
P = Pivot
In the given series of arrays, let’s assume that the leftmost item is the pivot.
So, in this condition, a[L] = 23, a[R] = 26 and a[P] = 23.
Since, at this moment, the pivot item is at left, so the algorithm initiates from
right and travels towards left.

Now, a[P] < a[R], so the algorithm travels forward one position towards left, i.e.
–

Now, a[L] = 23, a[R] = 18, and a[P] = 23.

Since a[P] > a[R], so the algorithm will exchange or swap a[P] with a[R], and
the pivot travels to right, as –

Now, a[L] = 18, a[R] = 23, and a[P] = 23. Since the pivot is at right, so the
algorithm begins from left and travels to right.
As a[P] > a[L], so algorithm travels one place to right as –
 9

Now, a[L] = 8, a[R] = 23, and a[P] = 23. As a[P] > a[L], so algorithm travels
one place to right as –

Now, a[L] = 28, a[R] = 23, and a[P] = 23. As a[P] < a[L], so, swap a[P] and
a[L], now pivot is at left, i.e. –

Since the pivot is placed at the leftmost side, the algorithm begins from right
and travels to left. Now, a[L] = 23, a[R] = 28, and a[P] = 23. As a[P] < a[R], so
algorithm travels one place to left, as –

Now, a[P] = 23, a[L] = 23, and a[R] = 13. As a[P] > a[R], so, exchange a[P] and
a[R], now pivot is at right, i.e. –

Now, a[P] = 23, a[L] = 13, and a[R] = 23. Pivot is at right, so the algorithm
begins from left and travels to right.

Now, a[P] = 23, a[L] = 23, and a[R] = 23. So, pivot, left and right, are pointing
to the same element. It represents the termination of the procedure.
Item 23, which is the pivot element, stands at its accurate position.
Items that are on the right side of element 23 are greater than it, and the
elements that are on the left side of element 23 are smaller than it.
 10

Now, in a similar manner, the quick sort algorithm is separately applied to the
left and right sub-arrays. After sorting gets done, the array will be –

Quick Sort Algorithm

Algorithm:
QUICKSORT (array A, begin, finish)
{
if (begin < finish)
{
p = partition(A, begin, finish)
QUICKSORT (A, begin, p – 1)
QUICKSORT (A, p + 1, finish)
}
}
Partition Algorithm:
The partition algorithm rearranges the sub-arrays in a place.
PARTITION (array A, begin, finish)
{
1. pivot ? A[finish]
2. i = begin-1
3. for j = begin to finish-1 {
4. do if (A[j] < pivot) {
5. then i =i + 1
6. swap A[i] with A[j]
}}
swap A[i+1] with A[finish]
return i+1
}

The space complexity for quicksort is O(log n).

Merge Sort Algorithm
Merge sort is the sorting technique that follows the divide and conquers strategy.It is very much
similar to the quick sort algorithm as it also prefers the divide and conquers method to sort the
elements. It is one of the most efficient sorting algorithms. It splits the provided array into two
halves, then sorts them and combines them.

In the below algorithm, ar is the given array, start is the starting element, and finish is the last
component of the array.

1. MERGE_SORT(ar, start, finish)

2. if start< finish
 11

3. set mid = (start + finish)/2

4. MERGE_SORT(ar, start, mid)
5. MERGE_SORT(ar, mid + 1, finish)
6. MERGE (ar, start, mid, finish)
7. finish of if
8. FINISH MERGE_SORT

Working of Merge Sort Algorithm

To understand the working of the merge sort algorithm, we are considering an
unsorted list of arrays.
Let the components of the array are –

The given array will initially be divided into two parts in accordance with the
merge sort. The list is repeatedly split into two equal pieces in the merge sort
algorithm until it can no longer be split.
There are a total of eight elements in the array below, which has been
separated into four array sizes (each).

Now divide these two arrays once more into two sections. These arrays are 4
bytes in size. We’ll divide them into two equal pieces.

To get the final value that we can’t split any further, we shall split these arrays
once more.

Now, combine them exactly as we did when we separated them.

Merging involves comparing the list’s elements first, after which they are
combined into another list of sorted arrays.
Therefore, compare 11 and 30 first since they both have sorted positions. Then,
after comparing 24 and 7, order the two values in the array of two by placing 7
before 24. Then order them and place 16 first, then 31 after comparing 31 and
16. Compare 39 and 41 after that, then arrange them in order.

In the subsequent iteration, compare the arrays holding the two data values
and combine them into a single array of found values in sorted order.

The arrays are finally combined at this point. The array will now appear as
follows:

Now, the array is completely sorted.

 12

Merge Sort Complexity

Time Complexity of Merge Sort Algorithm
Time Complexity of Merge
Case
Sort

Best Case O(n*logn)

Average
O(n*logn)
Case

Worst Case O(n*logn)

2. Space Complexity of Merge Sort Algorithm

Space Complexity of Merge Sort

O(n)
Algorithm

Matrix Multiplication using Divide and Conquer

Conventional Approach
Matrix multiplication is an important operation in many mathematical and
image processing applications. Suppose we want to multiply two matrices A
and B, each of size n x n, multiplication is operation is defined as

C11 = A11 B11 + A12 B21

C12 = A11 B12 + A12 B22
C21 = A21 B11 + A22 B21
C22 = A21 B12 + A22 B22
This approach is very costly as it required 8 multiplications and 4 additions.
Algorithm MATRIX_MULTIPLICATION(A, B, C)
// A and B are input matrices of size n x n
// C is the output matrix of size n x n

fori ← 1 to n do
forj ← 1 to n do
C[i][j] ← 0
fork ← 1 to n do
C[i][j] ← C[i][j] + A[i][k]*B[k][j]
end
end
end

Complexity Analysis
The innermost statement is enclosed within three for loops. That statement
runs in constant time, i.e. in O(1) time. Running time of algorithm would be,
 13

Running time of this algorithm is cubic, i.e. O(n 3)

Matrix Multiplication using Strassen’s Method
Strassen suggested a divide and conquer strategy-based matrix multiplication
technique that requires fewer multiplications than the traditional method. The
multiplication operation is defined as follows using Strassen’s method:

C11 = S1 + S4 – S5 + S7
C12 = S3 + S5
C21 = S2 + S4
C22 = S1 + S3 – S2 + S6
Where,
S1 = (A11 + A22) * (B11 + B22)
S2 = (A21 + A22) * B11
S3 = A11 * (B12 – B22)
S4 = A22 * (B21 – B11)
S5 = (A11 + A12) * B22
S6 = (A21 – A11) * (B11 + B12)
S7 = (A12 – A22) * (B21 + B22)
Let us check if it is same as the conventional approach.
C12 = S3 + S5
= A11 * (B12 – B22) + (A11 + A12) * B22
= A11 * B12 – A11 * B22 + A11 * B22 + A12 * B22
= A11 * B12 + A12 * B22
This is same as C12 derived using conventional approach. Similarly we can derive all Cij for
strassen’s matrix multiplication.
Complexity Analysis of Matrix Multiplication using Divide and Conquer approach
The conventional approach performs eight multiplications to multiply two matrices of size 2 x 2.
Whereas Strassen’s approach performs seven multiplications on the problem of size 1 x 1, which in
turn finds the multiplication of 2 x 2 matrices using addition. In short, to solve the problem of size
n, Strassen’s approach creates seven problems of size (n – 2). Recurrence equation for Strassen’s
approach is given as,
T(n) = 7.T(n/2)
Two matrices of size 1 x 1 needs only one multiplication, so the base case would be, T (1) = 1. Let
us find the solution using the iterative approach. By substituting n = (n / 2) in above equation,

⇒T(n) = 72.T(n/22)
T(n/2) = 7.T(n/4)

.
.
.

Let’s assume n = 2k⇒ k = log2 n

k k
T(n) = 7 .T(2 )

T (n) = 7k .T(2k/2k)
= 7k .T (1)
= 7k
 14

= 7log2 n
= nlog2 7
= n2.81 < n3
Thus, running time of Strassen’s matrix multiplication algorithm O(n 2.81), which is less than cubic
order of traditional approach. The difference between running time becomes significant when n is
large.
Example of Matrix Multiplication using Divide and Conquer Approach
Problem: Multiply given two matrices A and B using Strassen’s
approach, where
15
16
 17

UNIT - II
Disjoint set operations, union and find algorithms
A disjoint set data structure is a data structure that stores a list of disjoint
sets. In other words, this data structure divides a set into multiple subsets
- such that no 2 subsets contain any common element. They are also
called union-find data structures or merge-find sets.
For example: if the initial set is [1,2,3,4,5,6,7,8].
A Disjoint Set Data Structure might partition it as - [(1,2,4), (3,5), (6,8),
(7)].
This contains all of the elements of the original set, and no 2 subsets have
any element in common.
The following partitions would be invalid:
[(1,2,3),(3,4,5),(6,8),(7)] - invalid because 3 occurs in 2 subsets.
[(1,2,3),(5,6),(7,8)] -invalid as 4 is missing.
Representative Member
Each subset in a Disjoint Set Data Structure has a representative
member. More commonly, we call this the parent. This is simply the
member responsible for identifying the subset.
Let's understand this with an example.
Suppose this is the partitioning of sets in our Disjoint Set Data structure.

We wish to identify each subset, so we assign each subset a value by

which we can identify it. The easiest way to do this is to choose
a member of the subset and make it the representative member. This
representative member will become the parent of all values in the
subset.

Here, we have assigned representative members to each subset. Thus, if

we wish to know which subset 3 is a part of, we can simply say - 3 is a
part of the subset with representative member 1. More simply, we
can say that the parent of 3 is 1.
Here, 1 is its own parent.
Disjoint Set Operations
There are 2 major disjoint set operations
 18

1. Union/Merge - this is used to merge 2 subsets into a single subset.

2. Find - This is used to find which subset a particular value belongs
to.
Here we have considered cities instead of integers.

Union/Merge
Suppose, in our example - a new express train started from Delhi to Agra.
This would mean that all the cities connected to Delhi are now connected
to all the cities connected to Agra.
This simply means that we can merge the subsets of Agra and Delhi into
a single subset. It will look like this.

One key issue here is which out of Agra and Delhi will be the new Parent?
For now, we will just choose any of them, as it will be sufficient for our
purposes. Let's take Delhi for now.
Further optimizations can be made to this by choosing the parent
based on which subset has a larger number of values.
 19

This is the new state of our Disjoint Set Data Structure. Delhi is the parent
of Delhi, Gurgaon, Noida, Agra, Vrindavan, and Mathura.
This would mean that we would have to change the parent of Agra,
Vrindavan, and Mathura (basically, all the children of Agra), to Delhi. This
would be linear in time. If we perform the union operation m times, and
each union takes O(n) times, we would get a quadratic O(mn) time
complexity. This is not optimized enough.
Instead, we structure it like this:

Earlier, Agra was its own parent. Now, Delhi is the parent of Agra.
Now, you might be wondering - The parent of Vrindavan is still Agra. It
should have been Delhi now.
This is where the next operation helps us - the find operation.
Find
The find operation helps us find the parent of a node. As we saw above,
the direct parent of a node might not be its actual (logical) parent. E.g.,
the logical parent of Vrindavan should be Delhi in the above example. But
its direct parent is Agra.
So, how do we find the actual parent?
The find operation helps us to find the actual parent. In pseudocode, the
find operation looks like this:
find(node):
if (parent(node)==node) return node;
else return find(parent(node));
We don't return the direct parent of the node. We keep going up the tree
of parents until we find a node that is its own parent.
Let's understand this via our example.
 20

Suppose we have to find the parent of Mathura.

1. Check the direct parent of Mathura. It's Agra. Is Agra == Mathura?
The answer is false. So, now we call the find operation on Agra.
2. Check the direct parent of Agra. It's Delhi. Is Delhi ==Agra?
The answer is false. So now we call the find operation on Delhi.
3. Check the direct parent of Delhi. It's Delhi. Is Delhi==Delhi.
The answer is true! So, our final answer for the parent of Mathura is
Delhi.
This way, we keep going "up" the tree until we reach a root element. A
root element is a node with its own parent - in our case, Delhi.

Let's try to find the parent of K in this example. (A and D are their own
parents)
1. ParentOf(K) is I. Is I == K?
False. So, we move upward, now using I.
2. ParentOf(I) is C. Is C== I?
False. Move upward using C.
3. ParentOf(C) is A. Is A==C?
False. Move upward using A.
 21

4. ParentOf(A) is A. Is A==A?
True! Our final answer is A.
Let's understand the use of a Disjoint Set Data Structure through a simple
application - Finding a cycle in an undirected graph.

Find a Cycle in an Undirected Graph using Disjoint Set Data

Structure

Here, wewill use a disjoint set data structure to find whether an undirected
graph contains a cycle or not. We are assuming that our graph does not
contain any self-loops.

Let this be our graph. Each node is initialized as its own parent. The list
ofedges is shown on the top right, and the parents are shown at the
bottom. We have shown each edge only once for simplicity (i.e., 1-2 and
2-1 aren't shown separately)
Algorithm
We will go through each edge and do the following. Let the edge be u-v.
1. Find the parent of u and v. If both parents are the same, it means u
and v are part of the same subset, and we have found a cycle.v
2. If they are not the same, merge u and v. We don't merge u and v
directly. Instead, we merge the parents of u and v. This ensures that
all the siblings of u and all the siblings of v have the same common
parent.
We do this for all edges.

Walkthrough

1. 1-2 Edge.
Parent of 1 is 1, parent of 2 is 2. They are different, so we will merge
them. Set the parent of 2 as 1 (this is chosen randomly, setting the parent
of 1 as 2 would also have been correct ).
 22

2. 1-4 Edge.

Parent of 1 is 1. Parent of 4 is 4. They are not the same, so merge 1 and

4. Set parent of 4 as 1.

3. 2-5 Edge.

The parent of 2 is 1, and the parent of 5 is 5. They aren't the same, so

we'll merge them. Set the parent of 5 as 1.
 23

4. 3-6 Edge.

The parent of 3 is 3, and the parent of 6 is 6. They aren't the same, so

we'll merge them. Set the parent of 6 as 3.

5. 5-6 Edge.

The parent of 5 is 1, and the parent of 6 is 3. They aren't the same, so

we'll merge them. Set the parent of 3 as 1.

Note here - the direct parent of 6 is still 3. But, the actual parent becomes
1, because the parent of 3 is 1. (The dotted line is not an edge in the
graph, it shows that the parent of 3 is 1)

6. 6-2 Edge.

The parent of 6 is 1 (actual parent), and the parent of 2 is also 1. These

are both the same. Thus, our graph contains a cycle.
 24

N Queen Problem
N Queen problem is the classical Example of backtracking. N-Queen
problem is defined as, “given N x N chess board, arrange N queens in
such a way that no two queens attack each other by being in same row,
column or diagonal”.
 For N = 1, this is trivial case. For N = 2 and N = 3, solution is not
possible. So we start with N = 4 and we will generalize it for N
queens.
4-Queen Problem
Problem : Given 4 x 4 chessboard, arrange four queens in a way, such
that no two queens attack each other. That is, no two queens are placed
in the same row, column, or diagonal.

4 x 4 Chessboard
 We have to arrange four queens, Q1, Q2, Q3 and Q4 in 4 x 4 chess
board. We will put ith queen in ith row. Let us start with position (1,
1). Q1 is the only queen, so there is no issue. partial solution is <1>
 We cannot place Q2 at positions (2, 1) or (2, 2). Position (2, 3) is
acceptable. partial solution is <1, 3>.
 Next, Q3 cannot be placed in position (3, 1) as Q1 attacks her. And
it cannot be placed at (3, 2), (3, 3) or (3, 4) as Q2 attacks her. There
is no way to put Q3 in third row. Hence, the algorithm backtracks
and goes back to the previous solution and readjusts the position of
queen Q2. Q2 is moved from positions (2, 3) to
(2, 4). Partial solution is <1, 4>
 Now, Q3 can be placed at position (3, 2). Partial solution is <1, 4,
3>.
 Queen Q4 cannot be placed anywhere in row four. So again,
backtrack to the previous solution and readjust the position of Q3.
Q3 cannot be placed on (3, 3) or(3, 4). So the algorithm backtracks
even further.
 All possible choices for Q2 are already explored, hence the
algorithm goes back to partial solution <1> and moves the queen
Q1 from (1, 1) to (1, 2). And this process continues until a solution is
found.
 All possible solutions for 4-queen are shown in fig (a) & fig. (b)
 25

We can see that backtracking is a simple brute force approach, but it

applies some intelligence to cut out unnecessary computation. The
solution tree for the 4-queen problem is shown in Fig. (c).

Below figure describes the backtracking sequence for the 4-queen

problem.
 26

The solution of the 4-queen problem can be seen as four tuples (x 1, x2, x3,
x4), where xi represents the column number of queen Q i. Two possible
solutions for the 4-queen problem are (2, 4, 1, 3) and (3, 1, 4, 2).

Algorithm

The following algorithm arranges n queens on n x n board using a

backtracking algorithm.

Algorithm
N_QUEEN (k, n)
// Description : To find the solution of n x n queen problem using
backtracking
// Input :
n: Number of queen
k: Number of the queen being processed currently, initially set to 1.

// Output : n x 1 Solution tuple

 27

for i ← 1 to n do
if PLACE(k , i) then
x[k] ← i
if k == n then
print X[1…n]
else
N_QUEEN(k + 1, n)
end
end
end

 Function PLACE (k, i) returns true, if the k th queen can be placed in

the ith column. This function enumerates all the previously kept
queen’s positions to check if two queens are on the same diagonal.
It also checks that iis distinct from all previously arranged queens.
 Function abs(a) returns the absolute value of argument a. The array
X is the solution tuple.
 Like all optimization problems, the n-queen problem also has some
constraints that it must satisfy. These constraints are divided into
two categories : Implicit and explicit constraints

Function

PLACE(k, i)
// k is the number of queen being processed
// i is the number of columns
For j ← 1 to k – 1 do
if x[j] == i OR ((abs(x[j]) - i) == abs(j - k))then
return false
end
end

return true
 28

Explicit Constraints:

 Explicit constraints are the rules that allow/disallow selection of x i to

take value from the given set. For example, xi = 0 or 1.

xi = 1 if LBi ≤ xi ≤ UBi

xi = 0 otherwise

 Solution space is formed by the collection of all tuple which

satisfies the constraint.

Implicit constraints:

 The implicit constraint is to determine which of the tuple of solution

space satisfies the given criterion functions. The implicit constraint
for n queen problem is that two queens must not appear in the
same row, column or diagonal.

Complexity analysis :In backtracking, at each level branching factor

decreases by 1 and it creates a new problem of size (n – 1) . With n
choices, it creates n different problems of size (n – 1) at level 1.

 PLACE function determines the position of the queen in O(n) time.

This function is called n times.
 Thus, the recurrence of n-Queen problem is defined as, T(n) = n*T(n
– 1) + n2. Solution to recurrence would be O(n!).
 29

Sum of Subsets –backtracking

Sum of Subsets Problem: Given a set of positive integers, find the

combination of numbers that sum to given value M.

Example

Problem: Consider the sum-of-subset problem, n = 4, Sum = 13,

and w1 = 3, w2 = 4, w3 = 5 and w4 = 6. Find a solution to the
problem using backtracking. Show the state-space tree leading to
the solution. Also, number the nodes in the tree in the order of
recursion calls.

Solution:

The correct combination to get the sum of M = 13 for given W = {3, 4, 5,

6} is [3, 4, 6]. The solution vector for [3, 4, 6] would be X = [1, 1, 0, 1]
because element 5 is not chosen, so X[3] = 0. Let’s derive the solution
using backtracking. The numbers in W are already sorted.

Set X = [0, 0, 0, 0]

Set Sum = 0. Sum indicates summation of selected numbers from W.

Step 1 : i = 1, Adding item wi

Sum = Sum + wi = Sum + w1 = 0 + 3 = 3

Sum ≤ M, so add item i to solution set.

X[i] = X[1] = 1 ⇒ X =[1, 0, 0, 0]

Step 2 : i = 2, Adding item w2

Sum = Sum + wi = Sum + w2 = 3 + 4 = 7

Sum ≤ M, so add item i to solution set.

X[i] = X[2] = 1 ⇒ X =[1, 1, 0, 0]

Step 3 : i = 3, Adding item w3

Sum = Sum + wi = Sum + w3 = 7 + 5 = 12

Sum ≤ M, so add item i to solution set.

X[i] = X[3] = 1 ⇒ X =[1, 1, 1, 0]

 30

Step 4 : i = 4, Adding item w4

Sum = Sum + wi = Sum + w4 = 12 + 6 = 18

Sum > M, so backtrack and remove the previously added item from the
solution set.

X[i] = X[3] = 0 ⇒ X =[1, 1, 0, 0].

Update Sum accordingly. So, Sum = Sum – w 3 = 12 – 5 = 7

And don’t increment i.

Step 5 : i = 4, Adding item w4

Sum = Sum + wi = Sum + w4 = 7 + 6 = 13

Sum = M, so solution is found and add item i to solution set.

X[i] = X[4] = 1 ⇒ X =[1, 1, 0, 1] A complete state space tree for given

data is shown in Fig.

Algorithm for Sum of subsets

The algorithm for solving the sum of subsets problem using recursion is stated below:
 31

Algorithm
SUB_SET_PROBLEM(i, sum, W, remSum)
// Description : Solve sub of subset problem using backtracking
// Input :
W: Number for which subset is to be computed
i: Item index
sum : Sum of integers selected so far
remSum : Size of remaining problem i.e. (W – sum)

// Output : Solution tuple X

If FEASIBLE_SUB_SET(i) == 1 then
if (sum == W) then
print X[1…i]
end
else
X[i + 1] ← 1
SUB_SET_PROBLEM(i + 1, sum + w[i] + 1, W, remSum – w[i]
+1)
X[i + 1] ← 0 // Exclude the ith item
SUB_SET_PROBLEM(i + 1, sum, W, remSum – w[i] + 1 )
end

function

FEASIBLE_SUB_SET(i)
if (sum + remSum ≥ W) AND (sum == W) or (sum + w[i] + 1 ≤ W) then
return0
end
else
return 1

The first recursive call represents the case when the current item is
selected, and hence the problem size is reduced by w[i].

The second recursive call represents the case when we do not select the
current item.

Complexity Analysis

It is intuitive to derive the complexity of sum of the subset problem. In the

state-space tree, at level i, the tree has 2i nodes. So, given n items, the
total number of nodes in the tree would be 1 + 2 + 2 2 + 23+ .. 2n.

T(n) = 1 + 2 + 22 + 23 + .. 2n = 2n+1 – 1 = O(2n)

 32

Graph Coloring Problem

Graph coloring refers to the problem of coloring vertices of a graph in

such a way that no two adjacent vertices have the same color. This is also
called the vertex coloring problem.

 If coloring is done using at most k colors, it is called k-coloring.

 The smallest number of colors required for coloring graph is called
its chromatic number.

 The chromatic number is denoted by X(G). Finding the chromatic

number for the graph is NP-complete problem.
 Graph coloring problem is both, decision problem as well as an
optimization problem. A decision problem is stated as, “With given
M colors and graph G,

 The optimization problem is stated as, “Given M colors and graph G,

find the minimum number of colors required for graph coloring.”
 Graph coloring problem is a very interesting problem of graph
theory and it has many diverse applications. Few of them are listed
below.

Applications of Graph Coloring Problem

 Design a timetable.
 Sudoku
 Register allocation in the compiler
 Map coloring
 Mobile radio frequency assignment:

The input to the graph is an adjacency matrix representation of the graph.

Value M(i, j) = 1 in the matrix represents there exists an edge between
vertex i and j. A graph and its adjacency matrix representation are shown
in Figure

C1 C2 C3 C4 C5
C1 0 1 0 1 0
C2 1 0 1 0 0
C3 0 1 0 1 1
C4 1 0 1 0 1
 33

C5 0 0 1 0 0
Adjacency matrix for graph G

The problem can be solved simply by assigning a unique color to each

vertex, but this solution is not optimal. It may be possible to color the
graph with colors less than |V|. below figures demonstrate both such
instances. Let Ci denote the ithcolor.

Nonoptimal solution (uses 5 colors)

Optimal solution (uses 2 colors)

This problem can be solved using backtracking algorithms as follows:

 List down all the vertices and colors in two lists

 Assign color 1 to vertex 1
 If vertex 2 is not adjacent to vertex 1 then assign the same color,
otherwise assign color 2.
 Repeat the process until all vertices are colored.

Algorithm backtracks whenever colori is not possible to assign to any

vertex k and it selects next colori + 1 and test is repeated. Consider the
graph shown inFigure

If we assign color 1 to vertex A, the same color cannot be assigned to

vertex B or C. In the next step, B is assigned some different color 2. Vertex
 34

A is already colored and vertex D is a neighbor of B, so D cannot be

assigned color 2. The process goes on. State-space tree is shown in Figure

State-space tree of the graph of Figure

Thus, vertices A and C will be colored with color 1, and vertices B and D
will be colored with color 2.

Complexity Analysis

With M colors and n vertices, total number of nodes in state space tree
would be
1 + M + M2 + M3 + …. + Mn

Hence, T(n) = 1 + M + M2 + M3 + …. + Mn

So, T(n) = O(Mn).

Thus, the graph coloring algorithm runs in exponential time.

 35

UNIT -III

ALL PAIR SHORTEST PATH ALGORITH.

(Floyd-Warshall Algorithm)

DYNAMIC PROGRAMMING APPROACH

Floyd Warshall is a dynamic programming-based algorithm, so it breaks the problem

into smaller subproblems and then solves each unitary subproblems after that it
combines the result to solve the bigger problem by storing the result of each
subproblem for future reference.

Floyd Warshall is all pair shortest path algorithm used to find the shortest path or
shortest distance between every pair of vertices in the given graph. The algorithm
is applicable on both directed and undirected graphs, but it fails with the graph
having negative cycles; a negative cycle means the sum of the edges in a cycle is
negative.

Example:

Make the distance matrix or graph matrix. Insert the distance value and if the
distance is unknown fill that with ∞.

Step1: Calculating the Distance of every pair Via A.

Applying Floyd’s Warshall algorithm,
D0 [B, C] = D0 [B, A] + D0 [A, C]
∞>3+5
∞ > 8….. updating the distance
 36

D0 [B, C] = 8
D0 [B, D] = D0 [B, A] + D0 [A, D]
2>3+∞
2 > ∞….. No changes
D0 [B, D] = 2
D0 [C, B] = 4
D0 [C, D] = D0 [C, A] + D0 [A, D]
∞>∞+∞
∞ > ∞….. No changes
D0 [C, D] = ∞
D0 [D, B] = D0 [D, A] + D0 [A, B]
∞>∞+6
∞ > ∞….. No changes
D0 [D, B] = ∞
D0[D, C] = 7

Step 2 :Calculating the Distance of every pair Via B

 37

Step 3 :Calculating distance of each path via C.

Similarly, if we calculate the shortest distance Via D, No changes will be required.

Hence, the shortest path matrix using Floyd’s Warshall algorithm is as follows

Algorithm

1. Make a matrix for the given input graph.

2. Create another solution matrix same as the input graph matrix.
3. Update the solution matrix while considering all vertex as an
intermediate vertex.
 38

4. Choose each vertex one by one and update all the shortest paths that
includes the selected vertex as an intermediate vertex in the shortest path.
5. If a vertex k is selected as an intermediate vertex, then {0, 1, 2 ….. k-1}
will be considered as an intermediate vertex automatically.
6. For every pair of vertex (i, j) i.e. source and destination respectively, two
cases are possible:
a. k is not an intermediate vertex between i and j. The value of the
distance between i and j dist[i][j] will remain the same.
b. if k is an intermediate vertex between i and j. The value of dist[i][j]
will become dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]
7. End.

Psuedo Code
n = no of vertices
D = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Dk[i, j] = min (Dk-1[i, j], Dk-1[i, k] + Dk-1[k, j])
return D

Complexity
Following are the complexities in the algorithm:
Time Complexity: There are three for loops in the pseudo-code of the
algorithm, so the time complexity will be O (n^3).
Space Complexity: The space complexity of Floyd’s Warshall algorithm is O
(n^2).
 39

0/1 knapsackproblem
Dynamic Programming approach

We are given N items where each item has some weight and profit
associated with it. We are also given a bag with capacity W, [i.e., the bag
can hold at most W weight in it]. The target is to put the items into the
bag such that the sum of profits associated with them is the maximum
possible.

The constraint here is we can either put an item completely into the bag
or cannot put it at all [It is not possible to put a part of an item into the
bag].

FRACTIONAL Vs 0/1 KNAPSACK

Let the CAPACITY =6

OBJECTS OB OB OB
1 2 3
PROFIT 10 12 28
WEIGHT 1 2 4
PROFIT/WEIGHT 10 6 7

Object OB1 – 1 UNIT OB3 – 4 UNITS OB2 1 UNIT

Corresponding profit 10 28 6
Total profit = 10 + 28 + 6 = 44(Using Greedy approach, and fraction)
If the same approach is used for 0/1 knapsack:
Object OB1 – 1 UNIT OB3 – 4 UNITS OB2 can’t fit because capacity
left is 1 ob2 size is 2 units
Corresponding 10 28
profit
Total profit = 10 + 28 = 38
But, if weights are selected in other way instead of greedy method we
getOB3 – 4 UNITS, OB2 – 2 UNITS, 28+12 =40
Here it denotes that greedy method fails in case of 0/1 knapsack.
• In case of greedy method the time complexity is O(nlogn) it is
polynomial but as it is failing so we try dynamic programming
In Order to apply dynamic programming, we must identify
• Recursive equation.
• Optimal substructure
• Overlapping sub problems.
Recursive Equation for0/1 KNAP SACK PROBLEM
KS(i,w) Denotes i elements, w is the capacity of the bag
pi ,wi are profit and weight of ith object
 40

Recursive Tree

For avoiding repetitive calls to solve same subproblems, we use tabulation

method
Let the capacity =6

STEP 1 : KS (i,w) =0 ;i=0: w=0

 41

STEP 2 : KS (i,w) ; i=1: w=1..6

On applying recursive equationwe get the solution as

follows

STEP 3 : KS (i,w) ; i=2; w=1..6

 42

STEP 4 : KS (i,w) i=3; w=1..6

Hence the optimum profit obtained for the problem is 40

Bottom Up dynamic programming Algofor 0/1 knapsack problem
Input : {w1 , w2, w3,…….wn}, c , {p1,p2,p3…….pn}
Output : T(n,c)
For (i=0 to c) do
T[0,i] = 0
For (i=1 to n ) do
T[i,0]=0
For (j=1 to c) do
if (if wi<=j) and T[i-1], j-wi] +pi > T[i-1,j] Then
T[i,j] = T[i-1], j-wi] +pi
else
T[i,j] = T[i-1,j]
Analysis for 0/1 knapsack algorithm
Here the Time complexity is O(nw)
Where n is number of objects
w is weights
O(nw) looks like linear but it is true when w is constant
Here w is variable, if w is largei.e equal to 2 n then the time complexity
becomes
O(nx 2n) it is very huge again. Hence we can go with brute force method
O(2n )
Sothe time complexity is
 43

Min of { O(nw) , O(2n ))

Space complexity also O(nw) table size

Optimal ca Search Tree Algorithm

(Dynamic programming Approach)

 In Binary search tree, the nodes in the left subtree have lesser
value than the root node and the nodes in the right subtree have
greater value than the root node.
 If we know the key values and the frequencies of each node we can
determine the overall cost of searching a node. The cost of
searching is a very important factor in various applications. The
overall cost of searching a node should be less.
 The time required to search a node in BST is more than the
balanced binary search tree as a balanced binary search tree
contains a lesser number of levels than the BST. There is one way
that can reduce the cost of a binary search tree is known as an
optimal binary search tree.
 For example: 10, 20, 30 are the keys, and the following are the
binary search trees that can be made out from these keys.
2n
The Formula for calculating the number of trees: Cn
n+1

 Let the Keys: 10 20 30 and number of elements (n)=3, the number

of binary search trees possible are:

2X3
C3 6 C 3
= =5
3+1 4
If we find the cost for searching an element based on its level. The height
balanced binary search tree is providing the less cost.

But if we consider the frequencies of the elements in the binary search

tree, there may be a tree structure which may give less cost than the
height balanced binary search tree. Such a BST can be treated as optimal
binary search tree.Finding such tree is the problem statement
 44

Example:

KEY 1 2 3
0 0 0
FREQUENCY 3 2 5

30, 10 , 20 element sequence is giving optimal solution

Dynamic Approach
Consider the below table, which contains the keys and frequencies.
index 1 2 3 4
key value 10 20 30 40
freq 4 2 6 3
Obtain the cost value for each pair of keys and store the values in a table.
Step 1:
 We will calculate the values where j-i is equal to zero.
 Therefore, c[0, 0] = 0, c[1 , 1] = 0, c[2,2] = 0, c[3,3] = 0, c[4,4] = 0

Step 2:
Now we will calculate the values where j-i equal to 1.
Now to calculate the cost, we will consider only the jth value.
The cost of c[0,1] is 4 (The key is 10).
The cost of c[1,2] is 2 (The key is 20).
The cost of c[2,3] is 6 (The key is 30).
The cost of c[3,4] is 3 (The key is 40).
Step 3:
Now we will calculate the values where j-i = 2
In this case, we will consider two keys.
 45

Step 4
Now we will calculate the values when j-i = 3
When j=3, i=0 then j-i = 3
When j=4, i=1 then j-i = 3
When i=0, j=3 then we consider 1,2,3 as roots and weight w[0,3] is
(4+2+6)
When i=1, j=4, then we consider 2,3,4 as roots and weight w[1,4] is
(2+6+3)

Step 5
When j=4 and i=0 then j-i = 4
In this case, we will consider four keys, i.e., 10, 20, 30 and 40. The
frequencies of 10, 20, 30 and 40 are 4, 2, 6 and 3 respectively.
w[0, 4] = 4 + 2 + 6 + 3 = 15
 46

Finally the table is as follows.

Construction of Binary search tree from the above table:

Keys as elements Optimal binary search tree with

R[0,4] denotes root value at the given values
0,4 in the table

General formula for calculating the minimum cost is:

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)
 47

Optimal Substructure:
• Here the task can be divided into sub problems and the solutions to
the sub problems are combined to give the final solution
Overlapping sub problems
• Here if we observe the sub problems are repeated.
• Hence by using Tabulation method, we can avoid repetitive calls to
same sub problem solution. And the time complexity can be
reduced
Time Complexity:
• The time complexity of OBST ALGO. is O(n2) as we are traversing a
matrix of size n x n. Although we are traversing the upper triangular
half only, In asymptotic analysis it is taken as O(n 2)
Space Complexity:
• The space complexity will be O(n2) because we have created a dp
matrix of size n x n.
Algorithm: Step 1 : Read n symbols with probability Pi

Step 2 : Create a table C[i,j]

Step 3 : Assign the diagonal with Zeros.
Step 4 : Recursively compute the cost with
the following equation
C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)
Step 5: Return C[0,n] as optimum cost for BST
Step 6: End

EXAMPLE 2:
48
49
50
51
52
 53

Travelling Salesman Problem (TSP)

DYNAMIC PROGRAMMING APPROACH
• Travelling Salesman Problem (TSP) is a classic combinatorics problem of
theoretical computer science. The problem asks to find the shortest
path in a graph with the condition of visiting all the nodes only one time
and returning to the origin city.
• The problem statement gives a list of cities along with the distances
between each city.
Objective
• To start from the origin city, visit other cities only once, and return to the
original city again. Our target is to find the shortest possible path to
complete the round-trip route.
Example:

For the above graph, the optimal route is to follow the minimum cost path: 1-
2-4-3-1. And this shortest route would cost 10+25+30+15 =80
Adjacency matrix for the above graph is:
 54

How The Algorithm Works:

Step 1)We are considering our journey starting at city 1, visit other cities
once and return to city 1.

will set the distance cost(i, S, 1) = ∝.

Step 2) S is the subset of cities. According to our algorithm, for all |S| > 1, we

Here cost(i, S, j) means we are starting at city i, visiting the cities of

S once, and now we are at city j. We set this path cost as infinity
because we do not know the distance yet. So the values will be the
following:
Cost (2, {3, 4}, 1) = ∝ ;the notation denotes we are starting at city 2, going
through cities 3, 4, and reaching 1. And the path cost is infinity. Similarly-
cost(3, {2, 4}, 1) = ∝
cost(4, {2, 3}, 1) = ∝
Step 3)
Now, for all subsets of S, we need to find the following:
cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j), where j∈S and i≠j
That means the minimum cost path for starting at i, going through the subset
of cities once, and returning to city j.
Considering that the journey starts at city 1, the optimal path cost would be=
cost(1, {other cities}, 1).
Let’s find out how we could achieve that:
Now S = {1, 2, 3, 4}. There are four elements. Hence the number of
subsets will be 2^4 or 16. Those subsets are-
1) |S| = Null:
{Φ}
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4:
{{1, 2, 3, 4}}
As we are starting at 1, we could discard the subsets containing city 1.
The algorithm calculation:
 55

1) |S| = Φ:
cost (2, Φ, 1) = dist(2, 1) = 10
cost (3, Φ, 1) = dist(3, 1) = 15
cost (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
cost (2, {3}, 1) = dist(2, 3) + cost (3, Φ, 1) = 35+15 = 50
cost (2, {4}, 1) = dist(2, 4) + cost (4, Φ, 1) = 25+20 = 45
cost (3, {2}, 1) = dist(3, 2) + cost (2, Φ, 1) = 35+10 = 45
cost (3, {4}, 1) = dist(3, 4) + cost (4, Φ, 1) = 30+20 = 50
cost (4, {2}, 1) = dist(4, 2) + cost (2, Φ, 1) = 25+10 = 35
cost (4, {3}, 1) = dist(4, 3) + cost (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
cost (2, {3, 4}, 1) = min [ dist[2,3]+Cost(3,{4},1) = 35+50 = 85,
dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70
cost (3, {2, 4}, 1) = min [ dist[3,2]+Cost(2,{4},1) = 35+45 = 80,
dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65
cost (4, {2, 3}, 1) = min [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75,
dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
cost (1, {2, 3, 4}, 1) = min [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80
dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80
dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80
So the optimal solution would be
1-2-4-3-1
1-3-4-2-1
 56

Algorithm for Traveling Salesman Problem

• A graph G=(V, E), which is a set of vertices and edges.
• V is the set of vertices.
• E is the set of edges.
• Vertices are connected through edges.
• Dist(i,j) denotes the non-negative distance between two vertices, i and j.

2. When |S| > 1, we define cost(i, S, 1) = ∝ where i !=1 . Because initially,

1. Set cost(i, , i) = 0, which means we start and end at i, and the cost is 0.

we do not know the exact cost to reach city i to city 1 through other
cities.
3. Now, we need to start at 1 and complete the tour. We need to select the
next city in such a way-
4. cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j) where i∈S and i≠j
5. end
Complexity Analysis of TSP
Time Complexity: There are a total of 2N subproblems for each node. So the
total number of subproblems would be N*2 N. Each of the sub-problems
requires linear time to solve. If the origin node is not specified, we have to run
loops for N nodes. So the total time complexity for an optimal solution would
be the Number of nodes * Number of subproblems * time to solve each sub-
problem. The time complexity can be defined as O(N2 * 2^N).
Space Complexity: The dynamic programming approach uses memory to
store C(S, i), where S is a subset of the vertices set. There is a total of 2 N
subsets for each node. So, the space complexity is O(2^N).
 57

Reliability Design Problem in Dynamic Programming

The reliability design problem is the designing of a system composed of

several devices connected in series or parallel. Reliability means the
probability to get the success of the device.

Let’s say, we have to set up a system consisting of D1, D2, D3, …………, and
Dndevices, each device has some costs C1, C2, C3, …….., Cn. Each device has a
reliability of 0.9 then the entire system has reliability which is equal to the
product of the reliabilities of all devices i.e., πri= (0.9)4. (for 4 devices)

Serial Combination of one copy of each device

It means that 35% of the system has a chance to fail, due to the failure of any
one device. the problem is that we want to construct a system whose
reliability is maximum. Here in order to increase the reliability we can take
more than one copy of each device so that if one device fails, the copy of that
device works, which means we connect the copies of devices parallel.

When the same type of 3 devices is connected parallelly in stage 1 having a

reliability 0.9 each then:

Reliability of device1, r1= 0.9

The probability that device does not work well = 1 – r1 = 1 – 0.9 = 0.1

The probability that all three copies failed = ( 1-r 1 )3 = (0.1)3 = 0.001

The Probability that all three copies work properly = 1 – (1- r1)3 = 1- 0.001 =
0.999

We can see that the system with multiple copies of the same device parallel
may increase the reliability of the system.

Multiple copies of the same device type are connected in parallel through the
use of a switching circuit
 58

Given a cost C and we have to set up a system by buying the devices

and we need to find number of copies of each device under the cost
such that reliability of a system is maximized.

We have to design a three-stage system with device types D1, D2, and D3.
The costs are $30, $15, and $20 respectively. The cost of the system is to be
no more than $105. The reliability of each device type is 0.9, 0.8, and 0.5
respectively.

Pi Ci ri
P1 30 0.9
P2 15 0.8
P3 20 0.5

Explanation:

Given that we have total cost C = 105,

sum of all Ci = 30 + 15 + 20 = 65, the remaining amount we can use to buy a

copy of each device in such a way that the reliability of the system, may
increase.

Remaining amount = C – sum of Ci = 105 – 65 = 40

Now, let us calculate how many copies of each device we can buy with $40, If
consume all $40 in device1 then we can buy 40/30 = 1 and 1 copy we have
already so overall 2 copies of device1. Now In general, we can have the
formula to calculate the upper bond of each device:

Ui = floor( C – ∑Ci / Ci ) + 1 (1 is added because we have one copy of

each device before)

C1=30, C2=15, C3=20, C=105

r1=0.9, r2=0.8, r3=0.5
u1 = floor ((105+30-(30+15+20))/30) = 2
u2 = 3
u3 = 3

A tuple is just an ordered pair containing reliability and total cost up to a

choice of mi’s that has been made. we can make pair in of Reliability and Cost
device
of each stage like copyS

S0 = {(1,0)}

Device 1:

Each Si from Si-1 by trying out all possible values for ri and combining the
resulting tuples together.

 let us consider P1 :
 59

o S1 = {(0.9, 30)} where 0.9 is the reliability of stage1 with a

1
copy of one device and 30 is the cost of P1.
 Now, two copies of device1 so, we can take one more copy as:
o 2S1 = { (0.99, 60) } where 0.99 is the reliability of stage one
with two copies of device, we can see that it will come as:

1 – ( 1 – r1 )2 = 1 – (1 – 0.9)2 = 1 – 0.01 = 0.99 .

 After combining both conditions of Stage1 i.e., with copy one and copy
of 2 devices respectively.

S1 = { ( 0.9, 30 ), ( 0.99, 60 ) }

Device 2:

S2 will contain all reliability and cost pairs that we will get by taking all
possible values for the stage2 in conjunction with possibilities calculated in S 1.

First of all we will check the reliability at stage2 when we have 1, 2, and 3 as a
copy of device. let us assume that Ei is the reliability of the particular stage
with n number of devices, so for S2 we first calculate:

 E2 (with copy 1) = 1 – ( 1 – r2 )1 = 1 – ( 1 – 0.8 ) = 0.8

 E2 (with copy 2) = 1 – (1 – r2 )2 =1 – (1 – 0.8 )2= 0.96
 E2 (with copy 3) = 1 – (1 – r2 )3 = 1 – ( 1 – 0.8 )3 = 0.992

P1 1 COPY P1 2 COPIES
0.9 30 0.99 60

P2 1 COPY 0.8 15 0.72 45 0.792 75

P2 2 COPIES 0.96 30 0.864 60 0.9504 90
P2 3 COPIES 0.992 45 0.8928 75 0.98208 105

S2 = { ( 0.72, 45 ), ( 0.864,60), (0.8928,75) }

Device 3:

First of all we will check the reliability at stage3 when we have 1, 2, and 3 as a
copy of device. Ei is the reliability of the particular stage with n number of
devices, so for S3 we first calculate:

 E3 (with copy 1) = 1 – ( 1 – r3 )1 = 1 – ( 1 – 0.5 ) = 0.5

 E3 (with copy 2) = 1 – (1 – r3 )2 = 1 – (1 – 0.5 )2 = 0.75
 E3 (with copy 3) = 1 – (1 – r3 )3 = 1 – ( 1 – 0.5 )3= 0.875

S2 0.72 45 0.864 60 0.8928 75

 60

P3 1 COPY 0.5 20 0.36 65 0.432 80 0.4464 95

P3 2 COPIES 0.75 40 0.54 85 0.648 100 0.6696 115
P3 3 COPIES 0.875 60 0.63 105 0.756 120 0.7812 135

{(0.36, 65) (0.432 ,80), (0.4464,95) (0.54, 85) (0.63, 105)

(0.648, 100)}

S3 = {(0.36, 65), (0.432 ,80), (0.54, 85), (0.648, 100)}

Hence Max reliability can be achieved with D1 1 COPY, D2 TWO

COPIES, AND D3 2 COPIES
 61

UNIT - IV
Fractional Knapsack

The knapsack problem states that − given a set of items, holding weights and profit
values, one must determine the subset of the items to be added in a knapsack such
that, the total weight of the items must not exceed the limit of the knapsack and its
total profit value is maximum.

It is one of the most popular problems that take greedy approach to be solved. It is
called as the Fractional Knapsack Problem.

Knapsack Algorithm

The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are
taken as an input for the fractional knapsack algorithm and the subset of the items
added in the knapsack without exceeding the limit and with maximum profit is
achieved as the output.

Algorithm

1. Consider all the items with their weights and profits mentioned
respectively.
2. Calculate Pi/Wi of all the items and sort the items in descending order
based on their Pi/Wi values.
3. Without exceeding the limit, add the items into the knapsack.
4. If the knapsack can still store some weight, but the weights of other items
exceed the limit, the fractional part of the next time can be added.
5. Hence, giving it the name fractional knapsack problem.

Examples

 For the given set of items and the knapsack capacity of 10 kg, find the subset
of the items to be added in the knapsack such that the profit is maximum.

Items 1 2 3 4 5

Weights (in kg) 3 3 2 5 1

Profits 10 15 10 12 8

Solution

Step 1

Given, n = 5

Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}

Calculate Pi/Wi for all the items

 62

Items 1 2 3 4 5

Weights (in kg) 3 3 2 5 1

Profits 10 15 10 20 8

Pi/Wi 3.3 5 5 4 8

Step 2

Arrange all the items in descending order based on P i/Wi

Items 5 2 3 4 1

Weights (in kg) 1 3 2 5 3

Profits 8 15 10 20 10

Pi/Wi 8 5 5 4 3.3

Step 3

Without exceeding the knapsack capacity, insert the items in the knapsack with
maximum profit.

Knapsack = {5, 2, 3}

However, the knapsack can still hold 4 kg weight, but the next item having 5 kg
weight will exceed the capacity. Therefore, only 4 kg weight of the 5 kg will be
added in the knapsack.

Items 5 2 3 4 1

Weights (in kg) 1 3 2 5 3

Profits 8 15 10 20 10

Knapsack 1 1 1 4/5 0

Hence, the knapsack holds the weights = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] =

10, with maximum profit of [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 49.
 63

Job Sequencing with Deadlines (Algorithmwith Example)

The sequencing of jobs on a single processor with deadline constraints is called as

Job Sequencing with Deadlines.
Here-
 We are given a set of jobs.
 Each job has a defined deadline and some profit associated with it.
 The profit of a job is given only when that job is completed within its deadline.
 Only one processor is available for processing all the jobs.
 Processor takes one unit of time to complete a job.
The problem states-
“How can the total profit be maximized if only one job can be completed at a time?”
Greedy Algorithm-
Greedy Algorithm is adopted to determine how the next job is selected for an
optimal solution.
The greedy algorithm described below always gives an optimal solution to the job
sequencing problem-
Step-01:
Sort all the given jobs in decreasing order of their profit.
Step-02:
 Check the value of maximum deadline.
 Draw a Gantt chart where maximum time on Gantt chart is the value of
maximum deadline.
Step-03:
 Pick up the jobs one by one.
 Put the job on Gantt chart as far as possible from 0 ensuring that the job gets
completed before its deadline.
Example
Given the jobs, their deadlines and associated profits as shown-
Jobs J1 J2 J3 J4 J5 J6
Deadlines 5 3 3 2 4 2
Profits 200 180 190 300 120 100
Step-01:

Sort all the given jobs in decreasing order of their profit-

Jobs J4 J1 J3 J2 J5 J6

Deadlines 2 5 3 3 4 2

Profits 300 200 190 180 120 100

Step-02:
Value of maximum deadline = 5.
 64

So, draw a Gantt chart with maximum time on Gantt chart = 5 units as
shown-

Now,
We take each job one by one in the order they appear in Step-01.
We place the job on Gantt chart as far as possible from 0.
Step-03:
We take job J4.
Since its deadline is 2, so we place it in the first empty cell before deadline 2
as-

Step-04:
We take job J1.
Since its deadline is 5, so we place it in the first empty cell before deadline 5
as-

Step-05:
We take job J3.
Since its deadline is 3, so we place it in the first empty cell before deadline 3
as-

Step-06:
We take job J2.
Since its deadline is 3, so we place it in the first empty cell before deadline 3.
Since the second and third cells are already filled, so we place job J2 in the
first cell as-

Step-07:
 65

Now, we take job J5.

Since its deadline is 4, so we place it in the first empty cell before deadline 4
as-

Now,

The only job left is job J6 whose deadline is 2.

All the slots before deadline 2 are already occupied.
Thus, job J6 can not be completed.
The optimal schedule is-

J2 , J4 , J3 , J5 , J1

This is the required order in which the jobs must be completed in order to
obtain the maximum profit.
Maximum earned profit
= Sum of profit of all the jobs in optimal schedule
= Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5 + Profit of job J1
= 180 + 300 + 190 + 120 + 200
= 990 units
Time and space Complexity:
The time complexity for the above job scheduling algorithm is O(n 2) in the
worst case when we will look for all the slots in the Gantt chart for a given job
id and on average, n jobs search n/2 slots. So, this would also take O(n 2) time
approximately O(n2)time in the best and average cases. Space complexity is
O(n) as extra space is used in the above implementation.
 66

Minimum cost spanning treeAlgorithms -Greedy approach

Spanning Tree
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)
Minimum cost Spanning Tree
The cost of the spanning tree is the sum of the weights of all the edges in the tree.
There can be many spanning trees. Minimum spanning tree is the spanning tree
where the cost is minimum among all the spanning trees. There also can be many
minimum spanning trees.

There are two famous algorithms for finding the Minimum Spanning Tree:
Kruskal’s Algorithm
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a
growing spanning tree. Kruskal's algorithm follows greedy approach as in each
iteration it finds an edge which has least weight and add it to the growing spanning
tree.
Algorithm Steps:
 Sort the graph edges with respect to their weights.
 Start adding edges to the MST from the edge with the smallest weight until
the edge of the largest weight.
 Only add edges which doesn't form a cycle , edges which connect only
disconnected components.
Consider following example:
 67

Step Description

4
 68

Pseudo code
 69

Prim’s Algorithm
Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In
Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an
edge in Kruskal's, we add vertex to the growing spanning tree in Prim's.
Algorithm Steps:
 Maintain two disjoint sets of vertices. One containing vertices that are in the
growing spanning tree and other that are not in the growing spanning tree.
 Select the cheapest vertex that is connected to the growing spanning tree
and is not in the growing spanning tree and add it into the growing spanning
tree. This can be done using Priority Queues. Insert the vertices, that are
connected to growing spanning tree, into the Priority Queue.
 Check for cycles. To do that, mark the nodes which have been already
selected and insert only those nodes in the Priority Queue that are not
marked.
Consider the example below:

Step Description

1
 70

4
 71

Pseudo code
72
 73

Single source shortest path problem -Greedy approach

Dijkstra Algorithm-
 Dijkstra Algorithm is a very famous greedy algorithm.
 It is used for solving the single source shortest path problem.
 It computes the shortest path from one particular source node to all other
remaining nodes of the graph.
Single-Source Shortest Paths – Dijkstra’s Algorithm
Given a source vertex s from a set of vertices V in a weighted digraph where all its
edge weights w(u, v) are non-negative, find the shortest path weights d(s, v) from
source s for all vertices v present in the graph.
For example,
Vertex Minimum Cost Route

A —> B 4 A —> E —> B

A —> C 6 A —> E —> B —> C

A —> D 5 A —> E —> D

A —> E 3 A —> E

Example:
For instance, consider the following graph. We will start with vertex A, So vertex A
has a distance 0, and the remaining vertices have an undefined (infinite) distance
from the source. Let S be the set of vertices whose shortest path distances from the
source are to be calculated.

Initially, S contains the source vertex. S = {A}.

 74

We start from source vertex A and start relaxing A'sneighbors. Since vertex B can
be reached from a direct edge from vertex A, update its distance to 10 (weight of
edge A–B). Similarly, we can reach vertex E through a direct edge from A, so we
update its distance from INFINITY to 3.

After processing all outgoing edges of A, we next consider a vertex having minimum
distance. B has a distance of 10, E has distance 3, and all remaining vertices have
distance INFINITY. So, we choose E and push it into set S. Now our set becomes S =
{A, E}. Next, we relax with E'sneighbors. E has 3neighborsB,Cand D. We have
already found one route to vertex B through vertex A having cost 10. But if we visit
a vertex B through vertex E, we are getting an even cheaper route, i.e., (cost of
edge A–E + cost of edge E–B) = 3 + 1 = 4 < 10 (cost of edge A–B).

We repeat the process till we have processed all the vertices, i.e., Set S becomes
full.
75
 76

Following is pseudocode for Dijkstra’s Algorithm

function Dijkstra(Graph, source)

dist[source] = 0 // Initialization
create vertex set Q

for each vertex v in Graph

{
if v != source
{
dist[v] = INFINITY // Unknown distance from source to v
prev[v] = UNDEFINED // Predecessor of v
}
Q.add_with_priority(v, dist[v])
}
while Q is not empty
{
u = Q.extract_min() // Remove minimum
for each neighbor v of u that is still in Q
{
alt = dist[u] + length(u, v)
if alt < dist[v]
{
dist[v] = alt
prev[v] = u
Q.decrease_priority(v, alt)
}
}
}
return dist[], prev[]

Dijkstra’s algorithm runs in O(E.log(V)) time like Prim’s algorithm. Here, E is the
total number of edges, and V is the graph’s number of vertices.
 77

Limitation of Dijkstra’s algorithm:

Dijkstra’s algorithm works on negative weight edges but can’t detect negative weight edge
cycles. It can’t find shortest path when a negative weight edge cycle is present.
Example:

Here it works properly, even though there is negative weight edge.

Consider the following Example with negative weight edge cycle.

Here, we are not going to relax ‘C’. Because, it is already found that 3 is the smallest path.
If we relax it is giving 2.

If the negative weight edge=-6 the path from D  B will be ‘0’ it is better than ‘1’ at B.
Hence, it is clear that Dijkstra’s algorithm will not find shortest path when there is negative
weight edge cycles
 78

UNIT –V
Travelling Salesman Problem - using Branch and Bound
Travelling Salesman Problem (TSP) is an interesting problem. Problem is defined as
“given n cities and distance between each pair of cities, find out the path which
visits each city exactly once and come back to starting city, with the constraint of
minimizing the travelling distance.”
TSP has many practical applications. It is used in network design, and transportation
route design. The objective is to minimize the distance.
Consider directed weighted graph G = (V, E, W), where node represents cities and
weighted directed edges represents direction and distance between two cities.
1. Initially, graph is represented by cost matrix C.
2. Convert cost matrix to reduced matrix by subtracting minimum values from
appropriate rows and columns, such that each row and column contains at
least one zero entry.
3. Find cost of reduced matrix. Cost is given by summation of subtracted
amount from the cost matrix to convert it in to reduce matrix.
4. Prepare state space tree for the reduce matrix
5. Find least cost valued node A (i.e. E-node), by computing reduced cost node
matrix with every remaining node.
6. If <i, j> edge is to be included, then do following :
a. Set all values in row i and all values in column j of A to ∞
b. Set A[j, 1] = ∞
c. Reduce A again, except rows and columns having all ∞ entries.
7. Compute the cost of newly created reduced matrix as,
8. Cost = L + Cost(i, j) + r
9. Where, L is cost of original reduced cost matrix and r is cost computed
10. If all nodes are not visited then go to step 4.

Reduction procedure is described below:

Row Reduction:

Matrix M is called reduced matrix if each of its row and column has at least one zero
entry or entire row or entire column has ∞ value. Let M represents the distance
matrix of 5 cities. M can be reduced as follow:

MRowRed = {Mij – min {Mij | 1 ≤ j ≤ n, and Mij<∞ }}

Consider the following distance matrix:

 79

Find the minimum element from each row and subtract it from each cell of matrix.

Reduced matrix would be:

Row reduction cost is the summation of all the values subtracted from each rows:

Row reduction cost (M) = 10 + 2 + 2 + 3 + 4 = 21

Column reduction:

Matrix MRowRed is row reduced but not the column reduced. Matrix is called column
reduced if each of its column has at least one zero entry or all ∞ entries.

MColRed= {Mji – min {Mji | 1 ≤ j ≤ n, and Mji<∞ }}

To reduced above matrix, we will find the minimum element from each column and
subtract it from each cell of matrix.
 80

Column reduced matrix MColRed would be:

Each row and column of M ColRed has at least one zero entry, so this matrix is reduced
matrix, let us call the matrix as M1

Column reduction cost (M) = 1 + 0 + 3 + 0 + 0 = 4

Cost of M1 = C(1) = Row reduction cost + Column reduction cost

= (10 + 2 + 2 + 3 + 4) + (1 + 3) = 25

This means all tours in graph has length at least 25. This is the optimal cost of the
path.

State space tree

 81

Let us find cost of edge from node 1 to 2, 3, 4, 5.

Select edge 1-2:

Set M1 [1] [ ] = M1 [ ] [2] = ∞

Set M1 [2] [1] = ∞

Reduce the resultant matrix if required.

M2 is already reduced.

Cost of node 2 :

C(2) = C(1) + Reduction cost + M1 [1] [2]

= 25 + 0 + 10 = 35

Select edge 1-3

Set M1 [1][ ] = M1 [ ] [3] = ∞

Set M1 [3][1] = ∞

Reduce the resultant matrix if required.

 82

Cost of node 3:

C(3) = C(1) + Reduction cost + M1[1] [3]

= 25 + 11 + 17 = 53

Select edge 1-4:

Set M1 [1][ ] = M1[ ][4] = ∞

Set M1 [4][1] = ∞

Reduce resultant matrix if required.

Matrix M4 is already reduced.

Cost of node 4:

C(4) = C(1) + Reduction cost + M1 [1] [4]

= 25 + 0 + 0 = 25

Select edge 1-5:

 83

Set M1 [1] [ ] = M1 [ ] [5] = ∞

Set M1 [5] [1] = ∞

Reduce the resultant matrix if required.

Cost of node 5:

C(5) = C(1) + reduction cost + M1 [1] [5]

= 25 + 5 + 1 = 31

State space diagram:

Node 4 has minimum cost for path 1-4. We can go to vertex 2, 3 or 5. Let’s explore
all three nodes.

Select path 1-4-2 : (Add edge 4-2)

Set M4 [1] [] = M4 [4] [] = M4 [] [2] = ∞

Set M4 [2] [1] = ∞

Reduce resultant matrix if required.

 84

Matrix M6 is already reduced.

Cost of node 6:

C(6) = C(4) + Reduction cost + M4 [4] [2]

= 25 + 0 + 3 = 28

Select edge 4-3 (Path 1-4-3):

Set M4 [1] [ ] = M4 [4] [ ] = M4 [ ] [3] = ∞

Set M [3][1] = ∞

Reduce the resultant matrix if required.

M‘7 is not reduced. Reduce it by subtracting 11 from column 1.

 85

Cost of node 7:

C(7) = C(4) + Reduction cost + M4 [4] [3]

= 25 + 2 + 11 + 12 = 50

Select edge 4-5 (Path 1-4-5):

Matrix M8 is reduced.

Cost of node 8:

C(8) = C(4) + Reduction cost + M4 [4][5]

= 25 + 11 + 0 = 36

State space tree

Path 1-4-2 leads to minimum cost. Let’s find the cost for two possible paths.
 86

Add edge 2-3 (Path 1-4-2-3):

Set M6 [1][ ] = M6 [4][ ] = M6 [2][ ]

= M6 [][3] = ∞

Set M6 [3][1] = ∞

Reduce resultant matrix if required.

 87

Cost of node 9:

C(9) = C(6) + Reduction cost + M6 [2][3]

= 28 + 11 + 2 + 11 = 52

Add edge 2-5 (Path 1-4-2-5):

Set M6 [1][ ] = M6 [4][ ] = M6 [2][ ] = M6 [ ][5] = ∞

Set M6 [5][1] = ∞

Reduce resultant matrix if required.

Cost of node 10:

C(10) = C(6) + Reduction cost + M6 [2][5]

= 28 + 0 + 0 = 28

State space tree

 88

Add edge 5-3 (Path 1-4-2-5-3):

Cost of node 11:

C(11) = C(10) + Reduction cost + M10 [5][3]

= 28 + 0 + 0 = 28

State space tree:

89
 90

LCBB for Knapsack (least cost branch and bound for knapsack)
LC branch and bound solution for knapsack problem is derived as follows:
1. Derive state space tree.
2. Compute lower bound c^ and upper bound (u)
for each node in state space tree.
3. If lower bound is greater than upper bound than kill that node.
4. Else select node with minimum lower bound as E-node.
5. Repeat step 3 and 4 until all nodes are examined.
6. The node with minimum lower bound value c^is the answer node.
7. Trace the path from leaf to root in the backward direction to find the solution
tuple.
Example:
Consider an instance of knapsack using LCBB for knapsack capacity
M = 15.
i 1 2 3 4
Pi 10 10 12 18
Wi 2 4 6 9

Let us compute u(1) andc^(1)

u(1) =– (p1 + p2 + p3)
= -(10 + 10 + 12) = – 32

c^(1)=−32–15–(2+4+6)/9∗18
= -38

Node 2 : Inclusion of item 1 at node 1

Inclusion of item 1 is compulsory. So we will end up with same items in previous step.
u(2) = – (p1 + p2 + p3) = – (10 + 10 + 12) = – 32
c^(2)=−32–15–(2+4+6)/9∗18
= -38
Node 2 is inserted in list of live nodes.
Node 3 : Exclusion of item 1 at node 1
We are excluding item 1 and including 2 and 3. Item 4 cannot be accommodated in
knapsack along with items 2 and 3. So,
u(3) = -(p2 + p3) = – (10 + 12) = – 22
c^(3)=−22–15–(4+6)/9∗18
= -32
 91

Node 3 is inserted in the list of live nodes.

State-space tree:

At level 1, node 2 has minimum c^, so it becomes E-node.

Node 4 : Inclusion of item 2 at node 2

Item 1 is already added at node 2, and we must have to include item 2 at this node.
After adding items 1 and 2, the knapsack can accommodate item 3 but not 4.
u(4) = – (p1 + p2 + p3) = – (10 + 10 + 12) = – 32
c^(4)=−32–15–(2+4+6)/9∗18
= -38
Node 5: Exclusion of item 2 at node 2
At node 5, item 1 is already added, we must have to skip item 2. Only item 3 can be
accommodated in knapsack after inserting item 1.
u(5) =- (p1 + p3) = – (10 + 12) = – 22
c^(5)=−22–15–(2+6)/9∗18
= -36
State Space Tree:

At level 2, node 4 has minimum c^, so it becomes E-node.

Node 6 : Inclusion of item 3 at node 4

At node 4, item 1 and 2 are already added, we have to add item 3. After including
item 1, 2 and 3, item 4 cannot be accommodated.
u(6) = – (10 + 10 + 12) = – 32
c^(6)=−32–15–(2+4+6)/9∗18
= -38
Node 7 : Exclusion of item 3 at node 4
 92

On excluding item 3, we can accommodate item 1, 2 and 4 in knapsack.

u(7) = -(10 + 10 + 18) = – 38
c^(7)=−38–15–(2+4+9)/6∗12
= -38

State Space Tree:

When there is tie, we can select any node. Let’s make node 7 E-node.
Node 8 : Inclusion of item 4 at node 7
u(8) = -(10 + 10 + 18) = – 38
c^(8)=−38–15–(2+4+9)/6∗12
= -38
Node 9 : Exclusion of item 4 at node 7
This node excludes both the items, 3 and 4. We can add only item 1 and 2.
u(9) = -(10 + 10) = – 20
c^=−20–15–(2+4)0∗0 (no fraction)
= -20
At last level, node 8 has minimum c^, so node 8 would be the answer node. By
tracing from node 8 to root, we get item 4, 2 and 1 in the knapsack.
Solution vector X = {x1, x2, x4} and profit = p1 + p2 + p4 = 38
 93

Time Complexity: O(N), as only one path through the tree will have to be traversed in the
beat case and its worst time complexity is still given as O(2 N) .
 94

Branch and bound for Knapsack FIFO

In FIFO branch and bound approach, both the children of siblings are inserted in list
and most promising node is selected as new E node.
Example:
Consider an instance of knapsack using LCBB for knapsack capacity
M = 15.
i 1 2 3 4
Pi 10 10 12 18
Wi 2 4 6 9

u(1) = – (10 + 10 + 12) = – 32

Upper = u(1) = – 32

If we include the first three items then

C^(1)=−32–15–(2+4+6)/9∗18
= -38

State space tree:

Node 2 : Inclusion of item 1 at node 1

u(2) = -(10 + 10 + 12) = – 32

C^=−32–15–(2+4+6)/9∗18
= -38

Node 3 : Exclusion of item 1 at node 1

We are excluding item 1, including 2 and 3. Item 4 cannot be accommodated in a

knapsack along with 2 and 3.

u(3) = -(10 + 12) = – 22

c^(3)=−22–15–(4+6)/9∗18
= -32
 95

In LC approach, node 2 would be selected as E-Node as it has minimum ( ×). But in

FIFO approach, all children of node 2 and 3 are expanded and the most promising
child becomes E-node.

Node 4 : Inclusion of item 2 at node 2

u(4) = -(10 + 10 + 12) = – 32

C^ =−32–15–(2+4+6)/9∗18
= -38

Node 5 : Exclusion of item 2 at node 2

u(5) = -(10 + 12) = – 22

C^(5)=−22–15–(2+6)/9∗18
= -36

Node 6 : Inclusion of item 2 at node 3

u(6) = -(p2 + p3) = – (10 + 12) = – 22

C^(6)=−22–15–(4+6)/9∗18
= -32

Node 7 : Exclusion of item 2 at node 3

u(7) = -(p3 + p4) = – (12 + 18) = – 30

C^(7)=−30–0
= -30
 96

Out of node 4, 5, 6 and 7, C^(7) > upper, so kill node 7. Remaining 3 nodes are
alive and added in list. Out of 4, 5 and 6, node 4 has minimum c^ value, so it
becomes next E-node.

Node 8 : Inclusion of item 3 at node 4

u(8) = -(10 + 10 + 12) = – 32

c^(8)=−32–15–(2+4+6)/9∗18
= -38

Node 9 : Exclusion of item 3 at node 4

We are excluding item 3, including 1 and 2 and 4.

u(9) = -(p1 + p2 + p4) = – (10 + 10 + 18) = – 38

c^(9)=−38–0
= -38

Upper = u(9) = – 38.

C^(5)> upper and c^(6)> upper, so kill them. If we continue in this way, final state
space tree looks as follow :
 97

Solution vector = {x1, x2, x4},

profit = 10 + 10 + 18 = 38
 98

Types of Problems:

 Decidable problems
 Undecidable problems.

Decidable Problems:

 For these problems algorithm exists

 These problems can be divided into 2 types

Tractable

If there exist at least one polynomial bound algorithm O(n k), it is

tractable. K is any value 100, 1000. If k is some value. If k is some
value we know, later some one tries to reduce k with algorithms

Intractable

If a problem is not tractable then it is intractable, it means if you are

not able to find and algorithm that can run in polynomial time eg.
O(nlogn), O(Cn)

Here as n increases, the time taken to run an algorithm increases a lot.

O(2n) ie. Exponential time algorithm. Example : Travelling Sales man
problem O(n22n)

Here, we write an algorithm and run it, but it is useless. Because, as

size of input increases, the running time of algorithm increases a lot. So
we stop using such algorithm.

For intractable problems, it is not possible to give exact answer in

polynomial time. But we try to give some solution but it may not be the
exact answer. It is approximated.

In travelling salesmen problem, instead of solving shortest path

between all vertices, we give some answer but it is not exact.

Undecidable Problems:

For these problems no algorithms exist

Example : We don’t know whether Turing machine halts or not for some
given input.
 99

Classification of Problems

P – Means For the problems we have polynomial time algorithms

NP – means,As of now there is no polynomial time algorithm. But we don’t

know whether any one give polynomial time algorithm or say it is not
possible to give polynomial time algorithm.

Definitions

The problem is said to be decision problem if they produce output “Yes”

or “No” for given input. An algorithm which solves the decision problem is
called decision algorithm.

An optimization problem aims for the best solution from the set of all
feasible solutions. An algorithm which solves optimization problem is
called optimization algorithms.

The optimization algorithm seeks to find the best profit or least cost
solution. Decision problems are simpler than optimization problems.

Computational complexity: Computational problems have infinite

instances. Each instance in the set contains the solution. Typically, the
solution to the problem in computational complexity is Boolean i.e. ‘Yes’
or ‘No’.

The computational problem can be function problem too. Solution to

such problem differs on each execution even for the same input. So such
problems are more complex than decision problems.
 100

Complexity classes are set of problems of related complexity, like P

problems, NP problems, Decision problems, Optimization problems etc.
The complexity of any problem in given class falls in certain range

Problems which takes practically unacceptable time i.e. very long time to
be solved are called intractable problems.

If the running time of the algorithm is bounded to O(p(n)), where p(n) is

some polynomial in n, where n represents the size of the problem, we say
that the problem has polynomial time complexity.

Satisfiability Problem is to check the correctness of assignment.

Satisfiability problem finds out whether for given input an expression is
true for that assignment

Reducibility : Let P1 and P2 are two problems and there exists some
deterministic algorithm A for P1 such that P1 can be solved in polynomial
time using A. If the same algorithm can solve the problem P 2 then we can
say that P2 is reducible to P1.

P and NP Problems

P and NP Problems are the class of problems. Problems are grouped based
on their complexity.

P-class Problems

 P problems are a set of problems that can be solved in polynomial

time by deterministic algorithms.
 P is also known as PTIME or DTIME complexity class.
 P problems are a set of all decision problems which can be solved in
polynomial time using the deterministic Turing machine.
 They are simple to solve, easy to verify and take computationally
acceptable time for solving any instance of the problem. Such
problems are also known as “tractable”.
 In the worst case, searching an element from the list of size n takes
n comparisons. The number of comparisons increases linearly with
respect to the input size. So linear search is P problem.
 In practice, most of the problems are P problems. Searching an
element in the array (O(n)), inserting an element at the end of a
linked list (O(n)), sorting data using selection sort(O(n 2)), finding the
height of the tree (O(log 2n)), sort data using merge sort(O(nlog 2n)),
matrix multiplication O(n3) are few of the examples of P problems.
 An algorithm with O(2n) complexity takes double the time if it is
tested on a problem of size (n + 1). Such problems do not belong to
class P.
 It excludes all the problems which cannot be solved in polynomial
time. The knapsack problem using the brute force approach cannot
be solved in polynomial time. Hence, it is not a P problem.
 101

 There exist many important problems whose solution is not found in

polynomial time so far, nor it has been proved that such a solution
does not exist. TSP, Graph colouring, partition problem, knapsack
etc. are examples of such classes.
 Examples of P Problems:
 Insertion sort
 Merge sort
 Linear search
 Matrix multiplication
 Finding minimum and maximum elements from the
array

NP-Class of Problems

 NP is a set of problems which can be solved in nondeterministic

polynomial time. NP does not mean non-polynomial, it stands for
Non-Deterministic Polynomial-time.
 The non-deterministic algorithm operates in two stages.
 Nondeterministic (guessing) stage: For input instance I, some
solution string S is generated, which can be thought of as a
candidate solution.
 Deterministic (verification) stage: I and S are given as input to
the deterministic algorithm, which returns “Yes” if S is a solution for
input instance I.
 The solution to NP problems cannot be obtained in polynomial time,

NP includes all problems of P, i.e. P ⊆ NP.

but given the solution, it can be verified in polynomial time.

 Knapsack problem (O(2n)), Travelling salesman problem (O(n!)),
Tower of Hanoi (O(2n – 1)), Hamiltonian cycle (O(n!)) are examples of
NP problems.
 NP Problems are further classified into NP-complete and NP-hard
categories.

The following shows the taxonomy of complexity classes.

 The NP-hard problems are the hardest problem. NP-complete

problems are NP-hard, but the converse is not true.
 If NP-hard problems can be solved in polynomial time, then so is NP-
complete.
 102

Examples of NP problems

 Knapsack problem (O(2n))

 Travelling salesman problem (O(n!))
 Tower of Hanoi (O(2n – 1))
 Hamiltonian cycle (O(n!))

P and NP Problems – Differentiate

Sr.
P Problems NP Problems
No.
P problems are set of
NP problems are problems which can
problems which can be solved
1. be solved in nondeterministic
in polynomial time by
polynomial time.
deterministic algorithms.
The solution to NP problems cannot be
P Problems can be solved and obtained in polynomial time, but if the
2.
verified in polynomial time solution is given, it can be verified in
polynomial time.
P problems are a subset of NP NP Problems are a superset of P
3.
problems problems
All P problems are All the NP problems are non-
4.
deterministic in nature deterministic in nature
Example: Selection sort,
5. Example: TSP, Knapsack problem
Linear search

Deterministic and Non-Deterministic Algorithms

Deterministic and Non-Deterministic Algorithms differ in the way they

produce outputs on multiple executions.
 103

Deterministic Algorithms

 If we run deterministic algorithms multiple times on the same

input, they produce the same result every time.
 Deterministic algorithms are typically represented by the state
machine, where the machine moves from one state to another state
on a specific input.
 The underlying machine always goes through the same states
during execution.
 Finding a random number is deterministic, it always returns a
random number. Finding odd or even, sorting, finding max, etc. are
deterministic. Most of the algorithms used in practice are
deterministic in nature.

Non-deterministic Algorithms

 The non-deterministic algorithm works on guessing. For some

input, nondeterministic algorithms may produce different outcomes
every time.
 The nondeterministic algorithm operates in two phases: guessing
and verification. After guessing the answer, the algorithm verifies its
correctness.
 In the non-deterministic algorithm, each state has a probability of a
different outcome on the same input. The vending machine is an
example of the deterministic approach, in which the outcome
against given input is always deterministic.
 Randomly picking some element from the list and checking if it is
maximum is non-deterministic.
 The nondeterministic algorithm operates in two stages.
 Non-deterministic (guessing) stage : For input instance I, some
solution string S is generated, which can be thought of as a solution.
 Deterministic (verification) stage : I and S are given as input to
the deterministic algorithm, which returns “Yes” if S is a solution for
input instance I.
 Non-deterministic algorithm behaves differently for the same input
on different runs. The concurrent algorithm can produce different
outputs for the same input on different runs due to the race
condition.
 Selecting random permutations of n numbers and checking the
order of numbers is non-deterministic. The first permutation may be
(1, 2, 3), next may be (3, 1, 2), next may be (2, 3, 1) etc.

NP-Complete and NP-Hard Problems

NP-Complete and NP-Hard Problems are interesting classes of problems.
These problems are addressed in different ways by computer scientists.

NP-Complete Problems
 104

 Polynomial time reduction implies that one problem is at least as

hard as another problem, within the polynomial time factor. If A ≤ p B,
implies A is not harder than B by some polynomial factor.
 Decision problem A is called NP-complete if it has the following two
properties :
o It belongs to class NP.

polynomial time, i.e. For every B ∈ NP, B ≤p A.

o Every other problem B in NP can be transformed to A in

 These two facts prove that NP-complete problems are the harder
problems in class NP. They are often referred to as NPC.
 If any NP-complete problem belongs to class P, then
P = NP. However, a solution to any NP-complete problem can be
verified in polynomial time, but cannot be obtained in polynomial
time.
 NP-complete problems are often solved using randomization
algorithms, heuristic approaches or approximation algorithms.
 Some of the well-known NP-complete problems are listed here :
o Boolean satisfiability problem.
o Knapsack problem.
o Hamiltonian path problem.
o Travelling salesman problem.
o Subset sum problem.
o Vertex covers the problem.
o Graph colouring problem.
o Clique problem.

NP-Hard Problem

 Formally, a decision problem p is called NP-hard, if every problem in

NP can be reduced to p in polynomial time.
 NP-hard is a superset of all problems. NPC is in NP-hard, but the
converse may not be true.
 NP-hard problems are at least as hard as the hardest problems in
NP.
 If we can solve any NP-hard problem in polynomial time, we would
be able to solve all the problems in NP in polynomial time.
 NP-hard problems do not have to be in NP. Even they may not be a
decision problem.
 The subset subproblem, the travelling salesman problem is NPC and
also belongs to NP-hard. There are certain problems which belong to
NP-hard but they are not NP-complete.
 A well-known example of the NP-hard problem is the Halting
problem.
 The halting problem is stated as, “Given an algorithm and set of
inputs, will it run forever ?” The answer to this question is Yes or No,
so this is a decision problem.
 105

 There does not exist any known algorithm which can decide the
answer for any given input in polynomial time. So halting problem is
an NP-hard problem.
 Different mathematicians have given different relationships
considering the possibilities of P = NP and P ≠ NP.
 The relationship between P, NP, NP-Complete and NP-hard is
described in below Fig. assuming that P ≠ NP. This is a widely
accepted relationship among these complexity classes.

 Subset sum problem and travelling salesman problem are NPC and
also belong to NP-hard. There are certain problems which belong to
NP-hard but they are not NP-complete. A well-known example of an
NP-hard problem is the Halting problem.
 The halting problem is stated as, “Given the algorithm and set of
inputs, will it run forever ?” The answer to this question is Yes or No,
so this is a decision problem.
 There does not exist any known algorithm which can decide the
answer for any given input in polynomial time. So halting problem is
an NP-hard problem.
 Also, the Boolean satisfiability problem, which is in NPC, can be
reduced to an instance of the halting problem in polynomial time by
transforming it to the description of a Turing machine that tries all
truth value assignments. The Turing machine halts when it finds
such an assignment, otherwise, it goes into an infinite loop.

NP-Hard vs. NP-Complete

# NP-Complete NP-Hard

NP-complete problems are The NP-hard problem might not be a

1.
decision problems. decision problem.

NP-complete problems are harder NP-hard problems are the hardest

2.
problems. problem.

The NP-complete problems are in

3. NP-hard problems may not be in NP.
NP.
 106

# NP-Complete NP-Hard

Problem X is NP-complete if NP Problem X is NP-hard if NP-complete

4. problem Y is reducible to X in problem Y is reducible to X in
polynomial time. polynomial time.

5. Ex. 3 SAT problem. Ex. Halting problem.

Cook’s theorem
In computational complexity theory, the Cook–Levin theorem, also known
as Cook’s theorem, states that the Boolean satisfiability problem is NP-
complete. That is, it is in NP, and any problem in NP can be reduced in
polynomial time by a deterministic Turing machine to the Boolean
satisfiability problem.
hence, anSAT is a significant problem and can be stated as follows:
Given a boolean expression F having n variables x1,x2,….,xn, and Boolean
operators, is it possible to have an assignment for variables true or false
such that binary expression F is true?

This problem is also known as the formula – SAT. An SAT(formula-SAT

or simply SAT) takes a Boolean expression F and checks whether the
given expression(or formula) is satisfiable. A Boolean expression is said to
be satisfactory for some valid assignments of variables if the evaluation
comes to be true. Prior to discussing the details of SAT, some important
terminologies of a Boolean expression are:

 Boolean variable: A variable, say x, that can have only two values,
true or false, is called a boolean variable
 Literal: A literal can be a logical variable, say x, or the negation of
it, that is x or x̄; x is called a positive literal, and x̄ is called the
negative literal
 Clause: A sequence of variables(x1,x2,….,xn) that can be separated
by a logical OR operator is called a clause. For example, (x1 V x2 V
x3) is a clause of three literals.
 Expressions: One can combine all the preceding clauses using a
Boolean operator to form an expression.
 CNF form: An expression is in CNF form(conjunctive normal form) if
the set of clauses are separated by an AND (^), operator, while the
literals are connected by an OR (v) operator. The following is an

o f = (x1 V x̄2 V x3)∧ (x1 V x̄3 V x2)

example of an expression in the CNF form:

 3 – CNF: An expression is said to be in 3-CNF if it is in the

conjunctive normal form, and every clause has exact three literals.

Thus, an SAT is one of the toughest problems, as there is no known

algorithm other than the brute force approach. A brute force algorithm
would be an exponential-time algorithm, as 2npossible assignments need
 107

to be tried to check whether the given Boolean expression is true or not.

Stephen Cook and Leonid Levin proved that the SAT is NP-complete.
 108

Divide and Conquer Dynamic Programming

Divide and conquer is the top down
Dynamic programming is bottom up approach.
approach.
Divide and conquer prefers recursion. Dynamic programming prefers iteration.
In divide and conquer, sub problems Sub problems of dynamic programming are
are independent. dependent and overlapping.
Solutions of sub problems are not
Solutions of sub problems are stored in the table.
stored.
Lots of repetition of work. No repetition at work at all.
It splits input at a specific point. It splits input at each and every possible point.
Less efficient due to rework. More efficient due to the saving of solution.
Solution using divide and conquer is Sometimes, a solution using dynamic programming is
simple. complex and tricky.
Only one decision sequence is
Many decision sequences may be generated.
generated.
Divide and Conquer Vs Dynamic Programming

Dynamic Programming Vs Greedy Algorithm

Dynamic Programming Greedy Approach
It guarantees an optimal solution. It does not guarantee an optimal solution.
Sub problems in dynamic programming are Sub problems in greedy algorithm do not
overlapping. overlap.
It does more work due to splitting of problem at It does little work due to splitting problem at
every possible point. specific points only.
It considers the future choices while selects the Only considers the current choice without
current choice. looking about future.
Construct the solution from the set of feasible
There is no specialized set of feasible choices.
solutions.
Select choice which is globally optimum. Select choice which is locally optimum.
Employ memorization. There is no concept of memorization.

Greedy Vs. Divide and Conquer

 109

Divide and conquer Greedy Algorithm

A greedy algorithm is optimization
Divide and conquer is used to find the solution, it does technique. It tries to find an optimal
not aim for the optimal solution. solution from the set of feasible
solutions.
DC approach divides the problem into small sub
In greedy approach, the optimal
problems, each sub problem is solved independently and
solution is obtained from a set of
solutions of the smaller problems are combined to find
feasible solutions.
the solution of the large problem.
Greedy algorithm does not consider
Sub problems are independent, so DC might solve same
the previously solved instance again,
sub problem multiple time.
thus it avoids the re-computation.
DC approach is recursive in nature, so it is slower and Greedy algorithms are iterative in
inefficient. nature and hence faster.
Greedy algorithms also run in
Divide and conquer algorithms mostly runs in
polynomial time but takes less time
polynomial time
than Divide and conquer