Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Greedy Method

General Method
 Basic Notations

• A feasible solution is any subset of the original input that satisfies a given set
of constraints.

• An objective function is an input for which a feasible solution can be

obtained that either maximizes or minimizes.

• An optimal solution is a feasible solution that maximizes or minimizes the

objective function. For a given problem, there can be only one optimal
solution.
 Optimization Problem

• Optimization problems are those for which the objective is to Maximize or

Minimize some values. For example,
• Finding the minimum number of colors needed to color a given graph.
• Finding the shortest path between two vertices in a graph
• Strategies used for optimization problems:
• Greedy method
• Dynamic programming
• Branch and Bound
 Greedy Method

• The greedy algorithm obtains an Optimal solution by making a sequence of

decisions.
• Every greedy-based problem will be given a set of inputs and constraints.
• Our objective is to find a solution vector that satisfies a set of constraints.
• Decisions are made one by one in some order.
• Each decision is made using a greedy-choice property or greedy criterion.
 Greedy Choice Property

• Global Optimal Solutions will be made with local optimal (Greedy) choices

• In the Greedy algorithm, the best choice will be selected at the moment to solve
the sub-problem that remains

• The choice of the greedy may depend on the previous choices made but it
cannot depend on future choices or the solutions to the sub-problems
 Types of Greedy Problems

• Subset Paradigm: To solve a problem (or possibly find the optimal/best solution), a
greedy approach generates a subset by selecting one or more available choices.
Example:
• Knapsack problem
• Job sequencing with deadlines
 Control abstraction for subset paradigm

Greedy(a,n) // a[1:n] contains the n inputs

{
solution= ϕ // Initialize solution
for i=1 to n do
{
x := Select(a);
if Feasible(solution , x) then
solution=Union(solution , x)
else
reject(); //if solution is not feasible
}
return solution;
}
 Three important activites

1. Selection: Selection of solution from a[] and removing it

2. Feasibility: Feasible(solution,x) is a Boolean function to determine whether x can be
included into the solution vector
3. Optimality: From the set of feasible solutions, the particular solution that minimizes
or maximizes the given objective function
 Applications

• Knapsack Problem

• Job Sequencing with deadlines

• Minimum cost spanning tree (Prims and Kruskals)

• Huffman Codes

• Single source shortest path problem

10
 Limitations

1. The greedy algorithm makes judgments based on the information at each

iteration without considering the broader problem; hence it does not produce
the best answer for every problem.
2. The problematic part of a greedy algorithm is analyzing its accuracy. Even with
the proper solution, it is difficult to demonstrate why it is accurate.
3. Optimization problems (Dijkstra’s Algorithm) with negative graph edges
cannot be solved using a greedy algorithm.
 Divide and conquer Greedy Algorithm
Divide and conquer is used to find the solution, it A greedy algorithm is optimization technique. It tries to
does not aim for the optimal solution. find an optimal solution from the set of feasible solutions

DC approach divides the problem into small sub- In greedy approach, the optimal solution is obtained
problems, each sub-problem is solved independently from a set of feasible solutions.
and solutions of the smaller problems are combined
to find the solution to the large problem.

Sub problems are independent, so DC might solve Greedy algorithm does not consider the previously solved
same sub problem multiple time. instance thus it avoids the re-computation.

DC approach is recursive in nature, so it is slower and Greedy algorithms are iterative in nature and hence
inefficient. faster.

Divide and conquer algorithms mostly runs in Greedy algorithms also run in polynomial time but takes
polynomial time less time than Divide and conquer

Example: Example:
Merge sort, Knapsack problem,
Quick sort Job scheduling problem 12
 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Job sequencing with deadlines

Greedy Method
 Introduction

You 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?”
 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-1: Sort all the given jobs in decreasing order of their profit.

Step-2: Check the value of maximum deadline.

Draw a Gantt chart where maximum time on Gantt chart is the value of
maximum deadline.

Step-3: 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
Step-1: Sort all the given jobs in decreasing order of their profit
Step-2: Value of maximum deadline = 5.

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-3: We take job J4. Since its deadline is 2, so we place it in the first empty cell
before deadline 2 as

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

Step-6: 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-7: Now, we take job J5. Since its deadline is 4, so we place it in the first
empty cell before deadline 4 as-

The only job left is job J6 whose deadline is 2. All the slots before deadline 2 are
already occupied. Thus, job J6 cannot 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
 Job Sequencing with Deadlines
