Scribd
Upload
104 views18 pages

DAA Module 2

This document discusses several problems that can be solved using greedy algorithms including the knapsack problem, job sequencing with deadlines, optimal storage on tapes, and minimum cost spanning trees. It provides examples of greedy algorithms like Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees. It also covers Dijkstra's algorithm for finding single source shortest paths in a graph.

Uploaded by

Avinash Chunduri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
104 views18 pages

DAA Module 2

This document discusses several problems that can be solved using greedy algorithms including the knapsack problem, job sequencing with deadlines, optimal storage on tapes, and minimum cost spanning trees. It provides examples of greedy algorithms like Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees. It also covers Dijkstra's algorithm for finding single source shortest paths in a graph.

Uploaded by

Avinash Chunduri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MODULE-2

THE GREEDY METHOD

THE GENERAL METHOD:

DAA, Module-2 Page 1


DAA, Module-2 Page 2
Example for Greedy Method:

KNAPSACK PROBLEM:

Algorithm for Knapsack Problem:

DAA, Module-2 Page 3


Three feasible solutions are,

Out of three feasible solutions, solution 4 yields maximum profit. This solution is an optimal solution for
a given problem. All the solutions are shown below.

2st Feasible solution: Select the objects according to decreasing order of their profits.

DAA, Module-2 Page 4


3rd Feasible solution: Select the objects according to increasing order of their weights.

4th Feasible solution: Select the objects according to decreasing order of their profit/weight(pi/wi)

DAA, Module-2 Page 5


JOB SEQUENCING WITH DEADLINES :

DAA, Module-2 Page 6


Using greedy method to get an optimal solution:

DAA, Module-2 Page 7


OPTIMAL STORAGE ON TAPES:

DAA, Module-2 Page 8


DAA, Module-2 Page 9
MINIMUM COST SPANNING TREE:

DAA, Module-2 Page 10


For any problem, there are some greedy methods that are useful for finding minimum cost spanning
tree. These methods are,
 Prim’s Algorithm
 Kruskal’s Algorithm

PRIM’S ALGORITHM:

DAA, Module-2 Page 11


DAA, Module-2 Page 12
KRUSKAL’S ALGORITHM :
In this, always minimum coat edge has to be selected. It is not necessary to select the edge from already
connected vertices.

DAA, Module-2 Page 13


Algorithm :

DAA, Module-2 Page 14


SINGLE SOURCE SHORTEST PATHS (Dijkstra’s Algorithm):

DAA, Module-2 Page 15


DAA, Module-2 Page 16
The algorithm 4.14 : It shows the

DAA, Module-2 Page 17


DAA, Module-2 Page 18

You might also like