Greedy Algorithm LectueNote

CHAPTER 3:
GREEDY ALGORITHMS
Sub-topics Outlines
• Characteristics of Greedy Algorithm
• Graph Minimum Spanning Tree(MST)-Kruskal’s And Prim’s Algorithms
• Shortest Paths
• Scheduling
What is Greedy Algorithm?
A greedy algorithm is any algorithm that follows the problem-solving
heuristic of making the locally optimal choice at each stage.
greedy strategy does not produce an optimal solution, but a greedy
heuristic can yield locally optimal solutions that approximate a globally
optimal solution in a reasonable amount of time.
✓Is defined as a method for solving optimization problems by taking decisions that
result in the most evident and immediate benefit irrespective of the final outcome.
✓It works for cases where minimization or maximization leads to the required
solution.
Characteristics of Greedy algorithm
For a problem to be solved using the Greedy approach, it must follow a few major
characteristics:
▪There is an ordered list of resources(profit, cost, value, etc.)
▪Maximum of all the resources(max profit, max value, etc.) are taken.
▪For example, in the fractional knapsack problem, the maximum value/weight is
taken first according to available capacity.
For example consider the Fractional Knapsack problem
Optimal substructure property and can be solved using Greedy approach are:
1) Job sequencing Problem:
Greedily choose the jobs with maximum profit first, by sorting the jobs in decreasing
order of their profit. This would help to maximize the total profit as choosing the job
with maximum profit for every time slot will eventually maximize the total profit
2) Prim’s algorithm to find Minimum Spanning Tree:
It starts with an empty spanning tree. The idea is to maintain two sets of vertices.
The first set contains the vertices already included in the MST, the other set contains
the vertices not yet included. At every step, it considers all the edges that connect
the two sets and picks the minimum weight edge from these edges. After picking the
edge, it moves the other endpoint of the edge to the set containing MST.
What is Graph?
A Graph is a non-linear data structure consisting of vertices and edges.
The vertices are sometimes also referred to as nodes and the edges are lines or arcs
that connect any two nodes in the graph.
More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ).
The graph is denoted by G(E, V).
Components of a Graph
•Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are
also known as vertex or nodes. Every node/vertex can be labeled or unlabeled.
•Edges: Edges are drawn or used to connect two nodes of the graph. It can be
ordered pair of nodes in a directed graph. Edges can connect any two nodes in any
possible way. There are no rules. Sometimes, edges are also known as arcs. Every
edge can be labeled/unlabeled.
What is a Spanning Tree?
A Spanning tree is a subset of connected graph (G), where all the edges are
connected.
➢one can traverse to any edge from a particular edge with or without
intermediates.
➢Also, a spanning tree must not have any cycle in graph. If there are N vertices in
a connected graph then the number of edges that a spanning tree may have is N-1.
➢Minimum spanning Tree is the sum of edges weights from the source to destination
is minimum.
Maze solving problem
Graph Minimum Spanning Tree (MST)
Prim’s and Kruskal’s Algorithms
•Prim’s and Kruskal’s Algorithm are the famous greedy algorithms.
•They are used for finding the Minimum Spanning Tree (MST) of a given graph.
•To apply these algorithms, the given graph must be weighted, connected and
undirected.
If all the edge weights are distinct, then both the algorithms are guaranteed to find
the same MST.
In searching No loop /Cycle

The sum of edges is minimum
Examples:
Using Prim’s Algorithm, find the cost of minimum spanning tree (MST) of the given graph-
Solution: Step-3 Step-5
Step-1
Step-2
Step-4 Step-6
Cost of Minimum Spanning Tree

= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
Kruskal’s Algorithm-
Kruskal’s Algorithm is a famous greedy algorithm.
•It is used for finding the Minimum Spanning Tree (MST) of a given graph.
•To apply Kruskal’s algorithm, the given graph must be weighted, connected and
undirected.
•Worst case time complexity of Kruskal’s Algorithm
= O(ElogV) or O(ElogE), where E-Edge and V-Vertices
* Construct the minimum spanning tree
(MST) for the given graph using Kruskal’s
Algorithm
To construct MST using Kruskal’s Algorithm,
•Simply draw all the vertices on the paper.
•Connect these vertices using edges with minimum weights such that no cycle gets
formed.
Since all the vertices have been connected /
included in the MST, so we stop.
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
Shortest Paths:
shortest Paths in data structures,
•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.
Shortest Path Algorithms-
➢ Shortest path algorithms are a family of algorithms used for solving the shortest path
problem.
➢Shortest path algorithms have a wide range of applications such as:
• Google Maps
• Road Networks
• Logistics Research
Types of Shortest Path Problem
Single-Pair Shortest Path Problem
•It is a shortest path problem where the shortest path between a given pair of
vertices is computed.
•A* Search Algorithm is a famous algorithm used for solving single-pair shortest path
problem.
Single-Source Shortest Path Problem
•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 the famous algorithms used for
solving single-source shortest path problem.
Single-Destination Shortest Path Problem
•It is a shortest path problem where the shortest path from all the vertices to a single
destination vertex is computed.
•By reversing the direction of each edge in the graph, this problem reduces to single-
source shortest path problem.
•Dijkstra’s Algorithm is a famous algorithm adapted for solving single-destination
shortest path problem.
All Pairs Shortest Path Problem-
•It is a shortest path problem where the shortest path between every pair of vertices
is computed.
•Floyd-Warshall Algorithm and Johnson’s Algorithm are the famous algorithms used
for solving All pairs shortest path problem.
Greedy is a strategy that works well on optimization problems with the following
characteristics:
1. Greedy-choice property: A global optimum can be arrived at by selecting a local
optimum.
2. Optimal substructure: An optimal solution to the problem contains an optimal
solution to subproblems. The second property may make greedy algorithms look
like dynamic programming. However, the two techniques are quite different.
Binary Search Trees
A binary search tree is a binary tree with a special property called the BST-property,
which is given as follows: ?
For all nodes x and y, if y belongs to the left subtree of x, then the key at y is less than
the key at x, and if y belongs to the right subtree of x, then the key at y is greater than
the key at x. We will assume that the keys of a BST are pairwise distinct.
Each node has the following attributes:
➢p, left, and right, which are pointers to the parent, the left child, and the right child,
respectively, and
➢key, which is key stored at the node.
Examples
Traversal of the Nodes in a BST
By “traversal” mean visiting all the nodes in a graph.
Traversal strategies can be specified by the ordering of the three objects to visit: the
current node, the left subtree, and the right subtree. Assume the left subtree always
comes before the right subtree.
Then there are three strategies.
1. Inorder. The ordering is: the left subtree, the current node, the right subtree.
2. Preorder. The ordering is: the current node, the left subtree, the right subtree.
3. Postorder. The ordering is: the left subtree, the right subtree, the current node.
Inorder Traversal Pseudocode
This recursive algorithm takes as the input a pointer to a tree and executed inorder
traversal on the tree. While doing traversal it prints out the key of each node that is
visited.
Inorder-Walk(x)
1. if x = nil then return
2. Inorder-Walk(left[x])
3. Print key[x]
4. Inorder-Walk(right[x])
We can write a similar pseudocode for preorder and postorder.
What is the outcome of
a. inorder traversal?
b. postorder traversal and
c. preorder traversal?
The output of the three BST traversal is:
Inorder traversal gives: 2, 3, 4, 5, 6, 7, 8 , 9, 11, 12, 15, 19, 20.
Preorder traversal gives: 7, 4, 2, 3, 6, 5, 12, 9, 8, 11, 19, 15, 20.
Postorder traversal gives: 3, 2, 5, 6, 4, 8, 11, 9, 15, 20, 19, 12, 7.
Operations on BST
1. Searching for a key: assume that a key and the subtree in which the key is searched for are
given as an input. We’ll take the full advantage of the BST-property.
2. Suppose we are at a node. If the node has the key that is being searched for, then the
search is over. Otherwise, the key at the current node is either strictly smaller than the key
that is searched for or strictly greater than the key that is searched for. If the former is the
case, then by the BST property, all the keys in the left subtree are strictly less than the key
that is searched for. That means that we do not need to search in the left subtree. Thus,
we will examine only the right subtree. If the latter is the case, by symmetry we will
examine only the right subtree.
Algorithm
Here k is the key that is searched for and x is the start node.
BST-Search(x, k)
1. y ← x 2
2. while y 6= nil do
3. if key[y] = k then return y
4. else if key[y] < k then y ← right[y]
5. else y ← left[y]
6. return (“NOT FOUND”)
Your best quote that reflects your
approach… “It’s one small step for man,
one giant leap for mankind.”
- Neil Armstrong

Greedy Algorithm LectueNote

Uploaded by

Copyright:

Available Formats

Greedy Algorithm LectueNote

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Greedy Algorithm LectueNote

Uploaded by

Copyright:

Available Formats

CHAPTER 3:

In searching No loop /Cycle

Cost of Minimum Spanning Tree

You might also like