We are given a set of n jobs.
Deadline di >= 0 and a profit pi >0 are associated with each job i.
For any job profit is earned if and only if the job is completed by its deadline.
To complete a job, a job has to be processed by a machine for one unit of time.
Only one machine is available for processing jobs.
A feasible solution to this problem is a subset of jobs such that each job in this
subset can be completed by its deadline
The value of feasible solution J is the sum of the profits of the jobs in J , or
The optimal solution is a feasible solution that will maximize the total profit.
The objective is to find an order of processing of jobs that will maximize the total
profit.
Example 1: n = 4, (p1, p2, p3, p4) = (100,10,15,27)
(d1, d2, d3, d4) = (2, 1, 2, 1)
The maximum deadline
Feasible is 2 units, hence
solution the feasible
Processing solution set must have <=2
sequence jobs.
value
1 (1,2) 2,1 110
2 (1,3) 1,3 or 3, 1 115
3 (1,4) 4, 1 127
4 (2,3) 2, 3 25
5 (3,4) 4,3 42
6 (1) 1 100
7 (2) 2 10
8 (3) 3 15
9 (4) 4 27
Solution 3 is optimal.
Example 2:
Let n =5 , (P1,P2,P3,P4,P5)= (20,15,10,5,1) and (d1,d2,d3,d4,d5) = (2,2,1,3,3).

Solution:
J Assigned Jobs Considered Action Profit
Slots
Ø None

The optimal solution is J = {1,2,4} with a profit of 40.

Example 3:
Let n =7 , (P1,P2,P3,P4,P5 ,P6,P7)= (3,5,20,18,1,6,30) and
(d1,d2,d3,d4,d5,d6,d7) = (1,3,4,3,2,1,2).

J Assigned Jobs Considered Action Profit

Solution: Slots
Ø None

The optimal solution is J = { } with a profit of .

High level description of jobs sequencing algorithm :

Algorithm GreedyJob(d, j, n)
// J is a set of jobs that their deadlines can complete
{
j : = {1};
for i := 2 to n do
{
if (all jobs in J U {i} can be completed by their deadlines) then
j := j U {i};
}
}
Algorithm JS(d, j, n)
// d[i] ≥ 1, 1 ≤ i ≤ n are the deadlines, n ≥ 1.
// The jobs are ordered such that p[1] ≥ p[2] …… ≥ p[n]
// j[i] is the ith job in the optimal solution, 1 ≤ i ≤ k , at
//termination d [ j[i]] ≤ d[j[i+1]], 1 ≤ i ≤ k
{
d[0] := j[0] := 0; // Initialize
j[1] := 1; // Include job 1
k := 1;
 for i := 2 to n do
{ //Consider jobs in Descending order of p[i].
// Find position for i and check feasibility of insertion.
r := k;
while( ( d[ j[r]]> d[i] and ( d[j[r]] ≠ r )) do
r := r - 1;
if( d[i] > r )) then
{
// Insert i into j[].
for q = k to (r+1) step -1 do j[q+1] = j[q];
j[r+1] := i;
k:=k+1;
}
}
return k;
}
Time taken by this algorithm is o(n2)
 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Knapsack Problem

Greedy
GreedyMethod
Method
 Knapsack
KnapsackProblem
Problem
• The knapsack problem or rucksack problem , problem Given a set of items, each with a
weight and a value, determine the number of each item to include in a collection so
that the total weight is less than or equal to a given limit and the total value is as large
as possible.
• We are give n objects and a knapsack or bag .

• Object i has a weight wi and the knapsack has a capacity m.

• If a 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 obtain a filling of the knapsack that Maximizes the total profit
earned.
Knapsack Problem Variants: Knapsack problem has the following two
variants
1. 0/1 Knapsack Problem
➢ Items are indivisible i.e. we can not take a fraction of any item.
➢ We have to either take an item completely or leave it completely.
➢ It is solved using a dynamic programming approach.

2. Fractional Knapsack Problem

➢ Items are divisible here.
➢ We can even put a fraction of any item in the knapsack if taking the complete item is
impossible.
➢ It is solved using the Greedy Approach.
Steps for Fractional Knapsack Problem Using Greedy Method:

Step-01: For each item, compute its value/weight ratio.

Step-02: Arrange all the items in the decreasing order of their value/weight
ratios.
Step-03: Start putting the items in the Knapsack beginning with the item with the
highest ratio. Put as many items as you can in the Knapsack
Solution:1 Objects Profit (pi) Weight (wi)
A 25 18
Objects are arranged in increasing order of B 24 15
weights : x1,x2,x3 C 15 10
Maximum Weight that Knapsack can hold (m) =
20

Selection Vector (x1,x2,x3) : (1,2/15,0)

∑ wixi = ( 1*18+ 2/15*15+0*10) = (18+2+0) = 20

Profit = ∑ pixi = (1 *25+ 2/15 *24+0*15) = (25+3.2+0) = 28.2

Objects are arranged in decreasing order of weights: C, B, A
Objects Profit (pi) Weight (wi)
C 15 10
B 24 15
A 25 18
Maximum Weight that Knapsack can hold (m) = 20

Selection Vector (x1,x2,x3) : (0,2/3,1)

∑ wixi = ( 0*18+ 2/3*15+1*10) = (0+10+10) = 20

Profit = ∑ pixi = (0 *25+ 2/3 *24+1*15) = (0+16+15) = 31

 Solution:
