Analysis and Design of Algorithm

4th Sem
BCS401
AY : 2024-25

Department
DepartmentoofCSE ATME College of Engineering
CSE
Course Outcomes(COs):
Course Outcomes:

CO 1. Apply asymptotic notational method to analyze the performance of the

algorithms in terms of time complexity.
CO 2. Demonstrate divide & conquer approaches and decrease & conquer
approaches to solve computational problems.
CO 3. Make use of transform & conquer and dynamic programming design
approaches to solve the given real world or complex computational problems.
CO 4. Apply greedy and input enhancement methods to solve graph & string
based computational problems.
CO 5. Analyse various classes (P,NP and NP Complete) of problems
CO 6. Illustrate backtracking, branch & bound and approximation methods.

2
 Agenda
 What is an Algorithm?
 Algorithm Specification
 Analysis Framework
 Performance Analysis: Space complexity, Time complexity
 Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω),
Theta notation (Θ), and Little-oh notation (o)
 Mathematical analysis of Non-Recursive
 Recursive Algorithms with Examples .
 Important Problem Types: Sorting, Searching, String processing, Graph Problems,
Combinatorial Problems.
 Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries.
3
 MODULE – 1

INTRODUCTION
 What is an algorithm?
Algorithmic: The sprit of computing – David Harel.

Another reason for studying algorithms is their

usefulness in developing analytical skills.

Algorithms can be seen as special kinds of solutions to

problems – not answers but rather precisely defined
procedures for getting answers.

Department of 5
 What is an algorithm?
Recipe, process, method, technique, procedure,
routine,… with the following requirements:
1. Finiteness
 terminates after a finite number of steps
2. Definiteness
 rigorously and unambiguously specified
3. Clearly specified input
 valid inputs are clearly specified
4. Clearly specified/expected output
 can be proved to produce the correct output given a valid input
5. Effectiveness
 steps are sufficiently simple and basic
Department
Departmentof
of ATME College of Engineering 6
CCSSEE
 Algorithm

• Can be represented in various forms

• Unambiguity/clearness
• Effectiveness
• Finiteness/termination
• Correctness

Department
Departmentof
of ATME College of Engineering 7
CCSSEE
 What is an algorithm?
An algorithm is a sequence of unambiguous instructions
for solving a problem, i.e., for obtaining a required
output for any legitimate input in a finite amount of
time.
Problem

Algorithm

Input “Computer” Output

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 8

CCSSEE
 Euclid’s Algorithm
Problem: Find gcd(m,n), the greatest common divisor of two
nonnegative, not both zero integers m and n

Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ?

Euclid’s algorithm is based on repeated application of equality

gcd(m,n) = gcd(n, m mod n)
m mod n is the reminder of the division m &n.
until the second number becomes 0, which makes the problem
trivial.

Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12

Department
Departmentof
of ATME College of Engineering 10
CCSSEE
 Two descriptions of Euclid’s algorithm

Step 1 If n = 0, return m and stop; otherwise go to Step 2

Step 2 Divide m by n and assign the value of the remainder to r
Step 3 Assign the value of n to m and the value of r to n. Go to
Step 1.

while n ≠ 0 do
r ← m mod n
m← n
n←r
return m

Department
Departmentof
of ATME College of Engineering 11
CCSSEE
 Other methods for computing
Consecutive integer checking algorithm
Step 1 Assign the valuegcd(m,n)
of min{m,n} to t
Step 2 Divide m by t. If the remainder is 0, go to Step 3;
otherwise, go to Step 4
Step 3 Divide n by t. If the remainder is 0, return t and stop;
otherwise, go to Step 4
Step 4 Decrease t by 1 and go to Step 2

Is this slower than Euclid’s algorithm?

How much slower?

ATME College of Engineering 12

 Other methods for gcd(m,n)[cont.]
Middle-school procedure
Step 1 Find the prime factorization of m
Step 2 Find the prime factorization of n
Step 3 Find all the common prime factors
Step 4 Compute the product of all the common prime factors
and return it as gcd(m,n)

Is this an algorithm?

How efficient is it?

Department
Departmentof
of ATME College of Engineering 13
CCSSEE
 Sieve of Eratosthenes
Input: Integer n ≥ 2
Output: List of primes less than or equal to n
for p ← 2 to n do A[p] ← p
for p ← 2 to sqrt(n) do
if A[p]  0 //p hasn’t been eliminated on previous passes
j ← p* p
while j ≤ n do
A[j] ← 0 //mark element as eliminated
j←j+p

Example: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Output: 2 3 5 7 11 13 17 19

Department
Departmentof
of ATME College of Engineering 14
CCSSEE
Fundamental steps in solving problems

Department of Department
CCSSEE of ATME College of Engineering 15
 Fundamental steps in solving problems

Statement of the problem

Development of mathematical model
Design of the algorithm
Correctness of the algorithm
 Analysis of algorithm for its time and space
complexity
Implementation
Program testing and debugging
Documentation
Department
Departmentof
of ATME College of Engineering 16
CCSSEE
 Important problem types
• Sorting

• Searching

• String processing

• Graph problems

• Combinatorial problems

• Geometric problems

• Numerical problems

Department
Departmentof
of ATME College of Engineering 17
CCSSEE
 Graph Problems

• Informal definition
– A graph is a collection of points called vertices, some of
which are connected by line segments called edges.
• Modeling real-life problems
– Modeling WWW
– Communication networks
– Project scheduling …
• Examples of graph algorithms
– Graph traversal algorithms
– Shortest-path algorithms
– Topological sorting

Department
Departmentof
of ATME College of Engineering 18
CCSSEE
 Linear Data Structures

• Arrays  Arrays
– A sequence of n items of the same  fixed length (need preliminary
data type that are stored contiguously reservation of memory)
in computer memory and made  contiguous memory locations
accessible by specifying a value of the
 direct access
array’s index.
• Linked List  Insert/delete
– A sequence of zero or more nodes  Linked Lists
each containing two kinds of  dynamic length
information: some data and one or  arbitrary memory locations
more links called pointers to other
nodes of the linked list.  access by following links
– Singly linked list (next pointer)  Insert/delete
– Doubly linked list (next + previous
pointers)
a1 a2 … an .
19
 Stacks and Queues

• Stacks
– A stack of plates
• insertion/deletion can be done only at the top.
• LIFO
– Two operations (push and pop)
• Queues
– A queue of customers waiting for services
• Insertion/enqueue from the rear and deletion/dequeue from the
front.
• FIFO
– Two operations (enqueue and dequeue)

Department
Departmentof
of ATME College of Engineering 20
CCSSEE
 Priority Queue and Heap

 Priority queues (implemented using heaps)

A data structure for maintaining a set of elements, each associated
with a key/priority, with the following operations
 Finding the element with the highest priority
 Deleting the element with the highest priority
 Inserting a new element
 Scheduling jobs on a shared computer
9
6 8
5 2 3

9 6 8 5 2 3

21
 Graphs

• Formal definition
– A graph G = <V, E> is defined by a pair of two sets: a finite set V of
items called vertices and a set E of vertex pairs called edges.
• Undirected and directed graphs (digraphs).
• What’s the maximum number of edges in an
undirected graph with |V| vertices?
• Complete, dense, and sparse graphs
– A graph with every pair of its vertices connected by an edge is called
complete, K|V|

1 2

3 4
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 22
CCSSEE
 Graph Representation

• Adjacency matrix
– n x n boolean matrix if |V| is n.
– The element on the ith row and jth column is 1 if there’s an edge from ith
vertex to the jth vertex; otherwise 0.
– The adjacency matrix of an undirected graph is symmetric.
• Adjacency linked lists
– A collection of linked lists, one for each vertex, that contain all the vertices
adjacent to the list’s vertex.
• Which data structure would you use if the graph is a 100-node star shape?

0111 2 3 4
0001
4
0001
4
0000

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 23

CCSSEE
 Weighted Graphs

• Weighted graphs
– Graphs or digraphs with numbers assigned to the edges.

5
1 2
6 7
9
3 4
8

Department
Departmentof
of ATME College of Engineering 24
CCSSEE
 Graph Properties -- Paths and Connectivity

• Paths
– A path from vertex u to v of a graph G is defined as a sequence of
adjacent (connected by an edge) vertices that starts with u and ends
with v.
– Simple paths: All edges of a path are distinct.
– Path lengths: the number of edges, or the number of vertices – 1.
• Connected graphs
– A graph is said to be connected if for every pair of its vertices u and v
there is a path from u to v.
• Connected component
– The maximum connected subgraph of a given graph.

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 25

CCSSEE
 Graph Properties -- Acyclicity

• Cycle
– A simple path of a positive length that starts and ends
a the same vertex.
• Acyclic graph
– A graph without cycles
– DAG (Directed Acyclic Graph)

1 2

3 4

Department
Departmentof
of ATME College of Engineering 26
CCSSEE
 Trees

• Trees
– A tree (or free tree) is a connected acyclic graph.
– Forest: a graph that has no cycles but is not necessarily connected.
• Properties of trees

– For every two vertices in a tree there always exists exactly one simple
path from one of these vertices to the other. Why?
• Rooted trees: The above property makes it possible to select an arbitrary vertex in a
free tree and consider it as the root of the so called rooted tree.
• Levels in a rooted tree.
rooted
3
 |E| = |V| - 1 1 3 5
4 1 5
2 4
2
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 27
CCSSEE
 Rooted Trees (I)
• Ancestors
– For any vertex v in a tree T, all the vertices on the simple path
from the root to that vertex are called ancestors.
• Descendants
– All the vertices for which a vertex v is an ancestor are said to be
descendants of v.
• Parent, child and siblings
– If (u, v) is the last edge of the simple path from the root to
vertex v, u is said to be the parent of v and v is called a child of
u.
– Vertices that have the same parent are called siblings.
• Leaves
– A vertex without children is called a leaf.
• Subtree
– A vertex v with all its descendants is called the subtree of T
rooted at v.

Department
Departmentof
of ATME College of Engineering 28
CCSSEE
 Rooted Trees (II)

• Depth of a vertex
– The length of the simple path from the root to the vertex.
• Height of a tree
– The length of the longest simple path from the root to a leaf.

h=2
3

4 1 5

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 29

CCSSEE
 Ordered Trees
• Ordered trees
– An ordered tree is a rooted tree in which all the children of each vertex
are ordered.
• Binary trees
– A binary tree is an ordered tree in which every vertex has no more than
two children and each children is designated s either a left child or a
right child of its parent.
• Binary search trees
– Each vertex is assigned a number.
– A number assigned to each parental vertex is larger than all the
numbers in its left subtree and smaller than all the numbers in its right
subtree.
• log2n  h  n – 1, where h is the height of a binary tree and n the size.

9 6
6 8 3 9
5 2 3 2 5 8
Department
Departmentof
of ATME College of Engineering 30
CCSSEE
Computing time functions

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 31

CCSSEE
Values of some important functions as n  

Department
Departmentof
of ATME College of Engineering 32
CCSSEE
 Order of growth
• Most important: Order of growth within a
constant multiple as n→∞

• Example:
– How much faster will the algorithm run on computer that is
twice as fast?

– How much longer does it take to solve problem of double

input size?

Department
Departmentof
of ATME College of Engineering 33
CCSSEE
 Best-case, average-case, worst-case

For some algorithms efficiency depends on form of input:

• Worst case: Cworst(n) – maximum over inputs of size n

• Best case: Cbest(n) – minimum over inputs of size n
• Average case: Cavg(n) – “average” over inputs of size n

– Number of times the basic operation will be executed on typical

