Greedy Method: The general method

Unit II
Presented By – Amrapali Babar
 What is Greedy Algorithm?

• A greedy algorithm is a problem-solving technique that makes the best

local choice at each step in the hope of finding the global optimum
solution.
• Characteristics of Greedy Algorithm
• Greedy algorithms are simple and easy to implement.
• They are efficient in terms of time complexity, often providing quick
solutions.
• Greedy algorithms are used for optimization problems where a locally
optimal choice leads to a globally optimal solution.
• These algorithms do not reconsider previous choices, as they make
decisions based on current information without looking ahead.
 Optimization Problem
• An optimization problem is the one in which you want to find, not a just
solution, but the best solution.
• Optimization Problem –
Problem with an objective function to either
• Maximize Profit
• Minimize Some Cost

• Optimization Problems Appear in Different Applications:

1) Maximize the number of jobs using a resource
2) Collect the maximum value of goods that fir in a given bucket [knapsack
Problem]
3) Select the smallest weight of edges to connect all nodes in a graph[Minimum
spanning tree]
Greedy Algorithms
• Main Concept –

- Divide the problem into multiple steps (Sub problems)

- For each step take the best choice at the current moment. (Local
Optimal) (Greedy Choice)
- A Greedy Algorithm always makes the choice that looks best at the
moment.
- A locally optimal choice will lead to a globally optimal choice. For
some problems it works. For others it does not.
Graph Coloring Problem

• Graph Coloring is a process of assigning colors to the vertices of a

graph.
• It ensures that no two adjacent vertices of the graph are colored with
the same color.
• Chromatic Number is the minimum number of colors required to
properly color any graph.
Graph Coloring: -
• Definition: A graph has been colored if a color has been assigned to
each vertex in such a way that adjacent vertices have different colors.

• Definition: The chromatic number of a graph is the smallest number

of colors with which it can be colored.
 What is Backtracking?
• Backtracking is a problem-solving algorithmic technique that involves
finding a solution incrementally by trying different
options and undoing them if they lead to a dead end.
• It is commonly used in situations where you need to explore multiple
possibilities to solve a problem.
• Backtracking can be defined as a general algorithmic technique that
considers searching every possible combination in order to solve a
computational problem.
• Why We Use Backtracking – When you want multiple solutions and there
is different possible solutions go for backtracking.
M coloring Decision Problem
Continued..
• A space state tree is a tree that represents all of the possible states of
the problem, from the root as an initial state to the leaf as a terminal
state.
 Knapsack problem
• The Knapsack problem is an example of the combinational optimization
problem. This problem is also commonly known as the “Rucksack
Problem“.
• Given a bag with maximum weight capacity of W and a set of items,
each having a weight and a value associated with it.
• Decide the number of each item to take in a collection such that the
total weight is less than the capacity and the total value is maximized.
Types of Knapsack Problem:
• The knapsack problem can be classified into the following types:
• Fractional Knapsack Problem
• 0/1 Knapsack Problem
• Bounded Knapsack Problem
• Unbounded Knapsack Problem
 Fractional Knapsack Problem using Greedy Algorithm -
• The basic idea of the greedy approach is to calculate the
ratio profit/weight for each item and sort the item on the basis of this
ratio. Then take the item with the highest ratio and add them as much as
we can (can be the whole element or a fraction of it).
• This will always give the maximum profit because, in each step it adds an
element such that this is the maximum possible profit for that much
weight.
Example - Given the weights and profits of N items, in the form
of {profit, weight} put these items in a knapsack of capacity W to get the
maximum total profit in the knapsack. In Fractional Knapsack, we can break
items for maximizing the total value of the knapsack.
Algorithm For Fractional Knapsack Problem
• Calculate the ratio (profit/weight) for each item.
• Sort all the items in decreasing order of the ratio.
• Initialize res = 0, curr_cap = given_cap.
• Do the following for every item i in the sorted order:
• If the weight of the current item is less than or equal to the remaining
capacity then add the value of that item into the result
• Else add the current item as much as we can and break out of the loop.
• Return res.
Example -
• Object 1 2 3 4 5 6 7
• Profit 10 5 15 7 6 18 3
• Weight 2 3 5 7 1 4 1
------------------------------------------------------------
5 1.3 3 1 6 4.5 3 Profit for 1 kg
1 2/3 1 0 1 1 1 considered Weights