Solution:Increasing
Increasingorder
orderofofprofit
profitper
perweights
weights
Objects are arranged in increasing order of pi/wi
: B, C, A Objects Profit (pi) Weight (wi) Pi / wi
B 24 15 1.6
C 15 10 1.5
A 25 18 1.4
Maximum Weight that Knapsack can hold (m) = 20
Selection Vector (x1,x2,x3) : (0,1,1/2)

∑ wixi = ( 0*18+ 1*15+1/2*10) = (0+15+5) = 20

∑ pixi = (0 *25+ 1 *24+1/2*15) = (0+24+7.5) = 31.5

Conclusion
Profit using Solution :1 is 28.2
Profit using Solution :2 is 31
Profit using Solution :3 is 31.5
The Optimal Solution is Solution :3
2: Example
Example11

Consider the following instance of the knapsack problem

n= 7, m=15,(p1,p2,p3 ,p4,p5,p6,p7) = (5, 10, 15, 7, 8, 9, 4) and
(w1,w2,w3, w4,w5,w6,w7) = (1, 3, 5, 4, 1, 3,2)
 Example
Example22
2:
Consider the following instance of the knapsack problem
n= 7, m=15,(p1,p2,p3 ,p4,p5,p6,p7) = (10, 5, 15, 7, 6, 18, 3) and
(w1,w2,w3, w4,w5,w6,w7) = (2, 3, 5, 7, 1, 4, 1)
 Example
Example33

Consider the following instance of the knapsack problem

n= 3, m=20,(p1,p2,p3) = (30, 40, 35) and (w1,w2,w3) = (20, 25, 10)
Objects = {A, B, C} Maximum Weight that Knapsack can hold (m) = 40
 Greedy algorithm for the fractional Knapsack problem

Algorithm GreedyKnapsack(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;
for i := 1 to n do
{
if ( w[i] > U ) then break;
if x[i] := 1; U := U - w[i];
}
if ( i <= n) then x[i] := U/w[i];
}
 Time
TimeComplexity
Complexity

• The main time-consuming step is sorting all items in the decreasing order of their
value/weight ratios.

• If the items are already arranged in the required order, the while loop takes O(n)
time.

• The time complexity of the fractional knapsack problem is O(NlogN).

 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Spanning Trees -MST

Greedy Method
 Spanning Tree

• Graph: Set of Vertices and edges G: { V,E }D

• A tree is a connected undirected graph that contains no cycles.
• i.e Tree : Tree is Graph T: { V,E}
 Acyclic
 N nodes
 N-1 edges
• Note: Every Tree is a Graph , But Every Graph is not a Tree
 Properties

• A connected graph G can have more than one spanning tree.

• All possible spanning trees of graph G, have the same number of edges and
vertices.

• The spanning tree does not have any cycle (loops).

• Removing one edge from the spanning tree will make the graph disconnected, i.e.
the spanning tree is minimally connected.

• Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning
tree is maximally acyclic.
Example:

1 1
A B A B A B
5 2
4 2 4 4
6

D C D C D C
3 3 3

1 1

Undirected Graph A B A B
2 2
4

D C D C
3

Some Spanning Trees

Spanning Tree : A spanning tree of G is a sub graph T that is
Includes all of the vertices in given graph and vertices-1 edges.
𝑇⊆𝐺 𝑇: {𝑉′ = 𝑉, 𝐸′ ⊆ 𝐸}
𝑉′ = 𝑉 𝐸 = |𝑉| − 1
Spanning Tree properties:
• A graph may have many spanning trees. If the Graph G: { V,E } then
the possible spanning Trees are ECV-1
• Removing one edge from the Spanning Tree Will make it as Disconnected graph
• Adding one edge to the Spanning Tree will create a cycle.
• If each edge has distinct weight then there will be only one & unique
Minimum cost Spanning Tree.
• Disconnected graph doesn’t have any Spanning Tree.
 MST

• A minimum spanning tree is the one among all the spanning trees with the
smallest total cost or A Spanning tree with minimum weight

1 1
A B A B
4
4 2 2
5

D C D C
3 3

Undirected Graph Minimum Spanning Tree

 Applications

• Computer Networks
• How to connect a set of computers using the minimum amount of wire..
• Civil Network Planning
• Computer Network Routing Protocol
• Cluster Analysis
 Kruskal’s Algorithm

• Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum

spanning tree for a connected weighted graph.
• This algorithm treats every node as an independent tree and connects one with
another only if it has the lowest cost compared to all other options available.
• Steps to Kruskal’s algorithm:
 Sort the graph edges with respect to their weights.
 Start adding edges to the minimum spanning tree from the edge with the
smallest weight until the edge of the largest weight.
 Only add edges which don’t form a cycle—edges which connect only
