1 of 93

Algorithm Problem Solving (APS):

Greedy Method

Niema Moshiri

UC San Diego SPIS 2021

2 of 93

Example: The Change Problem (USA Currency)

In the USA, we commonly use the following coins:

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}

3 of 93

Example: The Change Problem (USA Currency)

In the USA, we commonly use the following coins:

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}

Input: A non-negative integer x (in cents, not dollars)

4 of 93

Example: The Change Problem (USA Currency)

In the USA, we commonly use the following coins:

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}

Input: A non-negative integer x (in cents, not dollars)
Output: A selection of coins in C summing to x

5 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you an arcade token

6 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you an arcade token
You would probably be annoyed with me, but why?

7 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you an arcade token
You would probably be annoyed with me, but why?

I selected a coin that wasn’t in C!

8 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you an arcade token
You would probably be annoyed with me, but why?

I selected a coin that wasn’t in C!

The issue: my solution is incorrect

9 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 2 pennies

10 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 2 pennies
You would probably be annoyed with me, but why?

11 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 2 pennies
You would probably be annoyed with me, but why?

All coins I selected were in C

12 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 2 pennies
You would probably be annoyed with me, but why?

All coins I selected were in C
The coins I selected don’t sum to 42!

13 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 2 pennies
You would probably be annoyed with me, but why?

All coins I selected were in C
The coins I selected don’t sum to 42!

The issue: my solution is incorrect

14 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 42 pennies

15 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 42 pennies
You would probably be annoyed with me, but why?

16 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 42 pennies
You would probably be annoyed with me, but why?

All coins I selected were in C

17 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 42 pennies
You would probably be annoyed with me, but why?

All coins I selected were in C
The sum of my coins equals 42

18 of 93

Example: The Change Problem (USA Currency)

Imagine I owe you 42¢, so I give you 42 pennies
You would probably be annoyed with me, but why?

All coins I selected were in C
The sum of my coins equals 42

The issue: your problem formulation was not specific!

19 of 93

Optimization Problems

In many problems, we may have many (even infinite) possible solutions

20 of 93

Optimization Problems

In many problems, we may have many (even infinite) possible solutions
In all problems, we must define the precise definition of correctness

21 of 93

Optimization Problems

In many problems, we may have many (even infinite) possible solutions
In all problems, we must define the precise definition of correctness
We can also choose to define an objective function to optimize

22 of 93

Optimization Problems

In many problems, we may have many (even infinite) possible solutions
In all problems, we must define the precise definition of correctness
We can also choose to define an objective function to optimize
A solution satisfying the definition of correctness is correct

23 of 93

Optimization Problems

In many problems, we may have many (even infinite) possible solutions
In all problems, we must define the precise definition of correctness
We can also choose to define an objective function to optimize
A solution satisfying the definition of correctness is correct
A correct solution optimizing the objective function is optimal

24 of 93

Revisiting the Change Problem (USA Currency)

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}

25 of 93

Revisiting the Change Problem (USA Currency)

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}
Input: A non-negative integer x (in cents, not dollars)

26 of 93

Revisiting the Change Problem (USA Currency)

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}
Input: A non-negative integer x (in cents, not dollars)
Output: A selection of coins in C summing to x

27 of 93

Revisiting the Change Problem (USA Currency)

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}
Input: A non-negative integer x (in cents, not dollars)
Output: A selection of coins in C summing to x such that the number of selected coins is minimized

28 of 93

Multiple Optimal Solutions

In some problems, there may be multiple equally-optimal solutions

29 of 93

Multiple Optimal Solutions

In some problems, there may be multiple equally-optimal solutions

Imagine if C = {1¢, 2¢, 3¢, 4¢} and x = 5¢

30 of 93

Multiple Optimal Solutions

In some problems, there may be multiple equally-optimal solutions

Imagine if C = {1¢, 2¢, 3¢, 4¢} and x = 5¢
[1¢, 4¢] and [2¢, 3¢] are equally-optimal solutions

31 of 93

Multiple Optimal Solutions

In some problems, there may be multiple equally-optimal solutions

Imagine if C = {1¢, 2¢, 3¢, 4¢} and x = 5¢
[1¢, 4¢] and [2¢, 3¢] are equally-optimal solutions

You should be happy receiving any such solution

32 of 93

Multiple Optimal Solutions

In some problems, there may be multiple equally-optimal solutions