15 Kg Select highest profit by weight

knapsack
Minimum - Cost Spanning Tree
- A minimum spanning tree (MST) is defined as a spanning
tree that has the minimum weight among all the possible
spanning trees.
- A spanning tree is defined as a tree-like sub graph of a
connected, undirected graph that includes all the vertices of the
graph.
 Properties of Spanning Tree
● The number of vertices (V) in the graph and the spanning tree is
the same.
● There is a fixed number of edges in the spanning tree which is
equal to one less than the total number of vertices ( E = V-1 ).
● The spanning tree should not be disconnected, as in there
should only be a single source of component, not more than
that.
● The spanning tree should be acyclic, which means there would
not be any cycle in the tree.
● The total cost (or weight) of the spanning tree is defined as the
sum of the edge weights of all the edges of the spanning tree.
● There can be many possible spanning trees for a graph.
Spanning Tree
Given (connected) graph G(V,E),
a spanning tree T(V’,E’):
- Is a sub graph of G;
- Spans the graph (V’ = V)
- Forms a tree (no cycle);
So, E’ has |V| -1 edges
Algorithms to find Minimum Spanning Tree:
There are several algorithms to find the minimum spanning tree from a given
graph, some of them are listed below:

1) Kruskal’s Minimum Spanning Tree Algorithm :-

This is one of the popular algorithms for finding the minimum spanning tree
from a connected, undirected graph. This is a Greedy algorithm The
algorithm workflow is as below:
● First, it sorts all the edges of the graph by their weights,
● Then starts the iterations of finding the spanning tree.
● At each iteration, the algorithm adds the next lowest-weight edge one by
one, such that the edges picked until now does not form a cycle.
 Algorithm for Kruskal’s Algorithm :
Step 1: Create a forest F in such a way that every vertex of the graph is a
separate tree.
Step 2: Create a set E that contains all the edges of the graph.
Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning
Step 4: Remove an edge from E with minimum weight
Step 5: IF the edge obtained in Step 4 connects two different trees, then
add it to the forest F (for combining two trees into one tree).
ELSE
Discard the edge
Step 6: END
Example for Kruskal’s Algorithm :
Given weighted Graph,
Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating
the cycle.
Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or
loop.

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming
the cycle.
Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the cycle,
so discard it.
Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so discard
it.
Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so
discard it.
• So, the final minimum spanning tree obtained from the given weighted graph
by using Kruskal's algorithm is –
Time Complexity for Kruskal’s Algorithm

• Time Complexity
The time complexity of Kruskal's algorithm is O(E logE) or O(V logV),
where E is the no. of edges, and V is the no. of vertices.
 2) Prim’s Minimum Spanning Tree Algorithm
This is also a greedy algorithm, the workflow is as follows :
● It starts by selecting an arbitrary vertex and then adding it to the MST.
● Then, it repeatedly checks for the minimum edge weight that connects
one vertex of MST to another vertex that is not yet in the MST.
● This process is continued until all the vertices are included in the MST.
Prim’s Algorithm :
• Step 1: Select a starting vertex
• Step 2: Repeat Steps 3 and 4 until there are fringe vertices
• Step 3: Select an edge 'e' connecting the tree vertex and fringe
vertex that has minimum weight
• Step 4: Add the selected edge and the vertex to the minimum
spanning tree T
• [END OF LOOP]
• Step 5: EXIT
Example of prim's algorithm :
Given a weighted graph,

Step 1 - First, we have to choose a vertex from the above graph. Let's
choose B.
 Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two
edges from vertex B that are B to C with weight 10 and edge B to D with weight 4. Among
the edges, the edge BD has the minimum weight. So, add it to the MST.

Step 3 - Now, again, choose the edge

with the minimum weight among all the other
edges.
In this case, the edges DE and CD are such
edges. Add them to MST and explore the
adjacent of C, i.e., E and A.
So, select the edge DE and add it to the MST.
 Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as
it would create a cycle to the graph. So, choose the edge CA and add it to
the MST.
Continued..

• The cost of the MST is given below -

• Cost of MST = 4 + 2 + 1 + 3 = 10 units.