disconnected components.
Kruskal’s Algorithm:
MST KRUSKAL(G, w)
T← Ø
cost← 0
for each vertex v V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) E, taken in nondecreasing order by weight
do if FIND-SET(u) ≠ FIND-SET(v)
then T.E← T.E ∪ {(u, v)}
UNION(u, v)
cost ← cost+ cost(u,v)
return cost
 Example

8 7
2 3 4
1 9
2
1 11 9 4 14 5


8

7 16
10
8 7 2
6
4

2 3 4

1 9 5

8 7 6
 Time Complexity

• With an efficient Find-set and union algorithms, the running time of kruskal’s
algorithm will be dominated by the time needed for sorting the edge costs of
a given graph.

• Hence, with an efficient sorting algorithm( merge sort ), the complexity of

kruskal’s algorithm is O( ElogE).
 Prim’s Algorithm

• Prim’s Algorithm is another greedy algorithm used for finding the Minimum Spanning
Tree (MST) of a given graph.
• The graph must be weighted, connected and undirected
• Start with minimum cost edge.
• For rest of the procedure, always select a minimum cost edge from graph make sure
that already connected to the selected vertices.
• Continue this process until the tree has n - 1 edges.
Differences
 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Single Source Shortest Path

Greedy
GreedyMethod
Method
 Shortest
ShortestPath
PathProblem
Problem
• Shortest path problem is a problem of finding the shortest path(s) between
vertices of a given graph.
• Shortest path between two vertices is a path that has the least cost as
compared to all other existing paths.
Applications-
• Google Maps
• Road Networks
• Logistics Research
Types
Typesof
ofShortest
ShortestPath
Path
 Shortest
ShortestPath
Path

• It is a shortest path problem where the shortest path from a given

source vertex to all other remaining vertices is computed.
• Dijkstra’s Algorithm and Bellman-Ford Algorithm are famous
algorithms for solving single-source shortest path problems.
 Dijkstra
DijkstraAlgorithm
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.
• Dijkstra algorithm works only for connected graphs.
• Dijkstra algorithm works only for those graphs that do not contain
any negative weight edge.
• The actual Dijkstra algorithm does not output the shortest paths. It
only provides the value or cost of the shortest paths.
• Dijkstra algorithm works for directed as well as undirected graphs.
 Implementation
Implementation

Step-01:
In the first step. two sets are defined-
•One set contains all those vertices included in the shortest path tree.
In the beginning, this set is empty.
•Another set contains all those vertices left to be included in the
shortest path tree.
In the beginning, this set contains all the vertices of the given graph.
Step-02:
For each vertex of the given graph, two variables are defined as
•Π[v] which denotes the predecessor of vertex ‘v’
•d[v] which denotes the shortest path estimate of vertex ‘v’ from the
source vertex.
Initially, the value of these variables is set as
•The value of variable ‘Π’ for each vertex is set to NIL i.e. Π[v] = NIL
•The value of variable ‘d’ for source vertex is set to 0 i.e. d[S] = 0
•The value of variable ‘d’ for remaining vertices is set to ∞ i.e. d[v] =
∞
Step-03:
The following procedure is repeated until all the vertices of the graph
are processed-
•Among unprocessed vertices, a vertex with a minimum value of
variable ‘d’ is chosen.
•Its outgoing edges are relaxed.
•After relaxing the edges for that vertex, the sets created in step-01
are updated.
 Edge
Edgerelaxation
relaxation

• Consider the edge (a,b) in the following graph-

• Here, d[a] and d[b] denotes the shortest path estimate for vertices a
and b respectively from the source vertex ‘S’.
• Now, If d[a] + w < d[b]
then d[b] = d[a] + w and Π[b] = a
• This is called as edge relaxation.
 Time
Timecomplexity
complexity

• The given graph G is represented as an adjacency matrix.

• Priority queue Q is represented as an unordered list.
Here,
• A[i,j] stores the information about edge (i,j).
• Time taken for selecting i with the smallest dist is O(V).
• For each neighbor of i, time taken for updating dist[j] is O(1) and
there will be a maximum V neighbors.
• Time taken for each iteration of the loop is O(V) and one vertex is
deleted from Q.
• Thus, total time complexity becomes O(V2).
 Example
Example

• Using Dijkstra’s Algorithm, find the shortest distance from source

vertex ‘S’ to remaining vertices in the following graph-
 Solution
Solution

Step-01:
The following two sets are created
•Unvisited set : {S , a , b , c , d , e}
•Visited set : { }
Step-02:
The two variables Π and d are created for each vertex and initialized as
•Π[S] = Π[a] = Π[b] = Π[c] = Π[d] = Π[e] = NIL
•d[S] = 0
•d[a] = d[b] = d[c] = d[d] = d[e] = ∞
Step-03:
•Vertex ‘S’ is chosen.
•This is because shortest path estimate for vertex ‘S’ is least.
•The outgoing edges of vertex ‘S’ are relaxed.
Before Edge Relaxation
Now,
•d[S] + 1 = 0 + 1 = 1 < ∞
∴ d[a] = 1 and Π[a] = S
•d[S] + 5 = 0 + 5 = 5 < ∞
∴ d[b] = 5 and Π[b] = S
• After edge relaxation, our shortest path tree is

