8-9 | Greedy algorithms

Question 1

Greedy algorithm definition

Answer 1

Greedy algorithm:

A way of solving a problem by making locally optimal choice with the hope of finding a global optimum

make decisions based on information available at hand without worrying about the effect of these decisions in the future.

Question 2

Types of computational problems

Answer 2

Decision problem

Optimization problem

Counting problem

Question 3

Greedy algorithm: typical use

Answer 3

Typically used to solve optimization problems

Question 4

Optimization problem definition

Answer 4

asks for finding the best possible solution among a set
of all possible solutions to a problem.

Question 5

Example of optimization problem

Answer 5

Change-making problem

Let the coins we have available are of value:
…

Devise an algorithm for paying a given amount of units using the smallest number of coins, if there is unlimited supply for each type of coin.

Question 5

Change making optimization problem

Greedy solution strategy?

Does it find the optimal solution?

Answer 5

Starting with nothing, at every stage we add to the coins already chosen a coin of largest value available that does not take us over the amount to be paid

why greedy?
At every step chooses the largest coin it can (locally optimal)
without worrying this will us to the best solution in the long run

Greedy algorithm does not find an optimal solution! (may depend on available coins)

Question 6

Greedy algorithms: general characteristics?

Answer 6

Set of candidates
Solution function
Feasibility function
Selection function
Objective function

Question 7

Greedy algorithms

Set of candidates ?

examples

Answer 7

An object / entity which is a part of a problem instance

Two disjoint subsets are accumulated
candidates that have been considered and chosen
candidates that have been considered and rejected

example
- Coins that are available for making a change
- Edges in a graph from which one is to find a shortest path

Question 8

Greedy algorithms

Solution function?

examples

Answer 8

checks whether or not a particular set of candidates constitutes a solution
without worrying if the solution is optimal

example
does the selected coins match the amount to be paid?
does the selected edges give a path from between two specified nodes?

Question 9

Greedy algorithms

Feasibility function?

examples

Answer 9

checks whether or not a set of candidates can be completed to a solution by adding other candidates

here, too, we do not worry about optimality

it is important to know whether or not a given set of candidates allows to build a solution, irrespective of optimality

(to show that the feasibility space is not empty)

Question 10

Greedy algorithms

Selection function?

examples

Answer 10

indicates which of the remaining candidates which have neither been selected nor rejected is the most promising

Question 11

Greedy algorithms

Objective function?

examples

Answer 11

gives the value of the solution found

Example
- the number of coins used
- the length of a path

whatever value we aim to optimize

Question 12

How do greedy algorithms work?

Answer 12

How do greedy algorithms work?

Initially, set of chosen candidates is empty

At each step
* consider adding the best remaining untried candidate (choice guided by the selection function)
* if the enlarged set is not feasible (guided by the feasibility function) reject the candidate we are currently considering
* otherwise, the candidate remains in the set of chosen candidates, where it stays from now on
* Each time we enlarge the set of candidates we check if it is a solution (guided by the solution function)

When the greedy algorithm works correctly, the first found solution is optimal

Question 13

Can greedy algorithms backtrack?

Answer 13

There is no turning back in a greedy algorithm

Once a candidate is included in a solution, it stays there for good!

Once a candidate is excluded from a solution, it is never considered again!

Question 14

General greedy algorithm

Answer 14

function greedy(𝐶)
𝐶 is the set of candidates
𝑆 ← ∅ # we construct the solution in 𝑆
while 𝐶 ≠ ∅ and not solution(𝑆) do
𝑥 ← select(𝐶)
if feasible(𝑆 ∪ {𝑥}) then
𝑆 ← 𝑆 ∪ {𝑥}
if solution(𝑆) then # why check this here?
return 𝑆
else
return there are no solutions

Question 15

Selection function

Answer 15

The key to a greedy algorithm is its selection function
Selection function is related to the objective function

Example
* objective – maximizing profit
selection – remaining item of largest value
* objective – minimizing cost
selection – cheapest remaining candidate

Sometimes, more than one selection function – care is needed in choosing the one which ensures correctness

Question 16

Change-making optimization problem

Set of candidates?

Answer 16

coins eg 100, 25, 10, 5, 1

Question 17

Change-making optimization problem

Solution function?

Answer 17

checks that the coins we have so far give the exact amount to be paid

Question 18

Change-making optimization problem

Feasibility function?

Answer 18

a set of coins in feasible if its total value does not exceed the
amount to be paid

Question 19

Change-making optimization problem

Selection function?

Answer 19

chooses the highest-valued coin from those remaining in the set of candidates

Question 20

Change-making optimization problem

Objective function?

Answer 20

the number of coins in the solution 2

Question 21

Change-making optimization problem

Greedy algorithm pseudocode?

Answer 21

function makeChange(n)
𝐶 = {candidate coins}
𝑆 ← ∅ # 𝑆 contains the solution
𝑠 ← 0 # 𝑠 is the sum of items in 𝑆
while 𝑠 ≠ 𝑛 do
𝑥 ← largest item in 𝐶 such that 𝑥 + 𝑠 ≤ 𝑛
if there is no such item
return no solution found
𝑆 ← 𝑆 ∪ {a coin of value 𝑥}
𝑠 ← 𝑠 + 𝑥
return 𝑆

Question 22

Subgraphs

Definition?

Answer 22

A subgraph of a given graph 𝐺 is the graph 𝐻, such that
𝑉(𝐻) ⊆ 𝑉(𝐺) and
𝐸(𝐻) ⊆ 𝐸(𝐺)

Question 23

Subgraphs

Types?

Answer 23

A vertex-induced subgraph of 𝐺 contains
* a subset of vertices of 𝐺
* all the edges that connect them in 𝐺

An edge-induced subgraph of 𝐺 contains
* a subset of edges of 𝐺
* all the vertices that are their end points in 𝐺

Question 24

In graphs, what is a clique?

Answer 24

graph in which all nodes are mutually connected