GREEDY APPROACH

Lecture # 𝟏𝟏

Dr. Imran Khalil

imrankhalil@uetpeshawar.edu.pk
Contents
• Greed?
• Greedy approach
• Greedy approach – Disadvantages
• Activity Selection Problem
• Single Source Shortest Path Problem
• Examples

2
Greed – Introduction

3
Greedy Approach

4
Greedy Approach

5
Disadvantages of Greedy Approach

6
Greedy Approach – Summary

7
Greedy Approach – Examples

8
Activity Selection Problem – Problem Statement

9
Activity Selection Problem – Greedy Approach

10
Activity Selection Problem – Example

Activities 𝑨𝟏 𝑨𝟐 𝑨𝟑 𝑨𝟒 𝑨𝟓 𝑨𝟔
Start 0 3 1 5 5 8
Finish 6 4 2 9 7 9

11
Activity Selection Problem – Example
Step 1: Sort the activities according to their finish time

Activities 𝑨𝟑 𝑨𝟐 𝑨𝟏 𝑨𝟓 𝑨𝟒 𝑨𝟔
Start 1 3 0 5 5 8
Finish 2 4 6 7 9 9

12
Activity Selection Problem – Example
Step 2: Select the first activity from the sorted array and execute.

Activities 𝑨𝟑
Start 1
Finish 2

13
Activity Selection Problem – Example
Step 3: Repeat for remaining activities in the sorted array.
If the start time of this activity is greater than or equal
to the finish time of the previously selected activity
then select this activity and execute it.

Activities 𝑨𝟑 𝑨𝟐
Start 1 3
Finish 2 4

14
Activity Selection Problem – Example
Step 3: Repeat for remaining activities in the sorted array.
If the start time of this activity is greater than or equal
to the finish time of the previously selected activity
then select this activity and execute it.

Activities 𝑨𝟑 𝑨𝟐 𝑨𝟓
Start 1 3 5
Finish 2 4 7

15
Activity Selection Problem – Example
Step 3: Repeat for remaining activities in the sorted array.
If the start time of this activity is greater than or equal
to the finish time of the previously selected activity
then select this activity and execute it.

Activities 𝑨𝟑 𝑨𝟐 𝑨𝟓 𝑨𝟔
Start 1 3 5 8
Finish 2 4 7 9

16
Activity Selection Problem – Practice Problem

Activities 𝑨𝟏 𝑨𝟐 𝑨𝟑 𝑨𝟒 𝑨𝟓 𝑨𝟔 𝑨𝟕 𝑨𝟖
Start 1 0 1 4 2 5 3 4
Finish 3 4 2 6 9 8 5 5

17
A Greedy Approach based Algorithm

18
A Greedy Approach based Algorithm

Time Complexity?
𝒏. 𝒍𝒐𝒈 𝒏

19
Single-Source Shortest Path Problem

20
Problem Statement

21
Dijkstra Algorithm

22
Dijkstra Algorithm – Example

CS & IT, UET Peshawar 23

Dijkstra Algorithm – Example
Step 1:
Remove all the loops
Step 2:
Remove all the parallel edges between two vertices except the one
with the least weight.

CS & IT, UET Peshawar 24

Dijkstra Algorithms

CS & IT, UET Peshawar 25

Dijkstra Algorithm – Example

𝑴𝒂𝒓𝒌𝒆𝒅 𝑨 𝑩 𝑪 𝑫 𝑬 𝑭
𝑨 0 ∞ ∞ ∞ ∞ ∞
𝑩 2 ∞ 3 2 ∞
𝑬 4 3 2 ∞
𝑫 4 3 5
𝑪 4 5
𝑭 5
CS & IT, UET Peshawar 26
Dijkstra Algorithm – Example

𝑴𝒂𝒓𝒌𝒆𝒅 𝑨 𝑩 𝑪 𝑫 𝑬 𝑭
𝑨 0 ∞ ∞ ∞ ∞ ∞
𝑩 2 ∞ 3 2 ∞
𝑬 4 3 2 ∞
𝑫 4 3 5
𝑪 4 5
𝑭 5

CS & IT, UET Peshawar 27

 Dijkstra Algorithm – Example

Shortest Path

𝐴⇒𝐸⇒𝐹
=2+3
= 5 𝑢𝑛𝑖𝑡𝑠

CS & IT, UET Peshawar 28

Practice Problem

CS & IT, UET Peshawar 29

 Practice Problem

Shortest Path

𝐴⇒𝐵⇒𝐶⇒𝐹⇒𝐻
=2+2+4+5
= 13 𝑢𝑛𝑖𝑡𝑠

CS & IT, UET Peshawar 30

Dijkstra Algorithm – Pseudocode
𝑶(𝑽 − 𝟏)

𝑶(𝟏)

𝑶(𝑳𝒐𝒈 𝑽)

𝑶(𝑬. 𝑳𝒐𝒈 𝑽)

31
Dijkstra Algorithm – Time Complexity

32
Acknowledgment
• [Barnett G. et al.] Data Structures and Algorithms
• [Levitin A.] Introduction to the design and analysis
• [T. H. Cormen et al.] Introductions to Algorithms
• .

33