Now, the sets are updated as

• Unvisited set : {a , b , c , d , e}
• Visited set : {S}
Step-04:
•Vertex ‘a’ is chosen.
•This is because the shortest path estimate for vertex ‘a’ is the least.
•The outgoing edges of vertex ‘a’ are relaxed.
Before Edge Relaxation
• d[a] + 2 = 1 + 2 = 3 < ∞ ∴ d[c] = 3 and Π[c] = a
• d[a] + 1 = 1 + 1 = 2 < ∞ ∴ d[d] = 2 and Π[d] = a
• d[b] + 2 = 1 + 2 = 3 < 5 ∴ d[b] = 3 and Π[b] = a
After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

• Unvisited set : {b , c , d , e}
• Visited set : {S , a}
Step-05:
•Vertex ‘d’ is chosen.
•This is because shortest path estimate for vertex ‘d’ is least.
•The outgoing edges of vertex ‘d’ are relaxed.
Before Edge Relaxation
Now,
•d[d] + 2 = 2 + 2 = 4 < ∞
∴ d[e] = 4 and Π[e] = d
After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

•Unvisited set : {b , c , e}
•Visited set : {S , a , d}
Step-06:
•Vertex ‘b’ is chosen.
•This is because shortest path estimate for vertex ‘b’ is least.
•Vertex ‘c’ may also be chosen since for both the vertices, shortest
path estimate is least.
•The outgoing edges of vertex ‘b’ are relaxed.
Before Edge Relaxation-
Now, d[b] + 2 = 3 + 2 = 5 > 2
∴ No change
 Single
SingleSource
SourceShortest
ShortestPath
Path

• Given a positively weighted directed graph G with a source vertex 1,

find the shortest paths from V1 to all other vertices in the graph.

v V1 V2 V5
V1 V 3
V 1 V3 V 4
V 1 V 3 V4 V 2
V1 V 5
V3 V4 V6 5) V 1V3 V 4V6 28
After edge relaxation, our shortest path tree remains the same as in
Step-05.
Now, the sets are updated as-
•Unvisited set : {c , e}
•Visited set : {S , a , d , b}
Step-07:
•Vertex ‘c’ is chosen.
•This is because shortest path estimate for vertex ‘c’ is least.
•The outgoing edges of vertex ‘c’ are relaxed.
Before Edge Relaxation-
Now,
•d[c] + 1 = 3 + 1 = 4 = 4
•∴ No change
 SSSP
SSSPDijkstra’s
Dijkstra’salgorithm
algorithm

• Dijkstra’s algorithm assumes that cost(e)0 for each e in the

graph.
• Maintains a set S of vertices whose SP from v ( source) has been
determined.
• a) Select the next minimum distance node u, which is not in S.
• b) for each node w adjacent to u do
if( dist[w]>dist[u]+cost[u,w]) ) then
dist[w]:=dist[u]+cost[u,w];

• Repeat step (a) and (b) until S=n (number of vertices).

After edge relaxation, our shortest path tree remains the same as in
Step-05.
•Now, the sets are updated as-
•Unvisited set : {e}
•Visited set : {S , a , d , b , c}
Step-08:
•Vertex ‘e’ is chosen.
•This is because shortest path estimate for vertex ‘e’ is least.
•The outgoing edges of vertex ‘e’ are relaxed.
•There are no outgoing edges for vertex ‘e’.
•So, our shortest path tree remains the same as in Step-05.
Now, the sets are updated as-
•Unvisited set : { }
•Visited set : {S , a , d , b , c , e}
Now,
•All vertices of the graph are processed.
•Our final shortest path tree is as shown below.
•It represents the shortest path from source vertex ‘S’ to all other remaining
vertices.

•The order in which all the vertices are processed is : S , a , d , b , c , e.

 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Huffman Coding

Greedy
GreedyMethod
Method
 Encoding
Encodingand
andCompression
Compressionof
ofData
Data

• Compression:
• Data Compression, shrinks down a String so that it takes up less space.
This is desirable for data storage and data communication.
• Encoding means converting the String into Binary codes
• Decompression:
In the decompression we convert the Binary codes into the Original string.
 Fixed
Fixedand
andVariable
VariableLength
LengthCode
Code

• Fixed length code:

If every word in the code has the same length, the code is called a fixed-length
code, or a block code.

Advantage Disadvantage
Access is fast because the Using Fixed length records, the records
computer knows where each are usually larger and therefore need
Word starts more storage space and are slower to
transfer
 Fixed
Fixedand
andVariable
VariableLength
LengthCode
Code

• Variable length code:

Variable-length codes can perform significantly better as frequent characters are
given short code words, while infrequent characters get longer code words.