input.
– NOT the average of worst and best case.

Department
Departmentof
of ATME College of Engineering 34
CCSSEE
 Asymptotic order of growth
A way of comparing functions that ignores constant
factors and small input sizes

• O(g(n)): class of functions f(n) that grow no faster than g(n)

• Θ(g(n)): class of functions f(n) that grow at same rate as g(n)

• Ω(g(n)): class of functions f(n) that grow at least as fast as g(n)

Department
Departmentof
of ATME College of Engineering 35
CCSSEE
 Establishing order of growth using the definition

Definition: f(n) is in O(g(n)) if order of growth of f(n) ≤ order of

growth of g(n) (within constant multiple),
i.e., there exist positive constant c and non-negative integer n0
such that
f(n) ≤ c g(n) for every n ≥ n0

Example:
• 5n+2 is O(n); c= 7 and n0 = 1

Note : The Upper Bound indicates that the function will be the worst case that it
does not consume more than this computing time.

Department
Departmentof
of ATME College of Engineering 36
CCSSEE
 Big-oh

Department
Departmentof
of ATME College of Engineering 37
CCSSEE
Establishing order of growth using the definition

Department
Departmentof
of ATME College of Engineering 38
CCSSEE
 Big-omega

Department
Departmentof
of ATME College of Engineering 39
CCSSEE
 Establishing order of growth using the definition

Definition: f(n) is in Ɵ(g(n)) iff there exists three positive

constants c1,c2 and n0 with the constraint that c1 g(n) ≤ f(n)
≤ c2 g(n) for every n ≥ n0 .

Example:
• 3n+2 is Ɵ (n)
• c1 g(n) ≤ f(n) ≤ c2 g(n) for every n ≥ n0
• 3 n ≤ 3n+2 ≤ 4 n for every n0 = 2, c1 = 3, c2 = 4

Department
Departmentof
of ATME College of Engineering 40
CCSSEE
 Big-theta

Department
Departmentof
of ATME College of Engineering 41
CCSSEE
 Properties of asymptotic order of growth

• f(n)  O(f(n))

• f(n)  O(g(n)) iff g(n) (f(n))

• If f (n)  O(g (n)) and g(n)  O(h(n)) , then f(n)  O(h(n))

Note similarity with a ≤ b

• If f1(n)  O(g1(n)) and f2(n)  O(g2(n)) , then

f1(n) + f2(n)  O(max{g1(n), g2(n)})

Department
Departmentof
of ATME College of Engineering 42
CCSSEE
 Time efficiency of nonrecursive
algorithms
General Plan for Analysis
• Decide on parameter n indicating input size

• Identify algorithm’s basic operation

• Determine worst, average, and best cases for input of size n

• Set up a sum for the number of times the basic operation is

executed

• Simplify the sum using standard formulas and rules

Department
Departmentof
of ATME College of Engineering 43
CCSSEE
 Establishing order of growth using limits