• The time complexity of Prim's algorithm is O((V + E) log V). This is

because each edge is inserted into a priority queue only once, and
inserting into a priority queue takes logarithmic time.
Diff Between Krsuskal’s and Prim’s Algorithm
Optimal Storage On Tapes :-
Program – 3 Tape length – L L1 - L2 - L3 -

{L1 ,L2 ,L3} = {5 ,10 ,3}

Tape –
0 1 2 4 5 6 7 8 9 10

Problem – How to optimize the retrieval of programs on tape

Solution – find a permutation to store programs that minimizes MRT (Mean

Retrieval Time)
Tape –

0 1 2 4 5 6 7 8 9 10
5 10 3
Time taken to retrieve a program is proportional to
sum of the lengths of the programs based on ordering = d( i )
L1 = 5, L2 = 10 ,L3 = 3
Ordering ( i ) =1 ,2 ,3 Time Complexity – O (n log n) MRT(Mean
Ordering d( i ) Retrieval Time)

1 2 3 5 5 + 10 5 + 10 + 3 38
1 3 2 5 5+3 5 + 3 + 10 31
2 1 3 10 10 + 5 10 + 5 + 3 43
2 3 1 10 10 + 3 10 + 3 + 5 41
3 1 2 3 3+5 3 + 5 + 10 29
3 2 1 3 3 + 10 3 + 10 + 5 34
For Optimal Storage on Tape
Single source shortest paths :
• Single source shortest path problem determines the shortest paths in
a graph from a specific source node to all other nodes.
• It is foundational in various applications, impacting efficiency in
navigation, telecommunications and network analysis.
• Used extensively in GPS navigation systems for optimal route finding.
• Critical in telecommunications for determining efficient data packet
routing in networks.
• Plays a role in urban planning, helping design transportation and
utility networks.
Shortest Path
• Input: t x
6
• Directed graph G = (V, E) 3 9
3
• Weight function w : E → R 4
s 2 1
0
2 7
• Weight of path p = v0, v1, . . . , vk 5 3
k
w( p )  w( vi  1 , vi ) 5
6
11
i 1 y z

• Shortest Path = path of minimum weight

• Shortest-path weight from u to v:

p

δ(u, v) = min w(p) : u v if there exists a path from u to v

∞ otherwise

• Note: there might be multiple shortest paths from u to v

Introduction to Dijkstra's Algorithm

• Dijkstra's Algorithm is a Graph algorithm that finds the shortest

path from a source vertex to all other vertices in the Graph (single
source shortest path).
• Dijkstra's Algorithm was designed and published by Dr. Edsger W.
Dijkstra, a Dutch Computer Scientist, Software Engineer,
Programmer, Science Essayist, and Systems Scientist.
• It is a type of Greedy Algorithm that only works on Weighted Graphs
having positive weights.
• The time complexity of Dijkstra's Algorithm is O(V2) with the help of
the adjacency matrix representation of the graph.
Pseudocode for Dijkstra's Algorithm

function Dijkstra_Algorithm(Graph, source_node)

// iterating through the nodes in Graph and set their distances to INFINITY
for each node N in Graph:
distance[N] = INFINITY
previous[N] = NULL
If N != source_node, add N to Priority Queue G
// setting the distance of the source node of the Graph to 0
distance[ source_node] = 0

// iterating until the Priority Queue G is not empty

while G is NOT empty:
// selecting a node Q having the least distance and marking it as visited
Q = node in G with the least distance[]
mark Q visited
 Continued..
// iterating through the unvisited neighboring nodes of the node Q and
performing relaxation accordingly
for each unvisited neighbor node N of Q:
temporary_distance = distance[Q] + distance_between (Q, N)

// if the temporary distance is less than the given distance of the path to
the Node, updating the resultant distance with the minimum value
if temporary_distance < distance[N]
distance[N] := temporary_distance
previous[N] := Q

// returning the final list of distance

return distance[], previous[]
Basic Understanding before Algorithm Implementation

• Directed Graph
• Weighted Graph
• Visited Property
• Path Property
• Relaxation d[u] + c[u , v]<d[v]
• d[v]= d[u] + c[u , v]

2 4 ∞, 6
1 2 3
u v
Example -
• Given directed graph, starting vertex A
Thank You…