Advantage Disadvantages
Variable-length codes over fixed Where a character ends
length is short codes that can be and another begins,
given to characters that occur difficult to identify.
frequently.
 Prefix
PrefixProperty
Property
• A code has the prefix property, code assigned to one character is not the prefix
of code assigned to any other character.
• Example:

Symbol Code 01001101100010

P 000 R S T Q P T
Q 11 000 is not a prefix of 11, 01, 001, or 10
R 01 11 is not a prefix of 000, 01, 001, or 10 ….
S 001
T 10
 Huffman
HuffmanCoding
Coding
• Developed by David Huffman in 1951
• Huffman Coding is a famous Greedy Algorithm.
• It is used for the lossless compression of data.
• It uses variable length encoding.
• It assigns variable length code to all the characters.
• The code length of a character depends on how frequently it occurs in the given
text.
• The character which occurs most frequently gets the smallest code.
• The character which occurs least frequently gets the largest code.
• It is also known as Huffman Encoding.
• Huffman Coding implements a rule known as a prefix rule.
• This is to prevent the ambiguities while decoding.
 Major
Majorsteps
stepsin
inHuffman
HuffmanCoding
Coding

There are two major steps in Huffman Coding-

[Link] a Huffman Tree from the input characters.
[Link] code to the characters by traversing the Huffman Tree.
 Huffman
HuffmanTree
Tree

The steps involved in the construction of Huffman Tree are as follows-

Step-01:
•Create a leaf node for each character of the text.
•Leaf node of a character contains the occurring frequency of that
character
Step-02:
•Arrange all the nodes in increasing order of their frequency value.
Step-03:
•Considering the first two nodes having minimum frequency
•Create a new internal node.
•The frequency of this new node is the sum of frequency of those two nodes.
•Make the first node as a left child and the other node as a right child of the
newly created node.

Step-04:
•Keep repeating Step-02 and Step-03 until all the nodes form a single tree.
•The tree finally obtained is the desired Huffman Tree.
 Sample
Sample
Message: aabacb
 Formulae
Formulae
The following 2 formulas are important to solve the problems based on Huffman
Coding-
Formula-01:

Formula-02:
•Total number of bits in Huffman encoded message
= Total number of characters in the message x Average code length per character
= ∑ ( frequencyi x Code lengthi )
 Example
Example

Problem-
A file contains the following characters with the frequencies as
shown. If Huffman Coding is used for data compression,
determine-
[Link] Code for each character
[Link] code length
[Link] of Huffman encoded message (in bits)
First let us construct the Huffman Tree.
•Huffman Tree is constructed in the following steps-
Step-01:

Step-02:
Step-03:
Step-04:
Step-05:
Step-06:
Step-07:
Now,
•We assign weight to all the edges of the constructed Huffman Tree.
•Let us assign weight ‘0’ to the left edges and weight ‘1’ to the right edges

Rule
•If you assign weight ‘0’ to the left edges, then assign weight ‘1’ to the right edges.
•If you assign weight ‘1’ to the left edges, then assign weight ‘0’ to the right edges.
•Any of the above two conventions may be followed.
•But follow the same convention at the time of decoding that is adopted at the time
of encoding.
Huffman Code fo each Character

To write Huffman Code for any character, traverse the Huffman Tree from root
node to the leaf node of that character.
Following this rule, the Huffman Code for each character is-
•a = 111
From here, we can observe-
•e = 10 •Characters occurring less frequently in the text are assigned the
•i = 00 larger code.
•o = 11001 •Characters occurring more frequently in the text are assigned
the smaller code.
•u = 1101
•s = 01
•t = 11000
Average Code Length
Using formula-01
Average code length
= ∑ ( frequencyi x code lengthi ) / ∑ ( frequencyi )
= { (10 x 3) + (15 x 2) + (12 x 2) + (3 x 5) + (4 x 4) + (13 x 2) + (1 x 5) } / (10 +
15 + 12 + 3 + 4 + 13 + 1)
= 2.52
Length of Huffman Encoded Message

Using formula-02
Total number of bits in Huffman encoded message
= Total number of characters in the message x Average code length per
character
= 58 x 2.52
= 146.16
≅ 147 bits
 Applications
Applications
• Huffman coding is a technique used to compress files for transmission
• Uses statistical coding
• more frequently used symbols have shorter code words
• Works well for text and fax transmissions
• An application that uses several data structures
 Home
HomeWork
Work
Suppose a data file has the following characters and the frequencies. If huffman coding
is used, calculate:
•Huffman Code of each character
•Average code length Characters Frequencies
•Length of Huffman encoded data
A 12

B 15

C 7

D 13

E 9
 Home
HomeWork
Work
Suppose a data file has the following characters and the frequencies. If huffman coding
is used, calculate:
•Huffman Code of each character
•Average code length
•Length of Huffman encoded data

Letter Z K M C U D L E
Frequency 2 7 24 32 37 42 42 120
 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Divide and Conquer

Merge Sort
 Merge Sort

