Design & Analysis of Algorithms

chapter 3 Greedy Method

Department of Computer Science

Mekdela amba university

1
 1. DAA ─Greedy Method

What is Greedy Method

 Among all the algorithmic approaches, the simplest and
straightforward approach is the Greedy method.
 In this approach, the decision is taken on the basis of current
available information without worrying about the effect of the
current decision in future.
 Greedy algorithms build a solution part by part, choosing the next
part in such a way, that it gives an immediate benefit.
 This approach never reconsiders the choices taken previously. This
approach is mainly used to solve optimization problems.
 Greedy method is easy to implement and quite efficient in most of
the cases.
 Hence, we can say that Greedy algorithm is an algorithmic paradigm
based on heuristic that follows local optimal choice at each step with
the hope of finding global optimal solution. 2
 1. DAA ─Greedy Method

Components of Greedy Algorithm

 Greedy algorithms have the following five
components:
• A candidate set: A solution is created from this set.
• A selection function: Used to choose the best candidate to be
added to the solution.
• A feasibility function: Used to determine whether a candidate
can be used to contribute to the solution.
• An objective function: Used to assign a value to a solution or a
partial solution.
• A solution function: Used to indicate whether a complete
solution has been reached.
3
 1. DAA ─Greedy Method

Areas of Application
 Greedy approach is used to solve many problems, such as
• Finding the shortest path between two vertices using Dijkstra’s
algorithm.
• Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s
algorithm, etc.
Where Greedy Approach Fails
 In many problems, Greedy algorithm fails to find an optimal solution,
moreover it may produce a worst solution. Problems like Travelling
Salesman and Knapsack cannot be solved using this approach.
 In many problems, it does not produce an optimal solution though it
gives an approximate (near optimal) solution in a reasonable time.

4
 2. JOB SEQUENCING WITH DEADLINES
 The problem is stated as below.
 There are n jobs to be processed on a machine.

 Each job i has a deadline di≥ 0 and profit pi≥0 .

 Pi is earned if the job is completed by its deadline.

 The job is completed if it is processed on a machine for unit time.
 Only one machine is available for processing jobs.

 Only one job is processed at a time on the machine.

 An optimal solution is a feasible solution with maximum profit value
and each job is completed by its deadline..
5
 2. JOB SEQUENCING WITH DEADLINES
Example :Let us consider a set of given jobs as shown in the following
table. We have to find a sequence of jobs, which will be completed
within their deadlines and will give maximum profit. Each job is
associated with a deadline and profit.
Job J1 J2 J3 J4 J5
Deadline 2 1 3 2 1
Profit 60 100 20 40 20

Solution
To solve this problem, the given jobs are sorted according to their profit
in a descending order. Hence, after sorting, the jobs are ordered as
shown in the following table.
Job J2 J1 J4 J3 J5
Deadline 1 2 2 3 1
Profit 100 60 40 20 20
6
 2. JOB SEQUENCING WITH DEADLINES
 From this set of jobs, first we select J2, as it can be
completed within its deadline and contributes maximum
profit.
• Next, J1 is selected as it gives more profit compared to J4.
• In the next clock, J4 cannot be selected as its deadline is
over, hence J3 is selected as it executes within its deadline.
• The job J5 is discarded as it cannot be executed within its
deadline.
 Thus, the solution is the sequence of jobs (J2, J1, J3),
which are being executed within their deadline and gives
maximum profit.
Total profit of this sequence is 𝟏𝟎𝟎 + 𝟔𝟎 + 𝟐𝟎 = 𝟏𝟖𝟎.
7
 3. DAA ─ Optimal Merge Pattern
 Merge a set of sorted files of different length into a single sorted file.
We need to find an optimal solution, where the resultant file will be
generated in minimum time.
 If the number of sorted files are given, there are many ways to merge
them into a single sorted file. This merge can be performed pair wise.
 Hence, this type of merging is called as 2-way merge patterns
 Two-way merge patterns can be represented by binary merge trees.
Let us consider a set of n sorted files {f1, f2, f3, …, fn}. Initially, each
element of this is considered as a single node binary tree. To find this
optimal solution, the following algorithm is used.
8
 3. DAA ─ Optimal Merge Pattern

Algorithm: TREE (n)

for i := 1 to n – 1 do
declare new node
[Link] := least (list)
[Link] := least (list)
[Link]) := (([Link]).weight) + (([Link]).weight)
insert (list, node);
return least (list);

9
 3. DAA ─ Optimal Merge Pattern
Example
->Let us consider the given files, f1, f2, f3, f4 and f5 with 20, 30, 10, 5
and 30 number of elements respectively.
If merge operations are performed according to the provided
sequence, then
M1 = merge f1 and f2 => 𝟐𝟎 + 𝟑𝟎 = 𝟓𝟎
M2 = merge M1 and f3 => 𝟓𝟎 + 𝟏𝟎 = 𝟔𝟎
M3 = merge M2 and f4 => 𝟔𝟎 + 𝟓 = 𝟔𝟓
M4 = merge M3 and f5 => 𝟔𝟓 + 𝟑𝟎 = 𝟗𝟓
Hence, the total number of operations is 𝟓𝟎 + 𝟔𝟎 + 𝟔𝟓 +95=270
Now, the question arises is there any better solution?
 Sorting the numbers according to their size in an ascending order,