Imagine if C = {1¢, 2¢, 3¢, 4¢} and x = 5¢
[1¢, 4¢] and [2¢, 3¢] are equally-optimal solutions

You should be happy receiving any such solution

If not, you need to fix your objective function!

33 of 93

Revisiting the Change Problem (USA Currency)

C = {1¢ (penny), 5¢ (nickel), 10¢ (dime), 25¢ (quarter)}
Imagine I owe you 42¢. How should I choose the coins to give you?

Let’s solve the problem!

34 of 93

Revisiting the Change Problem (USA Currency)

Algorithm change_USA(x,C):

change ← empty list

For each coin c in C (descending order):

While x >= c:

Add c to change

x ← x - c

Return change

35 of 93

Revisiting the Change Problem (USA Currency)

Algorithm change_USA(x,C):

change ← empty list

For each coin c in C (descending order):

While x >= c:

Add c to change

x ← x - c

Return change

Does this work for any arbitrary currency?

36 of 93

Global vs. Local Search

There may be many (even infinite!) possible solutions to our problem

37 of 93

Global vs. Local Search

There may be many (even infinite!) possible solutions to our problem

Exhaustive: Simply looking at every possible solution

38 of 93

Global vs. Local Search

There may be many (even infinite!) possible solutions to our problem

Exhaustive: Simply looking at every possible solution

When we try to cleverly search for an optimal solution more quickly:

39 of 93

Global vs. Local Search

There may be many (even infinite!) possible solutions to our problem

Exhaustive: Simply looking at every possible solution

When we try to cleverly search for an optimal solution more quickly:

Global: We can look at entire solutions at a time

40 of 93

Global vs. Local Search

There may be many (even infinite!) possible solutions to our problem

Exhaustive: Simply looking at every possible solution

When we try to cleverly search for an optimal solution more quickly:

Global: We can look at entire solutions at a time
Local: We can break solutions into parts and optimize part-by-part

41 of 93

Local Search: The Greedy Method

Greedy Method: Selecting the best possible choice at each step

42 of 93

Local Search: The Greedy Method

Greedy Method: Selecting the best possible choice at each step
Note that this does not always work!!!

43 of 93

Local Search: The Greedy Method

Greedy Method: Selecting the best possible choice at each step
Note that this does not always work!!!

We often skip what’s immediately best to improve in the long-run

44 of 93

Local Search: The Greedy Method

Greedy Method: Selecting the best possible choice at each step
Note that this does not always work!!!

We often skip what’s immediately best to improve in the long-run
Example: Buying vs. leasing a car

45 of 93

Local Search: The Greedy Method

Greedy Method: Selecting the best possible choice at each step
Note that this does not always work!!!

We often skip what’s immediately best to improve in the long-run
Example: Buying vs. leasing a car

Thus, it’s important to prove the correctness of a Greedy Algorithm

46 of 93

Revisiting the Change Problem

C = {1¢, 3¢, 4¢}

47 of 93

Revisiting the Change Problem

C = {1¢, 3¢, 4¢}
Imagine I owe you 6¢. How should I choose the coins to give you?

48 of 93

Revisiting the Change Problem

C = {1¢, 3¢, 4¢}
Imagine I owe you 6¢. How should I choose the coins to give you?

The greedy algorithm would return [4¢, 1¢, 1¢]

49 of 93

Revisiting the Change Problem

C = {1¢, 3¢, 4¢}
Imagine I owe you 6¢. How should I choose the coins to give you?

The greedy algorithm would return [4¢, 1¢, 1¢]
The optimal solution is [3¢, 3¢]

50 of 93

Revisiting the Change Problem

C = {1¢, 3¢, 4¢}
Imagine I owe you 6¢. How should I choose the coins to give you?

The greedy algorithm would return [4¢, 1¢, 1¢]
The optimal solution is [3¢, 3¢]
Our greedy algorithm doesn’t work for all possible currencies!!!

51 of 93

Immediate Benefit vs. Opportunity Cost

52 of 93

Immediate Benefit vs. Opportunity Cost

Immediate Benefit: How much do I gain from this choice?

53 of 93

Immediate Benefit vs. Opportunity Cost

Immediate Benefit: How much do I gain from this choice?
Opportunity Cost: How much is the future restricted by this choice?

54 of 93

Immediate Benefit vs. Opportunity Cost

Immediate Benefit: How much do I gain from this choice?
Opportunity Cost: How much is the future restricted by this choice?
Greedy: Take the best immediate benefit and ignore opportunity costs