• Merge Sort is a Divide and Conquer algorithm.

• It divides input array in two halves, calls itself for the two halves and then merges the two
sorted halves.
• The merge() function is used for merging two halves.
• The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted
and merges the two sorted sub-arrays into one.

Best case O(nlogn)

Average case O(nlogn)
Worst case O(nlogn)
Memory n
Stable YES
Inplace NO
 Algorithm

Algorithm D and C(P)

{
if small(P)
then return S(P)
else
{
divide P into smaller instances P1 ,P2 .....Pk
apply D and C to each sub problem
return combine (D and C(P1)+ D and C(P2)+.......+D and C(Pk))
}
}
 EXAMPLE
i=start; k=0; j=mid+1
start end
0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]<=arr[j] then temp[k]=arr[i], k++, i++

0 1 2 3 4 5 6 7 8
temp 2

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]>arr[j] then temp[k]=arr[j], k++, j++

0 1 2 3 4 5 6 7 8
temp 2 3

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]<=arr[j] then temp[k]=arr[i], k++, i++

0 1 2 3 4 5 6 7 8
temp 2 3 4

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]>arr[j] then temp[k]=arr[j], k++, j++

0 1 2 3 4 5 6 7 8
temp 2 3 4 5

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]<=arr[j] then temp[k]=arr[i], k++, i++

0 1 2 3 4 5 6 7 8
temp 2 3 4 5 6

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]>arr[j] then temp[k]=arr[j], k++, j++

0 1 2 3 4 5 6 7 8
temp 2 3 4 5 6 7

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

i m j

If arr[i]<=arr[j] then temp[k]=arr[i], k++, i++

0 1 2 3 4 5 6 7 8
temp 2 3 4 5 6 7 8

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

mi j

If arr[i]<=arr[j] then temp[k]=arr[i], k++, i++

0 1 2 3 4 5 6 7 8
temp 2 3 4 5 6 7 8 9

k
 0 1 2 3 4 5 6 7 8
arr 2 4 6 8 9 3 5 7 10

m i j

As i>mid; loop breaks. Check j<=end. If not, temp[k]=arr[j], k++, j++

0 1 2 3 4 5 6 7 8
temp 2 3 4 5 6 7 8 9 10

k
The final sorted list
 Algorithm

Algorithm MergeSort ( low, high)

// a[low: high] is a global array to be sorted.
// Small(P) is true if there is only one element to sort. In this case
the list is already sorted.
{ if ( low<high ) then // if there are more than one element
{ //solve the sub problems.
Recursive Calls
// Divide P into sub problems. MergeSort(low,mid);
// Find where to split the set. MergeSort(mid+1, high);
mid := [(low+high)/2]; // Combine the solutions.
Merge(low, mid, high);
}
}
Time Complexity
 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Divide and Conquer

Quick
QuickSort
Sort
 Quick sort
Quick sort
• Quick Sort is a Divide and Conquer algorithm.
• It picks an element as pivot and partitions the given array around the picked pivot.
• There are many different versions of quick sort that pick pivot in different ways.
• Always pick first element as pivot.
• Always pick last element as pivot
• Pick a random element as pivot.
• Pick median as pivot.
Best case O(nlogn)
Average case O(nlogn)
Worst case O(n^2)
Memory Average: logn
Worst: n
Stable NO
Inplace Yes
 Quick sort algorithm
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index -1
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
 EXAMPLE
List partition
5 3 8 1 4 6 2 7

P L R
5 3 8 1 4 6 2 7

P L R

5 3 8 1 4 6 2 7

P L R

5 3 8 1 4 6 2 7

P L SWAP ARR[L] = ARR[R] R

5 3 2 1 4 6 8 7

P L R
5 3 2 1 4 6 8 7

P L R

5 3 2 1 4 6 8 7

P L R

5 3 2 1 4 6 8 7

P L R
 5 3 2 1 4 6 8 7

P LR
5 3 2 1 4 6 8 7

R crossed L
P SWAP ARR[R] = ARR[P]
R L

4 3 2 1 5 6 8 7

P L R P L R

The same steps are repeated on the

left and right parts of the list.
 Time complexity

• Best case: The pivot chosen always divides the array into two equal halves.

• Average case: The pivot divides the array into two subarrays that are not necessarily
equal but reasonably balanced.

• Worst case: The pivot chosen is always the smallest or largest element, leading to highly
unbalanced partitions.
Best case
Average case
Worst case
 Examples

1. Sort the following elements using Quick sort technique using first element as
pivot: 54, 26, 93, 17, 77, 31, 44, 55, 20

2. Sort the following elements using Quick sort technique using last element as
pivot: 10, 80, 30, 90, 40, 50, 70, 60

3. 8,7,1,2,6,9,10,2,11 sort using the last element as pivot.

 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

24CS2203
Topic:

Divide and Conquer

Strassen’s
Strassen’sMatrix
MatrixMultiplication
Multiplication
 Matrix