0 order of growth of T(n) < order of growth of g(n

lim T(n)/g(n) c > 0 order of growth of T(n) = order of growth of g(n

n→ ∞
= ∞ order of growth of T(n) > order of growth of g(n

Examples:
• 10n vs. n2

• n(n+1)/2 vs. n2

Department
Departmentof
of ATME College of Engineering 44
CCSSEE
 Example: Sequential search

Worst case - O(n) Best case - Ω(n)

Average case – Θ(n/2)

Department of 45
CSE
Example 1: Maximum element

Department of 46
CSE
 Analysis
1. Input parameter : n 3.
2. Basic operation:
Comparison
A[i] > max
4.

Department of 47
CSE
Example 2: Element uniqueness
problem

Department
Departmentof
of ATME College of Engineering 48
CCSSEE
 Analysis
1. Input parameter is input size n
2. Basic operation: Comparison A[i] == A[j]
3.

4.

Є O(n2)

Department of 49
CSE
Example 3: Matrix
multiplication

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 50
CCSSEE
Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 51
CCSSEE
 Analysis
1. Input parameter is input size n2 X n2
2. Basic operation: Comparison C[i,j] == C[i,j] + A[i,k] * B[k,j]
3.

Є O(n3)
Department of 52
CSE
 Selection Sort
Algorithm SelectionSort (A[0..n-1])
//The algorithm sorts a given array by selection sort
//Input: An array A[0..n-1] of orderable elements
//Output: Array A[0..n-1] sorted in ascending order
for i  0 to n – 2 do
min  i
for j  i + 1 to n – 1 do
if A[j] < A[min]
min  j
swap A[i] and A[min]

Time efficiency: Θ(n2) comparisons (in the worst case)

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 53
CCSSEE
 Solve recurrence relations
•X(n) = x(n-1) + 5 for n>1, x(1) = 0
X(n) = x(n-1) + 5
X(n) = x(n-2) + 5+5
= x(n-2) + 2 *5
X(n) = x(n-3) + 3*5

X(n) = x(n-n-1) + n-1 * 5

= x(1) + (n-1) * 5
= O(n-1) = O(n)
Department
Departmentof
of ATME College of Engineering 54
CCSSEE
 Solve x(n) = 3x(n-1) for n>1, x(1) =4
x(n) = 3x(n-1)
= 3[3x(n-2)]
= 32 x(n-2)
= 33 [x(n-3)]
= 34 [x(n-4)]
-
-
= 3n-1 [x(n-n-1)]
=3n-1 [x(1)] = 3n-1 [4] = 4/3 * 3n
Department
Departmentof
of ATME College of Engineering 55
CCSSEE
 Solve

1. X(n) = x(n/2) + n for n>1

2. T(n) = T(n/2) + T(n/2) + 3 for n> 2
T(2) = 2, T(1) = 1

Department
Departmentof
of ATME College of Engineering 56
CCSSEE
 Plan for Analysis of Recursive
• Decide on a parameter indicating an input’s size.
Algorithms
• Identify the algorithm’s basic operation.

• Check whether the number of times the basic op. is executed

may vary on different inputs of the same size. (If it may, the
worst, average, and best cases must be investigated
separately.)

• Set up a recurrence relation with an appropriate initial

condition expressing the number of times the basic op. is
executed.

• Solve the recurrence (or, at the very least, establish its

solution’s order of growth) by backward substitutions or
another method.
Department
Departmentof
of ATME College of Engineering 57
CCSSEE
Example 1: Recursive evaluation of
Definition: n ! = 1  2 n!… (n-1)  n for n ≥ 1 and
0! = 1
Recursive definition of n!: F(n) = F(n-1)  n for n ≥
1 and
F(0) = 1

Size:
Basic operation:
Recurrence relation:
Department of 58
CSE
 Solving the recurrence for M(n)

M(n) = M(n-1) + 1, M(0) = 0

Refer Notes

Department
Departmentof
of ATME College of Engineering 59
CCSSEE
 Tower of Hanoi Problem
• In this problem, we have n disks of different sizes and
three pegs.
• Initially, all the disks are on the first peg in order of
size, the largest on the bottom and the smallest on
top.
• The goal is to move all the disks to the third peg,
using the second one as an auxiliary if necessary.
• We can move only one disk at a time, and it is
forbidden to place a larger disk on top of a smaller
one.

Department
Departmentof
of ATME College of Engineering 60
CCSSEE
 Example 2: The Tower of Hanoi
Puzzle

1 3

Recurrence for number of moves:

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 61

CCSSEE
Department
Departmentof
of ATME College of Engineering 62
CCSSEE
Solving recurrence for number of
moves

Department
Departmentof
of ATME College of Engineering 63
CCSSEE
Tree of calls for the Tower of Hanoi
Puzzle
n

n-1 n-1

n-2 n-2 n-2 n-2

.. .. ..
2 2 2 2

1 1 1 1 1 1 1 1

Department
Departmentof
of ATME College of Engineering 64
CCSSEE
 Fibonacci numbers
The Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, …

The Fibonacci algorithm (recursive )

Fib(n)
{
If n<=1
return n
Else
Return F(n-1) + F(n-2)

Department
Departmentof
of ATME College of Engineering 65
CCSSEE
•The recurrence equation for this problem is:
T(n) = T(n-1) + T(n-2) for n>1 and the initial
conditions are T(0) =0, T(1) = 1
Solution to recurrence relation:
T(n) = T(n-1) + T(n-2)
T(n) –T(n-1) –T(n-2) = 0
This is of the form ax(n) +bx(n-1) +cx(n-2) =0
Which is a homogeneous second order linear
relation with constant co-efficients.
De pa rtmen t oof
Department f ISE BATME
MS I n sCollege
tit u t e ofofTe ch nol og y and Mgmt
Engineering 66
CSE
Department
Departmentof
of ATME College of Engineering 67
CCSSEE
Department
Departmentof
of ATME College of Engineering 68
CCSSEE
 Little oh Notation (o)
• The asymptotic upper bound provided by O-
notation may or may not be asymptotically
tight. The bound 2n2 = O(n2) is asymptotically
tight but the bound 2n = o(n2) is not.
• We use o-notation to denote an upper bound
that is not asymptotically tight
• f(n) = o(g(n)); f(n) is equal to the little oh of
g(n), iff f(n) < c, g(n) for any +ve constant c>0,
no>0 and n>no

Department
Departmentof
of ATME College of Engineering 69
CCSSEE
 Establishing order of growth using limits

0 order of growth of T(n) < order of growth of g(n

lim T(n)/g(n) c > 0 order of growth of T(n) = order of growth of g(n

n→ ∞
= ∞ order of growth of T(n) > order of growth of g(n

Examples:
• 10n vs. n2

• 5n + 2 vs. n

Department
Departmentof
of ATME College of Engineering 70
CCSSEE
 Property of the Asymptotic Notations

1.Theorem :If t1(n) Є O(g1(n)) and t2(n) Є

O(g2(n)), then
t1(n) + t2(n) Є O(max{g1(n), (g2(n)})

2.Theorem: If f(n) = am nm + - - - - + a1 n + a0 and

am >0, then f(n) = O(nm)

Department
Departmentof
of ATME College of Engineering 71
CCSSEE
 Brute Force
A straightforward approach, usually based directly on the
problem’s statement and definitions of the concepts involved

Examples:
1. Computing an (a > 0, n a nonnegative integer)

2. Computing n!

3. Multiplying two matrices

4. Searching for a key of a given value in a list

Department
Departmentof
of ATME College of Engineering 72
CCSSEE
 Brute-Force Sorting Algorithm
Selection Sort Scan the array to find its smallest element and
swap it with the first element. Then, starting with the second
element, scan the elements to the right of it to find the
smallest among them and swap it with the second elements.
Generally, on pass i (0  i  n-2), find the smallest element in
A[i..n-1] and swap it with A[i]:

A[0]  . . .  A[i-1] | A[i], . . . , A[min], . . ., A[n-1]

in their final positions

Example: 7 3 2 5

Department
Departmentof
of ATME College of Engineering 73
CCSSEE
 Analysis of Selection Sort

Time efficiency: Θ(n^2)

In place: Yes

Stability: yes
Department of 74
CSE
 Brute-Force String Matching
• pattern: a string of m characters to search for
• text: a (longer) string of n characters to search in
• problem: find a substring in the text that matches the pattern
Brute-force algorithm
Step 1 Align pattern at beginning of text
Step 2 Moving from left to right, compare each character of
pattern to the corresponding character in text until
• all characters are found to match (successful search); or
• a mismatch is detected
Step 3 While pattern is not found and the text is not yet
exhausted, realign pattern one position to the right and
repeat Step 2

Department
Departmentof
of ATME College of Engineering 75
CCSSEE
 Examples of Brute-Force String Matching

1. Pattern: 001011
Text: 10010101101001100101111010

2. Pattern: happy
Text: It is never too late to have a
happy childhood.

Department
Departmentof
of ATME College of Engineering 76
CCSSEE
 Pseudocode and Efficiency

Time efficiency: Θ(mn) comparisons (in the worst case)

Department of 77
CSE
 Brute-Force Strengths and
Weaknesses
• Strengths
– wide applicability
– simplicity
– yields reasonable algorithms for some important problems
(e.g., matrix multiplication, sorting, searching, string
matching)

• Weaknesses
– rarely yields efficient algorithms
– some brute-force algorithms are unacceptably slow
– not as constructive as some other design techniques

Department
Departmentof
of ATME College of Engineering 78
CCSSEE
 MODULE – 2

DIVIDE AND CONQUER

Department of 79
CSE
 Divide-and-Conquer

The most-well known algorithm design strategy

1. Divide instance of problem into two or more
smaller instances
2. Solve smaller instances recursively
3. Obtain solution to original (larger) instance by
combining these solutions

Department
Departmentof
of ATME College of Engineering 80
CCSSEE
 Divide and conquer involves three steps,
at each level of recursion.

• Divide: Divide the problem into a number of

sub problems
• Conquer: Conquer the sub problems by
solving them recursively. If the sub – problem
sizes are small enough, then solve the sub-
problem in a straight forward manner.
• Combine: combine the solutions to the sub-
problems to get the solution to the original
problem.
Department
Departmentof
of ATME College of Engineering 81
CCSSEE
 Divide-and-Conquer Technique (cont.)

a problem of size n
(instance)

subproblem 1 subproblem 2
of size n/2 of size n/2

a solution to a solution to
subproblem 1 subproblem 2

T(n) = a T(n/b) + f (n) a solution to In general leads to a

the original problem
where f(n)  (nd), d  0
recursive algorithm!
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 82
CCSSEE
 Divide-and-Conquer Examples
• Sorting: merge sort and quicksort
• Finding min and max element in an array
• Binary search
• Multiplication of large integers
• Matrix multiplication: Strassen’s algorithm

Department
Departmentof
of ATME College of Engineering 83
CCSSEE
 General Divide-and-Conquer Recurrence

T(n) = aT(n/b) + f (n) where f(n)  (nd), d  0

Master Theorem: If a < bd, T(n)  (nd)

If a = bd, T(n)  (nd log n)

If a > bd, T(n)  (nlog b a )

Note: The same results hold with O instead of .

(n^2)
Examples: T(n) = 4T(n/2) + n  T(n)  ? (n^2log n)
T(n) = 4T(n/2) + n2  T(n)  ?
(n^3)
T(n) = 4T(n/2) + n3  T(n)  ?

Department
Departmentof
of ATME College of Engineering 84
CCSSEE
 Merge Sort Algorithm
Mergesort(low, high)
//Given an array A of n elements. This algorithm sorts the elements in
//ascending order. The variables low and high are used to identify the
//positions of first and last element in each partition.
1. If (low< high)
2. mid = (low+high)/2;
3. Mergesort (low,mid);
4. Mergesort(mid+1,high);
5. Merge(low,mid,high);
6. End if
7. Exit

Department
Departmentof
of ATME College of Engineering 85
CCSSEE
 Merge Algorithm
Merge(low, mid, high)
// The variables low, mid, and high are used to identify the
portions of elements in each partition.
1. Initialize i=low, j= mid+1, h=low;
2. while ((h <= mid) && (j <= high))
3. if (a[h] < a[j])
b[i++] = a[h++];
else
b[i++] = a[j++];

Department
Departmentof
of ATME College of Engineering 86
CCSSEE
 Cont…
4. if (h > mid)
for(k = j; k <= high; k++)
b[i++] = a[k];
else
for (k = h; k <= mid; k++)
b[i++] = a[k];
5. for (k = low; k <= high; k++)
a[k] = b[k];

Department
Departmentof
of ATME College of Engineering 87
CCSSEE
 Mergesort

• Split array A[0..n-1] into about equal halves and make

copies of each half in arrays B and C
• Sort arrays B and C recursively
• Merge sorted arrays B and C into array A as follows:
– Repeat the following until no elements remain in one of the arrays:
• compare the first elements in the remaining unprocessed portions
of the arrays
• copy the smaller of the two into A, while incrementing the index
indicating the unprocessed portion of that array
– Once all elements in one of the arrays are processed, copy the
remaining unprocessed elements from the other array into A.

Department
Departmentof
of ATME College of Engineering 88
CCSSEE
 Mergesort Example
8 3 2 9 7 1 5 4

8 3 2 9 7 1 5 4

83 29 71 54

8 3 2 9 7 1 5 4
The non-recursive
version of Mergesort
38 29 17 45 starts from merging
single elements into
2 3 8 9 1 4 5 7 sorted pairs.

1 2 3 4 5 7 8 9

Department of 89
CSE
Analysis of Mergesort

Department
Departmentof
of ATME College of Engineering 90
CCSSEE
• All cases have same efficiency: Θ(n log n)
• Number of comparisons in the worst case is
close to theoretical minimum for comparison-
based sorting:
log2 n! ≈ n log2 n - 1.44n
• Space requirement: Θ(n) (not in-place)
• Can be implemented without recursion

Department
Departmentof
of ATME College of Engineering 91
CCSSEE
 Quicksort
• Select a pivot (partitioning element) – as the first element
•
p
i j
A[i]p A[i]p
p

A[i]p A[i]p
• Exchange the pivot with the last element in the first (i.e., )
subarray — the pivot is now in its final position
• Sort the two subarrays recursively
• Note : Invented by
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 92
CCSSEE
 Quick Sort Algorithm
Quick sort(low, high)
// A is an array of elements.
// The variables low and high are used to identify the positions of first and
// last elements in each partition.
If(low< high) then
J= partition(low, high)
Quick sort( low, j-1)
Quick sort(j+1, high)
End if
Exit

Department
Departmentof
of ATME College of Engineering 93
CCSSEE
 Partition Algorithm
Partition(low, high)
//This procedure partitions the element into two lists and places the pivot
//element into a appropriate place. Low = first element of the array, high =
//last element of the array, a[low] = pivot.
Step 1. Set pivot = a[low];
i = low +1;
j = high;
Step 2. Repeat step 3 while (a[i] < pivot && i < high)
Step 3. i++;
Step 4. Repeat step 5 while (a[j] > pivot)
Step 5. j--;
Step 6. If(i<j)
swap a[i] and a[j]
go to step 2
else
swap a[j] and pivot
Department of CSE ATME College of Engineering 94
Step 7. Return (j)
 Quicksort Example
5 3 1 9 8 2 4 7
2 3 1 4 5 8 9 7
1 2 3 4 5 7 8 9
1 2 3 4 5 7 8 9
1 2 3 4 5 7 8 9
1 2 3 4 5 7 8 9

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Analysis of Quicksort
• Best case: split in the middle — Θ(n log n)
• Worst case: sorted array! — Θ(n2) T(n) = T(n-1) + Θ(n)

• Average case: random arrays — Θ(n log n)

• Improvements:
– better pivot selection: median of three partitioning
– switch to insertion sort on small subfiles
– elimination of recursion
These combine to 20-25% improvement

• Considered the method of choice for internal sorting of large

files (n ≥ 10000)

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Binary Search
Algorithm Binary_Search( A[0…n-1], Key)
Input: Given an array of n elements in sorted order and key is an element to be
searched.
Output: Returns the position of key element, if successful and returns -1
otherwise.
1. Set first = 0, last = n-1
2. While (first < = last)
mid = (first +last) / 2
if (key == A[mid])
return (mid+1); // successful
else if ( key < A[mid] )
last = mid – 1
else
first = mid+1
end while
3. return -1 // unsuccessful

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Analysis
Best Case: Best case occurs, when we are
searching the middle element itself. In that case,
total number of comparisons required is 1. there
fore best case time complexity of binary search
is Ω(1).
Worst Case: Let T(n) be the cost involved to
search ‘n’ elements. Let T(n/2) be the cost
involved to search either left part or the right
part of an array.
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Analysis
T(n) = a if n = 1
T(n/2) + b otherwise

T(n/2)  Time required to search either the left

part or the right part of the array.
b  Time required to compare the middle element.
Where a and b are some positive integer constants.
T(n) = O(log 2n )

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Analysis
Average Case:
The average case occurs when an element is found some where
in the recursive calls, but not till the recursive call ends.
The average number of key comparisons made by binary search
is only slightly smaller than that in this worst case.
T(n) = log 2n
The average number of comparison in a successful search is
T(n) = log 2n – 1
The average number of comparison in a unsuccessful search is
T(n) = log 2n + 1

Department
Departmentof
of ATME College of Engineering
CCSSEE
Algorithm for straight forward maximum and
minimum
StraightMaxMin(a,n,max,min)
// set max to the maximum and min to the minimum of a[1:n].
{
max := min := a[1];
for i := 2 to n do
{
if(a[i] > max) then max := a[i];
if(a[i] < min) then min := a[i];
}
}

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Analysis
• This algorithm requires 2(n-1) element
comparisons in the best, average, and worst
cases.
• Now the Best case occurs when the elements
are in increasing order. The number of
element comparisons is n-1.
• The worst case occurs when the element are
in decreasing order. In this case number of
comparisons is 2(n-1).
Department
Departmentof
of ATME College of Engineering
CCSSEE
Finding maximum and minimum using
divide and conquer technique
Algorithm max_min(i, j, max, min)
{
// Input: a[1:n] is a global array. Parameters i and j
are integers, 1<=i <= j<= n.
// output: to set max and min to the largest and
smallest values in a[i: j], respectively.
If (i == j) then // Small(P)
{ max = min  A[i];
} Department
Departmentof
of ATME
ATMECollege 103
CollegeofofEngineering
Engineering
CCSSEE
else if ( i =j-1) then // Another case of Small(P)
{
if (A[i] < A[j]) then
{
max  A[j]
min  A[i]
}
else
{
max  A[i]
min  A[j]
}
} DDeeppaarrt tmmeennttooff
CCSSEE
AATTMMEECCooleleggeeooffEEnngginineeerirningg
else
{
// if P is not small, divide P into sub problems. //
Find where to split the set
mid := (i+j)/2;
// Solve the sub problems.
max_min(i,mid,max,min);
max_min(mid+1, j, max1,min1);
// Combine the solutions
if( max < max1) then max := max1;
if( min > min1) then min:= min1;
}
} DDeeppaarrt tmmeennttooff
CCSSEE
AATTMMEECCooleleggeeooffEEnngginineeerirningg
 Analysis
0 n=1
T(n) = 1 n=2
T(n/2) + T(n/2) + 2 n>2

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

T(n) = 2T(n/2) + 2
= 2T(2k-1) ) + 2
= 2(2T(2k-2) + 2) + 2
= 22T(2k-2) + 22 + 2
= 23T(2k-3) + 23 + 22 + 2
...
= 2k-1 T(2k-(k-1)) + 2k-2 + 2k-1 + - - - + 21
= 2k-1 + 2k-2 + - - - + 21
= 2. (2k-1 – 1)/ 2-1 = O(n)
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Multiplication of Large Integers
Consider the problem of multiplying two (large) n-digit integers
represented by arrays of their digits such as:

A = 12345678901357986429 B = 87654321284820912836

The grade-school algorithm:

a1 a2 … an
b1 b2 … bn
(d10) d11d12 … d1n
(d20) d21d22 … d2n
…………………
(dn0) dn1dn2 … dnn

Efficiency: Θ(n2) single-digit multiplications

Department
Departmentof
of ATME College of Engineering
CCSSEE
 First Divide-and-Conquer
A small example: A  B where A = 2135 and B = 4014
Algorithm
A = (21·102 + 35), B = (40 ·102 + 14)
So, A  B = (21 ·102 + 35)  (40 ·102 + 14)
= 21  40 ·104 + (21  14 + 35  40) ·102 + 35  14

In general, if A = A1A2 and B = B1B2 (where A and B are n-digit,

A1, A2, B1, B2 are n/2-digit numbers),
A  B = A1  B1·10n + (A1  B2 + A2  B1) ·10n/2 + A2  B2
Recurrence for the number of one-digit multiplications M(n):
M(n) = 4M(n/2), M(1) = 1
Solution: M(n) = n2

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Second Divide-and-Conquer
A  B = A  B ·10 + (A  B + A  B ) ·10 + A  B
n n/2
1 1
Algorithm
1 2 2 1 2 2

The idea is to decrease the number of multiplications from 4 to 3:

(A1 + A2 )  (B1 + B2 ) = A1  B1 + (A1  B2 + A2  B1) + A2  B2,

I.e., (A1  B2 + A2  B1) = (A1 + A2 )  (B1 + B2 ) - A1  B1 - A2  B2,

which requires only 3 multiplications at the expense of (4-1) extra
add/sub.

Recurrence for the number of multiplications M(n):

M(n) = 3M(n/2), M(1) = 1 What if we count
Solution: M(n) = 3log 2n = nlog 23 ≈ n1.585 both multiplications
and additions?

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Example of Large-Integer
2135  4014
Multiplication
= (21*10^2 + 35) * (40*10^2 + 14)
= (21*40)*10^4 + c1*10^2 + 35*14
where c1 = (21+35)*(40+14) - 21*40 - 35*14, and
21*40 = (2*10 + 1) * (4*10 + 0)
= (2*4)*10^2 + c2*10 + 1*0
where c2 = (2+1)*(4+0) - 2*4 - 1*0, etc.

This process requires 9 digit multiplications as opposed to 16.

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Matrix Multiplication

• Brute-force algorithm

c11 c12 a11 a12 b11 b12

= *
c21 c22 a21 a22 b21 b22

a11 * b11 + a12 * b21 a11 * b12 + a12 * b22

=
a21 * b11 + a22 * b21 a21 * b12 + a22 * b22
8 multiplications
Efficiency class in general:  (n3)
4 additions
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Strassen’s Matrix Multiplication
• Strassen’s algorithm for two 2x2 matrices (1969):
c11 c12 a11 a12 b11 b12
= *
c21 c22 a21 a22 b21 b22

C1 = E + I + J - G C2 = D + G
=
C3 = E + F C4 = D + H + J - F
D = A1(B2 – B4)
E = A4( B3 – B1)
F = (A3 + A4) B1
G = (A1 + A2) B4
7 multiplications
H = (A3 – A1) (B1 + B2)
I = (A2 – A4) (B3 +B4) 18 additions
J = (A1 +A4)(B1 +B4)
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg 112
CCSSEE
 Strassen’s Matrix Multiplication
A= 1 2 B= 1 1
3 4 2 2

A1 = 1, A2 =2, A3 = 3, A4 = 4
B1 = 1, B2 = 2, B3 = 2, B4 = 2
1. D = A1(B2 – B4) = 1(1 – 2) = -1
2. E = A4(B3-B1) = 4(2-1) = 4
3. F = (A3 + A4) B1 = (3+4)1 = 7
4. G = (A1 + A2)B4 = (1+2)2 = 6
Department
Departmentof
of ATME College of Engineering
CCSSEE
5. H = (A3 – A1) (B1 + B2) = (3-1)(1+1) = 4
6. I = (A2 – A4)(B3+B4) = (2-4)(2+2) = -8
7. J = (A1+A4)(B1+B4) = (1+4)(1+2) = 15

C1 = E +I+J-G = 4+(-8) +15-6 = 5

C2 = D + G = -1 +6 = 5 5 5
C = 11 11
C3 = E + F = 4 + 7 = 11
C4 = D + H + J – F = -1 +4 +15 -7 = 11

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Strassen’s Matrix Multiplication
Strassen observed [1969] that the product of two
matrices can be computed in general as follows:

C00 C01 A00 A01 B00 B01

= *
C10 C11 A10 A11 B10 B11

M1 + M4 - M5 + M7 M3 + M5
=
M2 + M4 M1 + M3 - M2 + M6

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Formulas for Strassen’s Algorithm
M1 = (A00 + A11)  (B00 + B11)

M2 = (A10 + A11)  B00

M3 = A00  (B01 - B11)

M4 = A11  (B10 - B00)

M5 = (A00 + A01)  B11

M6 = (A10 - A00)  (B00 + B01)

M7 = (A01 - A11)  (B10 + B11)

Department
Departmentof
of ATME College of Engineering
CCSSEE
 M4 = A11  (B10 - B00)
= 4 * (2 - 1) = 4
A00 A01 B00 B01
M5 = (A00 + A01)  B11
1 2 1 1 = (1 + 2) * 2 = 6

M6 = (A10 - A00)  (B00 + B01)

3 4 2 2 = (3 - 1) * (1 + 1) = 4

A10 A11 B10 B11 M7 = (A01 - A11)  (B10 + B11)

= (2 - 4) * (2 + 2) = -8
M1 = (A00 + A11)  (B00 + B11)
= (1 + 4) * (1+2) = 15 C00 C01

M1 + M4 - M5 + M7 M3 + M5 5 5
M2 = (A 10 + A11)  B 00
= (3 + 4) * 1 = 7 =
M2 + M4 M1 + M3 - M2 + M6 11 11
M3 = A00  (B01 - B11)
= 1 * (1 - 2) = -1
C10 C11
Department
Departmentof
of ATME College of Engineering
CCSSEE
 M4 = A11  (B10 - B00)
= 4 * (1 - 5) = -16
A00 A01 B00 B01
M5 = (A00 + A01)  B11
2 1 5 2 = (2 + 1) * 2 = 6

M6 = (A10 - A00)  (B00 + B01)

3 4 1 2 = (3 - 2) * (5 + 2) = 7

A10 A11 B10 B11 M7 = (A01 - A11)  (B10 + B11)

= (1 - 4) * (1 + 2) = -9
M1 = (A00 + A11)  (B00 + B11)
= (2 + 4) * (5+2) = 42 C00 C01

M1 + M4 - M5 + M7 M3 + M5 11 6
M2 = (A 10 + A11)  B 00
= (3 + 4) * 5 = 35 =
M2 + M4 M1 + M3 - M2 + M6 19 14
M3 = A00  (B01 - B11)
= 2 * (2 - 2) = 0
C10 C11
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Solve
1021
0101
4110
2104
A= 0130 B = 2011
5021
1 350

A1 A2 B1 B2
10 21 01 01
41 10 21 04

01 30 20 11
50 21 13 50
A3 A4 B3 B4

Department
Departmentof
of ATME College of Engineering
CCSSEE
1. D = A1 (B2 – B4)

01 11
10 -
* 04 50
41

10 -1 0
41 * -5 4

-6 0
-9 4

2. E = A4 (B3 – B1)

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Analysis of Strassen’s Algorithm
If n is not a power of 2, matrices can be padded with zeros.

Number of multiplications:
M(n) = 7M(n/2), M(1) = 1
M(n) = 7M(2 k-1)
= 7[7M(2 k-2)] = 7 2 M(2 k-2)]
= 7 k M(2 k-k)] = 7 k (1)

Solution: M(n) = 7log 2n = nlog 27 ≈ n2.807 vs. n3 of brute-force alg.

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Advantages and Disadvantages
• Difficult problems is broken down into sub
problems and each sub problem is solved
independently.
• It gives efficient algorithms like quick sort,
merge sort, streassen’s matrix multiplication.
• Sub problems can be executed on parallel

processor.
Disadvantage
• It makes use of recursive methods and the
recursion is slow and complex.
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease-and-Conquer
The decrease and conquer technique is almost similar to the
divide and conquer technique, but instead of dividing the
problem into size n/2, it is decremented by a constant or
constant factor.
There are three variations of decrease and conquer
• Decrease by a constant
• Decrease by a constant factor
• Variable size decrease
The problems can be solved either top down (recursively) or
bottom up ( without recursion)

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease by a constant
• In this type of variation, the size of an instance
is reduced by the same constant ‘1’ on each
iteration. So, if a problem is of size ‘n’ , then a
sub problem of size ‘n-1’ is solved first but
before a sub sub problem of size ‘n-2’ is solved
and so on.

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease by a constant
1 2 n
…….

Problem of Size n

1 ……. n-1

Sub Problem of Size (n – 1)

….
(n -2)

Solution to sub problem

Solution to the Original

Problem
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease by a constant
Example: Consider a problem for computing a n
where n is a positive integer exponent
Let f(n) = a n
a n = a n-1 . a
= a n-2 . a . a F(n) = f(n-1 ) . a if n> 1
a if n = 1
=a .a.a.a
n-3

= a. a. a. a. . . n times
The above definition is a recursive definition i.e, a top down approach

Eg: Insertion sort, Depth First Search, Breath First Search,

Topological Sort
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg
CCSSEE
 Decrease by a constant factor
• In this type of variation, the size of instance is
reduced by a constant factor on each iteration
(most of the case it is 2).
• So, if a problem of size ‘n’ is to be solved then
first the sub problem of size n/2 is to be solved
which in-turn requires the solution for the sub
sub problem n/4 and so on.

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease by a constant factor
1 2 n
…….

Problem of Size n

1 ……. n/2

Sub Problem of Size (n / 2)

(n / 4)
---

Solution to sub problem

Solution to the Original

Problem
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease by a constant factor
Example: Consider a problem for computing an
As the problem is to be halved each time (Since
the constant factor is 2, to solve a n, first solve an/2
, but before solve an/4 and so on.

an = (an/2 ) 2 if n is even and > 1

(an-1/2 ) 2 if n is odd and > 1
a if n = 1
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Decrease by a constant factor

The efficiency of this variation i.e decrease by a

constant factor is O(log n) because, the size is
reduced by at least one half at the expense of
no more than two multiplications on each
iteration

Eg: Binary search and the method of bisection,

Fake coin problem

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Variable size decrease
In this type, the reduction in the size of the
problem instance is varied from one iteration to
another.
Eg: Euclid’s algorithm for computing
GCD of two nos.
gcd (m,n) = gcd (n, m mod n) if n> 0
m if n=0
Eg: Computing a median, Interpolation Search
and Binary Search Tree
Department
Departmentof
of ATME College of Engineering
CCSSEE
 DAGs and Topological Sorting
A dag: a directed acyclic graph, i.e. a directed graph with no
(directed) cycles

a b a b

a dag not a dag

c d c d

Arise in modeling many problems that involve prerequisite

constraints (construction projects, document version control)

Vertices of a dag can be linearly ordered so that for every edge its
starting vertex is listed before its ending vertex (topological
sorting). Being a dag is also a necessary condition for topological
sorting to be possible.
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Topological Sorting Example
Order the following items in a food chain
tiger

human

fish
sheep

shrimp

plankton wheat

Department
Departmentof
of ATME College of Engineering
CCSSEE
 DFS-based Algorithm
DFS-based algorithm for topological sorting
– Perform DFS traversal, noting the order vertices
are popped off the traversal stack
– Reverse order solves topological sorting problem
– Back edges encountered?→ NOT a dag!
Example:

b a c d

e f g h

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Source Removal Algorithm

Repeatedly identify and remove a source (a vertex with no

incoming edges) and all the edges incident to it until either no
vertex is left or
Example: 1 a there is bno source among
c the dremaining
vertices (not a dag)
e f g h
Efficiency: same as efficiency of the DFS-based algorithm, but how would you
identify a source? How do you remove a source from the dag?

a d
Example 2 c
b e
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Source Removal Algorithm
Topological Sort(G)
1. Find the indegree INDG(n) of each node n of
G.
2. Put in a queue Q all the nodes with zero
indegree.
3. Repeat step 4 and 5 until G becomes empty.
4. Repeat the element n of the queue Q and
add it to T (Set Front = Front +1).
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Source Removal Algorithm
5.Repeat the following for each neighbour, m of
the node n
a) Set INDEG(m) = INDG(m)-1
b) If INDEG(m) = 0 then add m to the rear end
of the Q.
6. Exit.

Note: For Problems refer class notes

Department
Departmentof
of ATME College of Engineering
CCSSEE
 MODULE – 3

GREEDY METHOD

Department of
CSE
 Greedy Method
• Approach for Solving problem
• Used for Solving Optimization Problem
• Optimization Problem : Problems which demands
minimum/maximum results
• Example:
12 hrs Minimum cost
A B
S1 S2 S3 S4 S5……

Optimal solution Feasible solutions

There will be only one minimum solution

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 139
CCSSEE
Strategies used for Optimization
Problem
• Greedy Method
• Dynamic Programming
• Branch and Bound

Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 140
CCSSEE
 Greedy Technique
Greedy algorithms, construct a solution through a
sequence of steps, each step expanding a partially
constructed solution obtained so far, until a complete
solution to the problem is reached.

 feasible -it has to satisfy the problem’s constraints

 locally optimal - it has to be the best local choice
among all feasible choices available on that step
 irrevocable - once made, it cannot be changed on
subsequent steps of the algorithm

24-08-2020 Department of CSE ATME College of Engineering 4 141

General method control abstraction
Algorithm Greedy(a, n)
// a[1..n] contains the ‘n’ inputs
{
Solution := 0; //Initialize the solution
for i:= 1 to n do
{
X : = Select(a);
If Feasible(Solution, x) then
Solution:= Union(Solution, x);
}
Return Solution;
}
Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 142
CCSSEE
 Applications of the Greedy Strategy
• Optimal solutions:
– change making for “normal” coin denominations
– minimum spanning tree (MST)
– single-source shortest paths
– simple scheduling problems
– Huffman codes
• Approximations/heuristics:
– traveling salesman problem (TSP)
– knapsack problem
– other combinatorial optimization problems

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 143

CCSSEE
Differences b/w Divide and conquer and greedy
Method

144
 Change-Making Problem
• Problem Statement: Given coins of several denominations
find out a way to give a customer an amount with fewest
number of coins.
• Example: if denominations are 1,5,10, 25 and 100 and the
change required is 30, the solutions are,
• Amount : 30
• Solutions : 3 x 10 ( 3 coins )
6 x 5 ( 6 coins )
1 x 25 + 5 x 1 ( 6 coins )
1 x 25 + 1 x 5 ( 2 coins )
The last solution is the optimal one as it gives us change only with 2
coins. Department
Departmentof
ofCSE ATME
ATMECollege
CollegeofofEngineering
Engineering 145
CSE
 Change-Making Problem

Given unlimited amounts of coins of denominations d1 > … >dn,

give change for amount n with the least number of coins

Example: d1 = 25c, d2 =10c, d3 = 5c, d4 = 1c and n = 48c

Greedy solution is optimal for any amount and “normal’’ set of

denominations

Solution: <1, 2, 0, 3>

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 cashier’s Algorithm
Algorithm coinchange() {25,10,1} for 30c
//Input: Denomination d[1] > d[2] >
d*3+ … d*n+
//Amount to obtain change – C
// Output: The optimal number of
coins for change of C, is stored in
Coins[i]

for i  1 to n do
{
Coins[i] = C/d[i];
C = C mod d[i]
Print coins[i]
}

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Change-Making Problem

For example, d1 = 25c, d2 = 10c, d3 = 1c, and n = 30c

Solution: <1, 0, 5>

May not be optimal for all denominations

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Knapsack Problem
(Fractional knapsack problem)
Given n objects and a knapsack or bag. Object i has a
weight wi and the knapsack has a capacity m. if the
fraction Xi, 0<=Xi<=1, of object i is placed into the
knapsack, then a profit of Pi*Xi is earned.

The objective is to maximize the total profit earned.

Since the knapsack capacity is m, we require the total
weight of all chosen objects to be at most m.

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Knapsack Problem - 1
Obtain the optimal solution for the knapsack
problem using greedy method given the
following:
M = 15
n=7
p1,p2,p3,p4,p5,p6,p7 = 10,5,15,7,6,18,3
w1,w2,w3,w4,w5,w6,w7= 2,3,5,7,1,4,1

Department of ATME College of Engineering

CSE
There are several greedy methods to obtain the feasible solutions.

Department of ATME College of Engineering

CSE
 Profits = Solution Vector = (1, 0,1, 4/7,0,1,0)= (1, 0,1, 0.57,0,1,0)

Optimal solution using this method is (x1, x2, x3,x4,x5,x6,x7) = (1, 0,1, 0.57,0,1,0)
with profit = 47
Department of ATME College of Engineering
CSE
Profits = Solution Vector = (1, 1,4/5,0,1,1,1)= (1, 1,0.8,0,1,1,1)

Optimal solution using this method is (x1, x2, x3,x4,x5,x6,x7) = (1, 1,0.8,0,1,1,1)
with profit = 54
Optimal solution is not guaranteed using method 1 and 2
Department of ATME College of Engineering
CSE
Profits = Solution Vector = (1, 2/3,1,0, 1,1,1)= (1, 0.67,1,0, 1,1,1)

Optimal solution is (x1, x2, x3,x4,x5,x6,x7) = (1, 0.67,1,0, 1,1,1)

with profit [1*10+0.67*5+1*15+0*7+1*6+1*18+1*3]= 55.34
Weight=[1*2+0.67*3+1*5+0*7+1*1+1*4+1*1]=15
This greedy approach always results optimal solution
Department of ATME College of Engineering
CSE
 Knapsack Problem
(Fractional knapsack problem)
Given n objects and a knapsack or bag. Object i has a
weight wi and the knapsack has a capacity m. if the
fraction Xi, 0<=Xi<=1, of object i is placed into the
knapsack, then a profit of Pi*Xi is earned.

The objective is to maximize the total profit earned.

Since the knapsack capacity is m, we require the total
weight of all chosen objects to be at most m.

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeoofEEnngginineeerirningg 155

CCSSEE
 Knapsack problem

Department of ATME College of Engineering

CSE
 Knapsack Algorithm
Algorithm Greedy Knapsack(m,n)
//p[1:n] and w[1:n] contain the profits and weights respectively, of the n
objects ordered such that p[i]/w[i] >= p[i+1]/w[i+1].
// m is the knapsack size and x[1:n] is the solution vector
{
for i := 1 to n do x[i] := 0.0; //Initialize x
U := m;//sack capacity
for i:=1 to n do
{
if (w[i] > U) then break; // weight of an object is greater than sack capacity
x[i] := 1.0; U:=U-w[i];
}
If(i<=n) then x[i]:=U/w[i];
}
Analysis: Disregarding the time to initially sort the object, each
of the above strategies use O(n) time
Department of ATME College of Engineering
CSE
 Problem - 2

Obtain the optimal solution for the knapsack

problem using greedy method given the
following:
M=40 , n=3
w1,w2,w3 = 20,25,10
p1,p2,p2 = 30,40,35

Department of ATME College of Engineering

CSE
 Job Sequencing with Deadline

Given an array of jobs where every job has a deadline

and associated profit, the job is to be finished before
the deadline. It is also given that every job takes
single unit of time. So the minimum possible deadline
for any job is 1. the objective is to maximize total
profit, provided only one job can be scheduled at a
time.

Department of ATME College of Engineering

CSE
 Problem 1

For the following sequence of job, give the snapshot of

execution which will achieve maximum profit.

Jobs n= 5
p1,p2,p3,p4,p5 = 20,15,10,1,6
d1,d2,d3,d4,d5 = 2, 2, 1, 3,3

Department of ATME College of Engineering

CSE
Problem 1
Job Sequencing with Deadline

Department of ATME College of Engineering

CSE
 Minimum Spanning Tree (MST)

Spanning tree of a connected graph G: a connected acyclic

subgraph of G that includes all of G’s vertices

6 c 6 c c
a a a
4 1 1 1
4
2 2
d d d
b 3 b b 3

Department of ATME College of Engineering

CSE
 Minimum spanning tree of a weighted, connected graph G: a
spanning tree of G of the minimum total weight

Example:

6 c 6 c c

a a a
1 1 1
4 4
2 2

d d d
b b b 3
3

COST=11 COST=6

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 165

CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Minimum Cost spanning Tree
algorithms
• Prim’s algorithm
• Kruskal’s algorithm

Department
Departmentof
of ATME College of Engineering
CCSSEE
MST – Prim’s algorithm

Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Departm
Department
ent of
of ISE BM
ATSME
I nCo
s titluletg
e eofo fTE
encg
hinnoelo
egriyng
a Mgmt 170
CSE nd
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 171
ECSE
 Efficiency
 The time efficiency of depends on the data
structures used for implementing the priority
queue and for representing the input graph.
 Since we have implemented using weighted
matrix and unordered array, the efficiency is
O(|V2|).
 If we implement using adjacency list and the
priority queue for min-heap, the efficiency is
O(|E|log|V|).

Department of CSE ATME College of Engineering 172

 Kruskal’s algorithm
Kruskal's algorithm finds MST of a weighted
connected graph G=<V,E> as an acyclic subgraph
with |V| - 1 edges. Sum of all the edges weight
should be minimum.
The algorithm begins by sorting the graph’s
edges in increasing order of their weights.
Then it scans this sorted list starting with the
empty sub graph and it adds the next edge on
the list to the current sub graph, if such an
inclusion doesn’t create a cycle and simply
skipping the edges.
Department of CSE ATME College of Engineering 173
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Time complexity
The crucial check whether two vertices belong to the
same tree can be found out using union -find algorithms.

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Shortest paths – Dijkstra’s
algorithm
The Dijkstra’s algorithm finds the shortest path
from a given vertex to all the remaining vertices
in a diagraph.
The constraint is that each edge has non-
negative cost. The length of the path is the sum
of the costs of the edges on the path.
We have to find out the shortest path from a
given source vertex ‘S’ to each of the
destinations (other vertices ) in the graph.
DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg
CCSSEE
 Example
1 2 3 4
5
Initially S 0 1 0 0 0 0

1
d ∞ 1 60 100 ∞ 10
60 100
1

10 60 10
2 3
0
10
20 2 3
50 20

20
4 50 20
5
5
4
5
DDeeppaarrt tmmeennttooff
CCSSEE
5
BAMTSMEInCstoitluletgeeooffTEencghinnoe leorgiyngandMgmt
 Example
1 2 3 4 5

S 1 0 0 0 1

1
d 1 60 100 ∞ 10
60 100
1

10 60 100
2 3
10
20 2 3
50 20

20
4 50 20
5
5
4
5
DDeeppaarrt tmmeennttooff
CCSSEE
5
BAMTSMEInCstoitluletgeeooffTEencghinnoe leorgiyngandMgmt
 Example 1 2 3 4 5

S 1 0 0 1 1

1
d 1 60 100 15 10
60 100
1

10 60 100
2 3
10
20 2 3
50 20

20
4 50 20
5
5
4
5
DDeeppaarrt tmmeennttooff
CCSSEE
5
BAMTSMEInCstoitluletgeeooffTEencghinnoe leorgiyngandMgmt
 Example
1 2 3 4 5

S 1 0 1 1 1

1
d 1 60 35 15 10
60 100
1

10 60 100
2 3
10
20 2 3
50 20

20
4 50 20
5
5
4
5
DDeeppaarrt tmmeennttooff
CCSSEE
5
BAMTSMEInCstoitluletgeeooffTEencghinnoe leorgiyngandMgmt
 Example Final distance form note 1 to
all other nodes
1 2 3 4 5

S 1 1 1 1 1

1
d 1 60 35 15 10
60 100
1

10 60 100
2 3
10
20 2 3
50 20

20
4 50 20
5
5
4
5
DDeeppaarrt tmmeennttooff
CCSSEE
5
BAMTSMEInCstoitluletgeeooffTEencghinnoe leorgiyngandMgmt
 b 4
c
Example2 a
3
7 2
dd
5 4
6

Tree vertices Remaining vertices

4
b c
a(-,0) b(a,3) c(-,∞) d(a,7) e(-,∞) 3
2 5
6
a d e
7 4

b 4
c
b(a,3) c(b,3+4) d(b,3+2) e(-,∞) 3 6
2 5
a d e
7 4

b 4 c
d(b,5) c(b,7) e(d,5+4) 3 6
2 5
a d e
7 4
4
b c
c(b,7) e(d,9) 3 6
2 5
a d e
7 4
e(d,9)
Department of ATME College of Engineering 184
CSE
 Dijkstra’s algorithm
Dijkstra’s( s)
// Finds shortest path from source vertex to all other vertices
//Input: Weighted connected graph G=<V,E> with nonnegative
weights and its vertices s
//Output: The length of distance of a shortest path from s to v
{
1. for i = 1 to n do // Intialize
S[i] = 0;
d[i] = a[s][i];

2. S[s] = 1; //Assume 1 as the source vertex

d[s] = 1;

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Dijkstra’s algorithm
3. for i = 1 to n do
{
Choose a vertex u in v-s such that d[u] is
minimum
S=s u
for each vertex v in v-s do
d[v] = min{ d[u], d[u]+c[u,v]}
}
}

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Key points on Dijkstra’s
algorithm
Doesn’t work for graphs with negative weights
(whereas Floyd’s algorithm does, as long as
there is no negative cycle).
Applicable to both undirected and directed graphs.
Efficiency O(|V2|) for graphs represented by weight
matrix and array implementation of priority queue
O(|E|log|V|) for graphs represented by adj. lists and
min-heap implementation of priority queue

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 MODULE – 4

DY N A M I C P RO G R A M M I N G

Department of ATME College of Engineering 188

CSE
 Dynamic Programming
Invented by American mathematician Richard Bellman in the
1950s to solve optimization problems
Optimization Problem : Problems which demands minimum/maximum
results
Dynamic “ means “changing”
Programming” means “planning”
Dynamic Programming is a general algorithm design technique
for solving problems with overlapping sub-problems.
Main idea:
-Solve smaller instances once.
-Record solutions in a table.
-Get solution to a larger instance from some smaller instances.
-Optimal solution for the initial instance is obtained from that table.

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 189

CCSSEE
 Principle of Optimality

Problems can be solved by taking sequence of

decisions to get optimal solutions

Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 190
CCSSEE
Example: Fibonacci numbers

DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 191

ECSE
Example: Fibonacci numbers

Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 194
ECSE
 Examples of DP algorithms
• Computing a binomial coefficient

• Longest common subsequence

• Warshall’s algorithm for transitive closure

• Floyd’s algorithm for all-pairs shortest paths

• Constructing an optimal binary search tree

• Some instances of difficult discrete optimization problems:

- traveling salesman
- knapsack

Department of ATME College of Engineering 195

CSE
 Multistage Graph
A Multi stage graph G = <V,E> which is a directed graph. In
this graph all the vertices and partitioned into K stages
where K>=2.

In multistage graph problem we have to find the shortest

path from source to sink.

The cost of each path is calculated by using the weight given

along that edge.

In multistage graph can be solved using forward and

backward approach.

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 196

CCSSEE
Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 197
CCSSEE
DeDeppaartr tmmeennttooffCS BM
ATSME
I nCo
s titlu
l etg
eeofo fTE
encg egy
hinnoelo ri and Mgmt 198
ECSE ng
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 199
ECSE
DeDeppaartr tmmeennttooffCS BM
ATSMIEnCo
s titluletg
e eofo fTE
encg
hni noeloegryi and Mgmt 200
ECSE ng
Department
Departmentof
of ATME College of Engineering
CCSSEE
Warshall’s Algorithm: Transitive Closure

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Warshall’s Algorithm: Transitive
Closure

Constructs transitive closure T as the last matrix in the sequence

of n-by-n matrices R(0), … , R(k), … , R(n) where
R(k)[i,j] = 1 iff there is nontrivial path from i to j with only the first
k vertices allowed as intermediate
Note: that R(0) = A (adjacency matrix), R(n) = T (transitive closure)

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 205
ECSE
Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 206
CCSSEE
 Warshall’s Algorithm (recurrence)
On the k-th iteration, the algorithm determines for every pair of
vertices i, j if a path exists from i and j with just vertices 1,…,k
allowed as intermediate

{
R(k)[i,j] =
R(k-1)[i,j]
or
(path using just 1 ,…,k-1)

R(k-1)[i,k] and R(k-1)[k,j] (path from i to k

and from k to j
using just 1 ,…,k-1)
k

Initial condition?
j
Department of
CSE
 Warshall’s Algorithm (matrix generation)

Recurrence relating elements R(k) to elements of R(k-1) is:

R(k)[i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j])

It implies the following rules for generating R(k) from R(k-1):

Rule 1 If an element in row i and column j is 1 in R(k-1),

it remains 1 in R(k)

Rule 2 If an element in row i and column j is 0 in R(k-1),

it has to be changed to 1 in R(k) if and only if
the element in its row i and column k and the element
in its column j and row k are both 1’s in R(k-1)

Department of
CSE
 Warshall’s Algorithm (pseudocode and analysis)

Time efficiency: Θ(n3)

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Floyd’s Algorithm: All pairs shortest paths
Problem: In a weighted (di)graph, find shortest paths between
every pair of vertices

Same idea: construct solution through series of matrices D(0), …,

D (n) using increasing subsets of the vertices allowed
as intermediate

Example:

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
DeDeppaartr tmmeennttooffCS BMATSMIEnstCol
itutelegeof
of Technology
Engineering
and Mgmt 211
ECSE
 Floyd’s Algorithm (matrix generation)

On the k-th iteration, the algorithm determines shortest paths

between every pair of vertices i, j that use only vertices among
1,…,k as intermediate

D(k)[i,j] = min {D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]}

D(k-1)[i,k]
k
i
D(k-1)[k,j]
D(k-1)[i,j]

j
Initial condition?
Department of ATME College of Engineering 212
CSE
Time efficiency: Θ(n3)
Note: Works on graphs with negative edges but without negative
cycles.
DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 213
CCSSEE
 Optimal Binary Search Tree
Binary Tree

Department
Departmentof
of ATME College of Engineering
CCSSEE
total number of BSTs with n nodes is given
by C(2n,n)/(n+1)

Department
Departmentof
of ATME College of Engineering
CCSSEE
Cost of searching any Key

Department
Departmentof
of ATME College of Engineering
CCSSEE
Cost of BST-Frequencies

18

DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 217

ECSE
 Optimal Binary Search Tree
Problem: Given n keys a1 < …< an and probabilities p1, …, pn
searching for them, find a BST with a minimum
average number of comparisons in successful search.
Since total number of BSTs with n nodes is given by C(2n,n)/(n+1),
which grows exponentially, brute force is not recommended.

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
Example: What is an optimal BST for keys A, B, C, and D with
search probabilities 0.1, 0.2, 0.4, and 0.3, respectively?

C
Average # of comparisons
= 1*0.4 + 2*(0.2+0.3) + 3*0.1
B D
= 1.7
A

DDeeppaarrt tmmeennttooff AATTMMEECCooleleggeeooffEEnngginineeerirningg

CCSSEE
 Obtain the optimal binary search tree for the
following

(do, if, int, while) with the following

probability(0.1,0.2,0.4,0.3)

DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 220

ECSE
DeDeppaartr tmmeennttooffCS BM
ATSMIEnCo
s titluletg
e eofo fTE
encg
hn logy
i noeeri and Mgmt 221
ECSE ng
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 226
ECSE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 227
ECSE
Department
Departmentof
of ISE ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 228
CSE
Department
Departmentof
of ATME
ATMECollege
CollegeofofEngineering
Engineering 229
CCSSEE
 Knapsack Problem
Given n objects of known weights w1,w2…wn and
profit p1, p2, … pn for those n objects and a knapsack
of capacity M i.e is not exceeding the weight M. Let a
variable xi be ‘0’ if we do not select the object ‘i’ or ‘1’
if we include the object ‘i’ into the knapsack.

The objective is to maximize the total profit

earned. Since the knapsack capacity is M, we
require the total weight of all chosen objects to
be at most M.

Department of
CSE
 Knapsack problem

Department of
CSE
For the given instances of problem obtain the
optimal solution for the knapsack problem

The capacity of knapsack is W=5

Department of
CSE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
ofCSE BMS
ATME
Institute
CollegeofofTechnology and M gmt
Engineering 234
CSE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg 235
ECSE
Department of CSE ATME College of Engineering 236
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
Department
Departmentof
of ATME College of Engineering
CCSSEE
To find items to be selected

Department
Departmentof
of ATME College of Engineering
CCSSEE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
DeDeppaartr tmmeennttooffCS ATATMMEECoColeleggeeooffEEnngginineeeeririnngg
ECSE
 Knapsack Problem by DP (pseudocode)
Algorithm DPKnapsack(int: w[1..n], int: p[1..n], M)
int: V[0..n,0..M]
for j := 0 to M do
V[0,j] := 0
for i := 0 to n do
V[i,0] := 0
for i := 1 to n do
for j := 1 to M do
if w[i]  j and p[i] + V[i-1,j-w[i]] > V[i-1,j] then
V[i,j] := p[i] + V[i-1,j-w[i]];
else
V[i,j] := V[i-1,j];
return V[n,M]

Running time and space: O(nW).

DDeeppaarrtmmeenntoof AATTMMEECCooleleggeeoofEEnngginineeerirningg 244

CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Memory Function Knapsack
Example: Knapsack of capacity M = 5
item weight value
1 2 $8
2 1 $6
3 3 $16
4 2 $11 capacity j
0 1 2 3 4 5
0 0 0 0 0 0 0
w = 2, p = 8 1 0 -1 -1 -1 -1 -1
1 1
w2 = 1, p2= 6 2 0 -1 -1 -1 -1 -1

w3 = 3, p3= 16 3 0 -1 -1 -1 -1 -1
w4 = 2, p4= 11 4 0 -1 -1 -1 -1 -1 ? 249
 Memory Function Knapsack

i=4, j=5, p[i]=11, wi =2

J-wi = 5-2 = 3 ( able to fit into knapsack)
Find V[4,5] = max{ mfk[i-1,j], p[i] + mfk[i-1, j-wi]}
= max{ mkf(3,5), 11+mfk(3,3)}
= max{ ---------, 11+ -------)}
Find V[3,5] = max{ mkf(2,5), 16+mfk(2,2)}
= max{ , 16+ }
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Memory Function Knapsack
Find V[3,3] = max{ mfk[i-1,j], p[i] + mfk[i-1, j-wi]}
= max{ mkf(2,3), 16+mfk(2,0)}
= max{ ----, 16+ -----)}
Find V[2,5] = max{ mkf(1,5), 6+mfk(1,4)}
= max{ , 6+ }
Find V[2,2] = max{ mkf(1,2), 6+mfk(1,1)}
= max{ , 6+ }

Department
Departmentof
of ATME College of Engineering
CCSSEE
Find V[2,3] = max{ mkf(1,3), 6+mfk(1,2)}
= max{ , 6+ -}
Find V[1,5] = max{ mkf(0,5), 8+mfk(0,3)}
= max{ 0 , 8 + 0} = 8
Find V[1,4] = max{ mkf(0,4), 8+mfk(0,2)}
= max{ 0 , 8 + 0} = 8 Back
Substitute
Find V[1,2] = max{ mkf(0,2), 8+mfk(0,0)} these
values
= max{ 0 , 8 + 0} = 8
Find V[1,3] = max{ mkf(0,3), 8+mfk(0,0)}
= max{ 0 , 8 + 0} = 8
Find V[1,1] = max{ mkf(0,1)} = 0

Department
Departmentof
of ATME College of Engineering
CCSSEE
Find V[2,3] = max{ mkf(1,3), 6+mfk(1,2)}
= max{ 8, 6 + 8} = 14
Find V[1,5] = max{ mkf(0,5), 8+mfk(0,3)}
= max{ 0 , 8 + 0} = 8
Find V[1,4] = max{ mkf(0,4), 8+mfk(0,2)}
= max{ 0 , 8 + 0} = 8 Back
Substitute
Find V[1,2] = max{ mkf(0,2), 8+mfk(0,0)} these
values
= max{ 0 , 8 + 0} = 8
Find V[1,3] = max{ mkf(0,3), 8+mfk(0,0)}
= max{ 0 , 8 + 0} = 8
Find V[1,1] = max{ mkf(0,1)} = 0

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Memory Function Knapsack
Find V[3,3] = max{ mfk[i-1,j], p[i] + mfk[i-1, j-wi]}
= max{ mkf(2,3), 11+mfk(2,0)}
= max{ 14 , 16+ 0)} = 16
Find V[2,5] = max{ mkf(1,5), 6+mfk(1,4)}
= max{ 8, 6+ 8} = 14
Find V[2,2] = max{ mkf(1,2), 6+mfk(1,1)}
= max{ 8, 6 + 0} = 8