we get the following sequence:f4, f3, f1, f2, f5
Hence, merge operations can be performed on this sequence
10
 3. DAA ─ Optimal Merge Pattern
M1 = merge f4 and f3 => 𝟓 + 𝟏𝟎 = 𝟏𝟓
M2 = merge M1 and f1 => 𝟏𝟓 + 𝟐𝟎 = 𝟑𝟓
M3 = merge M2 and f2 => 𝟑𝟓 + 𝟑𝟎 = 𝟔𝟓
M4 = merge M3 and f5 => 𝟔𝟓 + 𝟑𝟎 = 𝟗𝟓
 Therefore, the total number of operations is 𝟏𝟓 + 𝟑𝟓 + 𝟔𝟓 + 𝟗𝟓 = 𝟐𝟏𝟎
 Obviously, this is better than the previous one.
 In this context, we are now going to solve the problem using this
algorithm.
Initial Set

5 10 20 30 30

11
• Step-1 15 20 30 30

5 10

• Step-2
35 30 30

15 20

5 10

12
• Step-3 65 30

35 30

15 20

5 10

13
• Step-4 95

65 30

35 30

15 20

5 10

• Hence, the solution takes 15 + 35 + 65 + 95 = 210

number of comparisons. 14
 4. DAA ─ Spanning Tree

• A spanning tree of a graph is a tree and is

a subgraph that contains all the vertices.
• A graph may have many spanning trees;
for example, the complete graph on four
vertices has sixteen spanning trees:

15
Spanning Tree – cont.

16
 Minimum Spanning Trees
• A Minimum Spanning Tree (MST) is a sub graph of an
undirected graph such that the sub graph spans (includes) all
nodes, is connected, is acyclic, and has minimum total edge
weight.
• Suppose that the edges of the graph have weights or lengths.
The weight of a tree will be the sum of weights of its edges.
• Based on the example, we can see that different trees have
different lengths.
• The question is: how to find the minimum length spanning
tree?

17
 Minimum Spanning Trees
• The question can be solved by many different
algorithms, here is three classical minimum-
spanning tree algorithms :
– Boruvka's Algorithm
– Kruskal's Algorithm
– Prim's Algorithm

18
 Algorithm Characteristics
• Both Prim’s and Kruskal’s Algorithms work with undirected graphs
• Both work with weighted and un weighted graphs but are more
interesting when edges are weighted
• Both are greedy algorithms that produce optimal solutions

19
Kruskal’s Algorithm

Work with edges, rather than nodes

Two steps:
– Sort edges by increasing edge weight
– Select the first |V| – 1 edges that do not
generate a cycle

20
 Walk-Through
Consider an undirected, weight graph
3
10
F C
A 4
4
3
8
6
5
4
B D
4
H 1
2
3
G 3
E

21
 Sort the edges by increasing edge weight
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1 (B,E) 4
8 (B,F) 4
6 (D,G) 2
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

22
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

23
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3 (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

24
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3 (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

Accepting edge (E,G) would create a cycle

25
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3 (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

26
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3 (A,B) 8
(B,C) 4 (A,F) 10

27
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4 (A,F) 10

28
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10

29
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4 
8 (B,F) 4
6 (D,G) 2 
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10

30
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4 
8 (B,F) 4
6 (D,G) 2  
5
4
B D (E,G) 3  (B,H) 4
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10

31
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4 
8 (B,F) 4
6 (D,G) 2  
5
4
B D (E,G) 3  (B,H) 4 
4
H 1
(C,D) 3  (A,H) 5
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10

32
 Select first |V|–1 edges which do not
generate a cycle
3
10
F C edge dv edge dv

A 4
4
3 (D,E) 1  (B,E) 4 
8 (B,F) 4
6 (D,G) 2  
5
4
B D (E,G) 3  (B,H) 4 
4
H 1
(C,D) 3  (A,H) 5 
2
3 (G,H) 3  (D,F) 6
G 3
E (C,F) 3  (A,B) 8
(B,C) 4  (A,F) 10

33
 Select first |V|–1 edges which do not
generate a cycle
3
F C edge dv edge dv

A 4
3 (D,E) 1  (B,E) 4 
(D,G) 2  (B,F) 4 
5
B D (E,G) 3  (B,H) 4 
H 1
(C,D) 3  (A,H) 5 

}
2
3 (G,H) 3  (D,F) 6
G E (C,F) 3  (A,B) 8
not
considered
(B,C) 4  (A,F) 10

Done
Total Cost =  dv = 21

34