MatrixMultiplication
Multiplication

Algorithm: Matrix-Multiplication (X, Y, Z)

for i = 1 to p do
for j = 1 to r do
Z[i,j] := 0
for k = 1 to q do
Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]
 Need
Needof
ofthe
theStrassen’s
Strassen’smatrix
matrixmultiplication
multiplication

Strassen’s matrix multiplication follows Divide and Conquer Strategy.

By using the Strassen’s Matrix multiplication algorithm, the time consumption
can be improved a little bit when compared to the basic matrix multiplication.

Strassen’s Matrix multiplication can be performed only on square

matrices where n is a power of 2. Order of both of the matrices are n × n.
Divide
Divideand
andConquer
ConquerTechnique
Technique
 A11 A12 B11 B12

c11 c12 1 1 2 2  5 5 6 6
Then,  C11 C12   1 1 2 2  5 5 6 6
C   
C11=A11B11+A12B21 C 21 C 22 3 3 4 4  7 7 8 8
c21 c22 3 3 4 4 7 7 8 8 
C12=A11B12+A12B22 A21 A 22B 21 B 22

C21=A21B11+A22B21
C22=A21B12+A22B22
 Each of these four equations specifies two multiplications of n/2×n/2 matrices and the
addition of their n/2×n/2 products.
 We can derive the following recurrence relation:

T(n)= 1 if n=1
8T(n/2)+ 4n2 if n>1
Master
MasterTheorem
Theorem
 Strassen’s
Strassen’smethod
method

 Matrix multiplications are more expensive than matrix additions or subtractions

( O(n3) versus O(n2)).

 Strassen’s has discovered a way to compute the multiplication using only 7

multiplications and 18 additions or subtractions.
Strassen’s
Strassen’sFormulae
Formulae

T(n)= 1 if n=1
7T(n/2)+ 18n2 if n>1
 Conclusion
Conclusion
• The number 2.81 may not seem much smaller than 3, but because the difference is
in the exponent, the impact on running time is significant.
• In fact, Strassen’s algorithm beats the ordinary algorithm on today’s machines.

Mult Add Recurrence Relation Runtime

Regular 8 4 T(n) = 8T(n/2) + O(n2) O(n3) 

Strassen‘s 7 18 T(n) = 7T(n/2) + O(n2) O(n log27) = O(n2.81)

Time
Timecomplexity
complexity
Example
Example
Department of CSE

DESIGN AND ANALYSIS OF

ALGORITHMS
24CS2203
Topic:

Divide and Conquer

Convex Hull
 Convex vs Concave

• A polygon P is convex if, for every pair of points x and y in P, the line xy
is also in P; otherwise, it is called concave.

x
P y x
P y

concave convex
 Convex Hull Problem

concave polygon: convex polygon:

 Divide & Conquer

Steps:
1. Sort the Points:
1. Sort the given points based on their x-coordinates (if x-coordinates are the same, use y-
coordinates).
2. Sorting takes O(nlog⁡n)
2. Divide the Points:
1. Split the sorted points into two halves (left and right).
3. Recursive Hull Computation:
1. Recursively find the convex hulls for both halves.
4. Merge the Hulls:
1. Find the upper and lower tangents to combine the two convex hulls.
2. Remove the points that are not part of the final convex hull.
 Divide & Conquer

• Merge Step (Key Challenge)

Merging two convex hulls involves:
1. Finding the Upper Tangent:
1. Start from the rightmost point of the left hull and the leftmost point of the right hull.
2. Move counterclockwise on the left hull and clockwise on the right hull until the
tangent is found.
2. Finding the Lower Tangent:
1. Similar to the upper tangent but in the opposite directions.
3. Combine the hulls by removing the interior points.
The first step is to find out the farthest two points in the plane:
Then, in the two spaces S1 and S2, we will find out the farthest point:
We will continue to perform operations.
Finally, Our resultant polygon would look something like this:
 Time complexity

•
Ex: Draw the convex hull for the following points

(1,1),(2,3),(3,5),(5,3),(3,2),(2,2),(6,1),(7,4)

(0, 0), (0, 4), (-4, 0), (5, 0), (0, -6), (1, 0)
 Department of CSE

DESIGN AND ANALYSIS OF ALGORITHMS

23CS2205R
Topic:

Time Complexity

Time Complexity
Recurrence Relations
Substitution Method
Example
Master Theorem
Examples
 Types of recursive calls

Linear Recursion:
Example: T(n) = T(n-1) + O(1)
Time Complexity: O(n)

Divide and Conquer:

Example: T(n) = 2T(n/2) + O(1)
Time Complexity: O(n log n)

Multiple Recursive Calls with Constant Subtraction:

Example: T(n) = T(n-1) + T(n-2) + O(1)
Time Complexity: O(2^n)

Logarithmic Reduction:
Example: T(n) = T(n/2) + O(1)
Time Complexity: O(log n)