Department
Departmentof
of ATME College of Engineering
CCSSEE
 Memory Function Knapsack
V[i,j] = max{ mfk[i-1,j], p[i] + mfk[i-1, j-wi]}
i=4, j=5, p[i]=11, wi =2
J-wi = 5-2 = 3 ( able to fit into knapsack)
Find V[4,5] = max{ mfk[i-1,j], p[i] + mfk[i-1, j-wi]}
= max{ mkf(3,5), 11+mfk(3,3)}
= max{ 24 , 11+ 16)} = 27
Find V[3,5] = max{ mkf(2,5), 16+mfk(2,2)}
= max{ 14, 16+ 8} = 24
Department
Departmentof
of ATME College of Engineering
CCSSEE
 Memory Function Knapsack
Example: Knapsack of capacity M = 5
item weight value
1 2 $8
2 1 $6
3 3 $16
4 2 $11 capacity j
0 1 2 3 4 5
0 0 0 0 0 0 0 0 0 0 0 0 0
w1 = 2, p1= 8 1 0 -1 -1 -1 -1 -1 0 0 8 8 8 8
w = 1, p = 6 2 0 -1 -1 -1 -1 -1 0 -1
2 2
8 14 -1 14
w3 = 3, p3 = 16 3 0 -1 -1 -1 -1 -1 0 -1 -1 16 -1 24
w4 = 2, p4= 11 4 0 -1 -1 -1 -1 -1 ? 0 -1 -1 -1 -1 27 256
 Memory Function Knapsack Algo.