55 of 93

Immediate Benefit vs. Opportunity Cost

Immediate Benefit: How much do I gain from this choice?
Opportunity Cost: How much is the future restricted by this choice?
Greedy: Take the best immediate benefit and ignore opportunity costs

Optimal when immediate benefit outweighs opportunity costs

56 of 93

Example: The Event Scheduling Problem

Imagine you own an event room, and you want to schedule events

57 of 93

Example: The Event Scheduling Problem

Imagine you own an event room, and you want to schedule events

You charge a flat rate, regardless of the length of the event

58 of 93

Example: The Event Scheduling Problem

Imagine you own an event room, and you want to schedule events

You charge a flat rate, regardless of the length of the event
Thus, you want to schedule as many events as possible

59 of 93

Example: The Event Scheduling Problem

Imagine you own an event room, and you want to schedule events

You charge a flat rate, regardless of the length of the event
Thus, you want to schedule as many events as possible
However, events cannot overlap

60 of 93

Example: The Event Scheduling Problem

Input: All n possible events E = [(start₁, end₁), …, (start_n, end_n)]

61 of 93

Example: The Event Scheduling Problem

Input: All n possible events E = [(start₁, end₁), …, (start_n, end_n)]
Output: A non-overlapping subset of E maximizing its size

62 of 93

Example: The Event Scheduling Problem

Input: All n possible events E = [(start₁, end₁), …, (start_n, end_n)]
Output: A non-overlapping subset of E maximizing its size
If we wanted to design a greedy algorithm, what would we optimize?

63 of 93

Example: The Event Scheduling Problem

Input: All n possible events E = [(start₁, end₁), …, (start_n, end_n)]
Output: A non-overlapping subset of E maximizing its size
If we wanted to design a greedy algorithm, what would we optimize?

Shortest duration?
Earliest start time?
Fewest conflicts?
Earliest end time?

64 of 93

Counterexample: Shortest Duration

65 of 93

Counterexample: Shortest Duration

66 of 93

Counterexample: Shortest Duration

67 of 93

Counterexample: Shortest Duration

68 of 93

Counterexample: Shortest Duration

69 of 93

Counterexample: Earliest Start Time

70 of 93

Counterexample: Earliest Start Time

71 of 93

Counterexample: Earliest Start Time

72 of 93

Counterexample: Earliest Start Time

73 of 93

Counterexample: Earliest Start Time

74 of 93

Counterexample: Fewest Conflicts

75 of 93

Counterexample: Fewest Conflicts

76 of 93

Counterexample: Fewest Conflicts

77 of 93

Counterexample: Fewest Conflicts

78 of 93

Counterexample: Fewest Conflicts

79 of 93

Counterexample: Fewest Conflicts

80 of 93

Counterexample: Fewest Conflicts

81 of 93

Counterexample: Fewest Conflicts

82 of 93

Counterexample: Fewest Conflicts

83 of 93

Counterexample: Earliest End Time

84 of 93

Counterexample: Earliest End Time

I can’t think of one!

85 of 93

Counterexample: Earliest End Time

I can’t think of one!

We still need to prove it’s correct!!!

86 of 93

Example: The Event Scheduling Problem

Algorithm schedule(E):

Sort E in ascending order of end time

curr_time ← negative infinity

events ← empty list

For each event (start,end) in E:

If start ≥ curr_time:

Add (start,end) to events

curr_time ← end

Return events

87 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

88 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

Let g be the first greedy choice

89 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

Let g be the first greedy choice
Let S be any optimal solution that does not include g

90 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

Let g be the first greedy choice
Let S be any optimal solution that does not include g
Create S’ by exchanging a choice in S with g and show that

91 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

Let g be the first greedy choice
Let S be any optimal solution that does not include g
Create S’ by exchanging a choice in S with g and show that

S’ is a valid solution

92 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

Let g be the first greedy choice
Let S be any optimal solution that does not include g
Create S’ by exchanging a choice in S with g and show that

S’ is a valid solution
S’ is just as good, or better than, S

93 of 93

Proofs: The Exchange Argument

Common approach for proving greedy algorithms

Let g be the first greedy choice
Let S be any optimal solution that does not include g
Create S’ by exchanging a choice in S with g and show that

S’ is a valid solution
S’ is just as good, or better than, S

Let’s try to prove our algorithm!