ALGORITHM MFKnapsack(i, j) //Implements the memory function method for
the knapsack problem //Input: A nonnegative integer i indicating the number
of the first // items being considered and a nonnegative integer j indicating //
the knapsack capacity //Output: The value of an optimal feasible subset of the
first i items //Note: Uses as global variables input arrays Weights[1..n],
Values[1..n], //and table V[0..n, 0..W]whose entries are initialized with −1’s
except for //row 0 and column 0 initialized with 0’s
if V[i, j]< 0
if j<Weights[i] = value←MFKnapsack(i −1,j)
else value←max,MFKnapsack(i −1, j),
values[i]+MFKnapsack(i −1, j−Weights*i+)-
V[i, j+←value
return V[i, j]
Department of CSE ATME College of Engineering 257
 MODULE – 5

BACKTRACKING

Department of ATME College of Engineering

CSE
 Backtracking

Backtrack’ the Word was first introduced by Dr. D.H. Lehmer in

1950s.
•R.J Walker Was the First man who gave algorithmic description
in 1960.
• Later developed by S. Golamb and L. Baumert.

Backtracking technique resembles a depth-first – search

in a directed graph. The graph concerned here is usually
a tree, the aim of backtracking is to search the state
space tree systematically. The aim of the search is to find
solutions to some problems.

Department of ATME College of Engineering

CSE
 What is Backtracking?

When the search begins, solution to the problem is unknown.

Each move along an edge of the tree corresponds to adding a
new element to a partial solution, that is to narrowing down the
remaining possibilities for a complex solution.

The search is successful if, a solution can be completely

defined. At this stage an algorithm may terminate or it may
continue for an alternative solution.
The search is unsuccessful if at some stage the partial solution
constructed so far cannot be completed. In this case the search
backtracks like a depth first search, removing elements that
were added at each stage.

Department of ATME College of Engineering

CSE
 State Space Tree

In state space tree, root represents an initial state before the

search for a solution begins. The nodes of the first level in the
tree represent the choice made for the first component of a
solution, the nodes of the second level represent the choices for
the second components, and so on. A node in a state space tree
is said to be promising if it corresponds to a partially
constructed solution that may lead to a complete solution;
otherwise a node is said to be non promising.

Department of ATME College of Engineering

CSE
Department of ATME College of Engineering
CSE
N-Queen Problem

Department of ATME College of Engineering

CSE
N Queen Problem

Department of ATME College of Engineering

CSE
 Constraints
Explicit Constraints: All ‘n’ queens must be placed on the
chessboard in the columns 1,2,3, …. N. Xi belongs to S where S =
{1,2,3, …. N }

Implicit Constraints: In this all Xi Values must be distinct

No two queens can be on the same row
No two queens can be on the same column
No two queens can be on the same diagonal

Department of ATME College of Engineering

CSE
 Horizontal Attack:

Row wise attacking is avoided by placing 1st queen in

1st row, 2nd queen in 2nd row and so on.
By placing ith queen in ith row, horizontal attacking can
be avoided

Department of ATME College of Engineering

CSE
 Vertical Attack:
(i, x[i]) means the position of ith queen in row i and
column x[i]
(k, x[k]) means the position of kth queen in row k
and column x[k]
If ith & kth queen are in same column then
X[i] == x[k] --------------- (1)
Hence indicate that queens attack vertically
Q1 (1,1) & (4,1) x[i] == x[k] to be avoided

Q4

Department of ATME College of Engineering

CSE
 Diagonal Attack:
Top left corner to bottom right corner: The difference
between row value and column value is same.
1,1 1,2 1,3 1,4 (1,3) & (2,4) |i - x[i]| = |k - x[k]|-------(2) to be
2,1 2,2 2,3 2,4
avoided
3,1 3,2 3,3 3,4
4,1 4,2 4,3 4,4

Department of ATME College of Engineering

CSE
 Diagonal Attack:
Top right corner to bottom left corner: The difference
between row value and column value is same.
1,1 1,2 1,3 1,4 (1,3) & (3,1) i + x[i] = k + x[k] ------(3) to be
2,1 2,2 2,3 2,4
avoided
3,1 3,2 3,3 3,4 Using eqn. (2) and (3)
i – k = x[i] - x[k] -----------------(4)
4,1 4,2 4,3 4,4
i – k = - x[i] + x[k] ----------------(5)

|i – k| = |x[i] - x[k]| indicates queens attack diagonally.

X[i] == x[k] || abs(i –k) = abs(x[i] – x[k])  two queens

attack each other and cannot be placed.

Department of ATME College of Engineering

CSE
Algorithm

Department of ATME College of Engineering

CSE
State Space Tree for 4 Queens

Department of ATME College of Engineering

CSE
Two Solutions of 4 Queen Problem

Department of ATME College of Engineering

CSE
 Hamiltonian Cycle
Hamiltonian Path in an undirected graph is a path that visits each vertex exactly
once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that
there is an edge (in graph) from the last vertex to the first vertex of the
Hamiltonian Path. Determine whether a given graph contains Hamiltonian Cycle
or not. If it contains, then print the path. Following are the input and output of
the required function.
Input:
A 2D array graph[V][V] where V is the number of vertices in graph and
graph[V][V] is adjacency matrix representation of the graph. A value graph[i][j] is
1 if there is a direct edge from i to j, otherwise graph[i][j] is 0.
Output:
An array path[V] that should contain the Hamiltonian Path. path[i] should
represent the ith vertex in the Hamiltonian Path. The code should also return
false if there is no Hamiltonian Cycle in the graph.

Department of ATME College of Engineering

CSE
Example 2

Department of ATME College of Engineering

CSE
Department of ATME College of Engineering
CSE
Example

Department of ATME College of Engineering

CSE
Hamiltonian Cycle
X[1] =1 X[2] = 0 X[3]=0 X[4]=0

1 2
1

2 3 4
4 3
3 2 4 3

Dead end
4 2

1 1

Solution Solution

Department of ATME College of Engineering

CSE
Department of ATME College of Engineering
CSE
for (int i = 1; i <= n; i++)
x[i] = 0; 1
x[1] = 1;
void HamiltonianMethod(int k) { 2 3 4
while (true) {
NextValue(k, G, x, n);
if (x[k] == 0) 3 2 4
3
return;
if (k == n) { Dead end
for (int i = 1; i <= k; i++) 4 2
System.out.print(x[i] + " ");
System.out.println(x[1]);
System.out.println(); 1 1
found = true;
return; Solution
} else
HamiltonianMethod(k + 1);
}
Department of CSE ATME College of Engineering 279
}
 Hamiltonian Cycle
void NextValue(int k, int G[][], int x[], int n) {
while (true) {
Enter the number of the vertices: 4
x[k] = (x[k] + 1) % (n + 1);
if (x[k] == 0)
If edge between the following vertices
return;
enter 1 else 0:
if (G[x[k - 1]][x[k]] != 0) {
1 and 2: 1
int j;
1 and 3: 1
for (j = 1; j < k; j++)
1 and 4: 1
if (x[k] == x[j])
2 and 3:
break;
1
if (j == k)
2 and 4: 0
if ((k < n) || ((k == n) && G[x[n]][x[1]] != 0))
3 and 4: 1
return;
}
Solution:
}
12341
}
14321

Department of
CSE
 1

2 3 4

3 2 4 3

Dead end
4 2

1 1

Solution Solution

Department of
CSE
Department of
CSE
Sum of subsets

Department of
CSE
Sum of subsets

Department of
CSE
 Sum of Subsets
Find a subset of a given set S= {S1, S2, S3, S4, ------ Sn}
Of n +ve integers whose sum is equal to given +ve integer d subject
to the constrains

1. Implicit: All Xi values should be distinct and should belong to

the set S
2. Explicit: optimal solution be ∑𝑘 𝑆𝑖 = d
𝑖=1

Xi of the solution vector is either 1 or 0 depending on weather the

weight Wi is included or not.

Department of
CSE
For a node at level i, the left child corresponds to Xi = 1
and the right child to Xi = 0

The bounding function X[X1, X2, X3, -----Xn] = true iff

𝑊𝑖 𝑋𝑖 + ∑ 𝑛 𝑊𝑖 ≥ 𝑑
𝑘
∑𝑖 𝑖=𝑘+1
=1
X1, X2, -----Xk cannot lead to an promising node if this
condition is not satisfied.

Department of
CSE
The bounding function can be strengthened if we
assume that Wi’s are initially in increasing order.

In this case X1 – Xk can not lead to promising node if

X[X1, X2, X3, -----Xn] = true iff
𝑘
∑ 𝑊𝑖 𝑋𝑖 + 𝑊 𝑘 + 1 𝑑
≤
𝑖=1

X1, X2, -----Xk cannot lead to an promising node if this

condition is not satisfied.
Department of
CSE
Therefore the bounding function will be
𝑊𝑖 𝑋𝑖 + ∑ 𝑛 𝑊𝑖 ≥ 𝑑
𝑘
∑𝑖 𝑖=𝑘+1
=1

𝑎𝑛𝑑 ∑ 𝑊𝑖 𝑋𝑖 + 𝑊 𝑘 + 1 𝑑
≤
𝑖=1

Department of
CSE
 State space tree
0, 1, 21

X1=1 X1=0

3, 2, 18 0, 2, 18

X2=1 X2=0

8, 3, 13 3, 3, 13

X3=1 X3=0 X3=1 X3=0

14, 4, 7 8, 4, 7 9, 4, 7 3, 4, 7

X4=1
15, 5, 0
Solution

Department of
CSE
Sum of subsets

Department of
CSE
Sum of subsets

Department of
CSE
Sum of subsets

Department of
CSE
Coding
for (int i = 1; i <= n; i++)
sum = sum + S[i];
if (sum < d || S[1] > d)
System.out.println("No Subset possible");
else
SumofSub(0, 0, sum);

Department of
CSE
static void SumofSub(int i, int weight, int total) {
if (promising(i, weight, total) == true)
if (weight == d) {
for (int j = 1; j <= i; j++) {
if (soln[j] == 1)
System.out.print(S[j] + " ");
}
System.out.println();
} else {
soln[i + 1] = 1;
SumofSub(i + 1, weight + S[i + 1], total - S[i + 1]);
soln[i + 1] = 0;
SumofSub(i + 1, weight, total - S[i + 1]);
}
} Department of CSE ATME College of Engineering 294
static boolean promising(int i, int weight, int
total) {
return ((weight + total >= d) && (weight == d ||
weight + S[i + 1] <= d));

Department of
CSE
Graph Coloring

Department of
CSE
Department of
CSE
Department of
CSE
Graph Coloring

Department of
CSE
Graph Coloring

Department of
CSE
 Branch and Bound
The term Branch means the way in which we search the
state space tree and Bound means assigning bounding
function at each node. This bounding function is used to
prevent the expansion of nodes that cannot possibly
lead to an answer node.

Basically there are two methods used in branch and

bound technique.

1. FIFO based Branch & Bound

2. In this method, the live node form a queue (FIFO
Structure) & each live node will be taken from the
queue and next live node is selected.
Department of
CSE
 Branch and Bound

Least Cost Branch and Bound

At each node, an intelligent ranking function is used to
assign a value to that node. The next live node is
selected on the basis of the least cost.

Travelling sales man problem, a sales man must visit n

cities. The sales man visits each city exactly once and
comes back to the starting city.

The travelling sales man problem is minimization

problem and hence we require to find the lower bound.

Department of
CSE
 Example 1
Assignment Problem : given n jobs <j1,j2,--- jn> and n persons
<p1,p2,p3 ---pn>, it is required to assign all n jobs to all n persons
with the constraint that one job has to be assigned to one person
and the cost involved in completing all the jobs should be
minimum.

J1 J2 j3 j4
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4

Department of
CSE
 Example 1
J1 J2 j3 j4 Take minimum in each row
A 9 2 7 8 2
B 6 4 3 7 3
C 5 8 1 8 1

D 7 6 9 4 4

10
a  J1 a  J2 a  J3 a  J4
a 9 2 7 8
b 3 3 4 3
c 8 5 5 5
d 4 4 4 6
24 14 20 22

Department of
CSE
 Example 1
J1 J2 J3 J4 Take minimum in each row
A 9 2 7 8 2
B 6 4 3 7 3
C 5 8 1 8 1

D 7 6 9 4 4

10
b  J1 b  J3 b  J4
a 2 2 2
b 6 3 7
c 1 5 1
d 4 4 7
13 14 17

Department of
CSE
 Example 1
J1 J2 J3 J4 Take minimum in each row
A 9 2 7 8 2
B 6 4 3 7 3
C 5 8 1 8 1

D 7 6 9 4 4

10
C  J3 C  J4 C  J4
a 2 2 a 2
b 6 6 b 6
c 1 8 c 1
d 4 9 d 4
13 25 13

Department of
CSE
 Start
Lb=10

a –> J1 a – >J2 a –> J3 a –> J4

Lb=24 Lb=14 Lb=20 Lb=22

b –> J1 b –> J3 c –> J4

Lb=13 Lb=14 Lb=17

c –> J3 c –> J4
Lb=13 Lb=25

d –> J4
Lb=13
Department of
CSE
 Example 2

J1 J2 j3 j4
A 10 3 8 9
B 7 5 4 8
C 6 9 2 9
D 8 7 10 5

Department of
CSE
 Knapsack Problem
Knapsack Problem: Given n items of known weights wi and values vi, i=1, 2, . . . ,
n,and a knapsack of capacity W, find the most valuable subset of the items that
fit in the knapsack. It is convenient to order the items of a given instance in
descending order by their value-to-weight ratios. Then the first item gives the
best payoff per weight unit and the last one gives the worst payoff per weight
unit

Department of
CSE
First arrange in V/W in decreasing order
Since it is a maximization problem. The upper bound is calculated
using the function

i =0 , v=0, w=0 v i+1/wi+1 = 10

Ub = 0 + (10) 10 = 100

Department of
CSE
 w=0. v=0
Ub = 100

With item 1 Without item 1

i =1, w=4. v=40, v i+1/wi+1 = 6 i =1, w=0. v=0, v i+1/wi+1 = 6
Ub = v + (W-w)(v i+1/wi+1 ) Ub = v + (W-w)(v i+1/wi+1 )
= 40 + 6. 6 = 0 + 10 . 6
= 76 = 60

With item 2 With out item 2

i =2, w=7. v=42, v i+1/wi+1 = 5 i =2, w=0+4. v=40+0, v i+1/wi+1 =
5
Ub = v + (W-w)(v i+1/wi+1 )
= 42 + (10 – 11) . 5 Ub = v + (W-w)(v i+1/wi+1 )
= Not Feasible = 40 + 6. 5
= 70

Department of
CSE
 w=0. v=0
Ub = 100

With item 3 Without item 3

i =3, w=5+4. v=40+25, v i+1/wi+1 = 4 i =3, w=4+0. v=40+0, v i+1/wi+1 = 4
Ub = v + (W-w)(v i+1/wi+1 ) Ub = v + (W-w)(v i+1/wi+1 )
= 65 + 1. 4 = 40 + 6 . 4
= 69 = 64

With item 4 With out item 4

i =4, w=9+3 =12. i =4, w=0+9. v=65+0, v i+1/wi+1 = 1
Ub = v + (W-w)(v i+1/wi+1 ) Ub = v + (W-w)(v i+1/wi+1 )
= Not Feasible = 65 + 1. 1
= 66

Department of
CSE
 w=0. v=0
Ub = 100

With item 1 Without item 2

i =1, w=4. v=40, v i+1/wi+1 = 6 i =1, w=0. v=0, v i+1/wi+1 = 6
= 76 = 60

With item 2 With out item 2

i =2, w=7. v=42, v i+1/wi+1 = 5 i =2, w=0+4. v=40+0, v i+1/wi+1 = 5
= Not Feasible = 70

With item 3 Without item 3

i =3, w=5+4. v=40+25, v i+1/wi+1 = 4 i =3, w=4+0. v=40+0, v i+1/wi+1 = 4
= 69 = 64

With item 4 With out item 4

i =4, w=9+3 =12. i =4, w=0+9. v=65+0, v i+1/wi+1 = 0
Not Feasible = 65
Department of
CSE
 Travelling Sales Person Problem
4
a d In the travelling sales man problem, a sales man must visit n
1 cities. The sales man visits each city exactly once and comes
3 2 back to the starting city.
1 The travelling sales man problem is minimization problem
b c and hence we require to find the lower bound.
5

Lower bound = lb = S / 2;
Where S = [Va+ Vb+Vc+Vd]
Va = sum of distances from vertex a to the nearest
vertices 1 + 3 = 4
Vb = 1+3 = 4
Vc = 1+2= 3
Vd = 1+2 = 3
Lb = [4 +4 +3+3] / 2 = 14 / 2 = 7

Department of
CSE
Now find,
a  b = (3+1)+(3+1)+(1+2)+(1+2) = 14/ 2 = 7
a  c = (1+3)+(3+1)+(1+2)+(1+2) = 14/ 2 = 7
a  d = (4+1)+(1+3)+(1+2)+(4+1) = 17/2 = 8

Start
Lb=7

a –> b a–>c a –> d

Lb=7 Lb=7 Lb=8

Department of
CSE
 Now find,
b  c = (3+1)+(5+1)+(5+1)+(1+2) = 19/ 2 = 9
b  d = (1+3)+(1+3)+(1+2)+(1+2) = 14/ 2 = 7
c  b = (1+3)+(5+1)+(5+1)+(1+2) = 19/2 = 9
c  d = (1+3)+(3+1)+(2+1)+(2+1) = 14/ 2 = 7
Start
Lb=7

a –> b a–>c a –> d

Lb=7 Lb=8
Lb=7

b –> c c –> b c –> d

b–>d
Lb=9 Lb=9 Lb=7
Lb=7

Department of
CSE
 Now find,
d  c = (1+3)+(1+3)+(2+1)+(1+2) = 14/2 = 7
d  b = (1+3)+(1+3)+(1+2)+(1+2) = 14/2 = 7
c  a = (1+3)+(1+3)+(1+2)+(1+2) = 14/2 = 7
b  a = (3+1)+(3+1)+(1+2)+(1+2) = 14/2 = 7
Start
Lb=7

a –> b a–>c a –> d

Lb=7 Lb=7 Lb=8

a b –> c a b –> d a c –> b a –> c  d

Lb=9 Lb=7 Lb=9 Lb=7

a b – > d  c a c  d – > b
Lb=7 Lb=7
a c  d – > b
a b – > d  c
Lb=7
Lb=7
Department of
CSE
 Thank you

24-08-2020 Department of
CSE