Algorithms and Data Structures

Lecture notes: Algorithm paradigms: Greedy

algorithms

Lecturer: Michel Toulouse

Hanoi University of Science and Technology

michel.toulouse@soict.hust.edu.vn

21 juin 2021
Outline

Greedy algorithms : an introduction

Greedy algo for 0-1 knapsack

Minimum spanning tree problem

Kruskal’s algorithm
Prim’s algorithm

The single-source shortest paths problem

Huffman’s encoding

Exercises
Greedy algorithms

Greedy algorithms can be used to solve the same type of ”optimization”

problems where divide&conquer or dynamic programming are applied,
such as making change, 0-1 knapsack or shortest path problems

In all theses problems the solution consist to select a subset of objects

optimizing some objective function :
I Making change : select the minimum subset of coins to return
change
I Knapsack : select a subset of objects that maximize profit
Greedy algorithms

Finding the right subsets of object is complicated using

divide&conquer or dynamic programming, while solutions by greedy
algorithms are extremely simple :
I order the object according to some ”desirability” (greedy) criterion
I select the objects based on the ”greedy criterion” used to order
them
For example, objects of a 0-1 knapsack can be sorted based on their
value, object with the greatest value come first

Then objects are put in the knapsack according to this greedy criterion
if their weight is smaller than the residual capacity of the knapsack
A greedy algorithm for 0-1 knapsack

Object i 1 2 3 4 5
Weight wi 2 3 5 6 4
Value vi 6 1 12 8 7

Greedy 0-1-Knapsack(int W = 11, int n)

int selected objects[n] = {0} ;
int objects[n] ;
int i, j, w = W
v [i]
Sort objects[] according either to their values, weights or density w [i]
for (i=1 ; i ≤ n, i++)
j = objects[i]
if (w > wj )
selected objects[i] = j
w = w − wj
i ++
Greedy criterion is values

Object i 1 2 3 4 5
Weight wi 2 3 5 6 4
Value vi 6 1 12 8 7
Greedy 0-1-Knapsack(int W = 11,int n)
int selected objects[n] = {0} ; int w = W ; int objects[n] ; int i, j
Sort in objects[n] objects along values
for (i = 1; i ≤ n, i + +)
j = objects[i]
if (w > wj )
selected objects[i] = j
w = w − wj
i ++
objects = [3, 4, 5, 1, 2] after sorting
i = 1, object = 3, selected objects = [3, 0, 0, 0, 0], w = 6
i = 2, object = 4, selected objects = [3, 4, 0, 0, 0], w = 0
Solution is 20
Greedy criterion is weights

Object i 1 2 3 4 5
Weight wi 2 3 5 6 4
Value vi 6 1 12 8 7
Greedy 0-1-Knapsack(int W = 11,int n)
int selected objects[n] = {0} ; int w = W ; int objects[n] ; int i, j
Sort in objects[n] objects along weights
for (i = 1; i ≤ n, i + +)
j = objects[i]
if (w > wj )
selected objects[i] = j
w = w − wj
i ++
objects = [1, 2, 5, 3, 4] after sorting
i = 1, object = 1, selected objects = [1, 0, 0, 0, 0], w = 9
i = 2, object = 2, selected objects = [1, 2, 0, 0, 0], w = 6
i = 3, object = 5, selected objects = [1, 2, 5, 0, 0], w = 2
Solution is 14
Greedy criterion is density

Object i 1 2 3 4 5
Weight wi 2 3 5 6 4
Value vi 6 1 12 8 7
Greedy 0-1-Knapsack(int W = 11,int n)
int selected objects[n] = {0} ; int w = W ; int objects[n] ; int i, j
Sort in objects[n] objects along density wv [i]
[i]
for (i = 1; i ≤ n, i + +)
j = objects[i]
if (w > wj )
selected objects[i] = j
w = w − wj
i ++
objects = [1, 3, 5, 4, 2] after sorting
i = 1, object = 1, selected objects = [1, 0, 0, 0, 0], w = 9
i = 2, object = 3, selected objects = [1, 3, 0, 0, 0], w = 4
i = 3, object = 5, selected objects = [1, 2, 5, 0, 0], w = 0
Solution is 25
Problems where greedy algorithms fail

We have just see that greedy algorithm for the same 0-1 knapsack problem instance
returns 3 different solutions !

This because greedy algorithms may fail to solve some optimization problems to
optimality, this is the case for 0-1 knapsack and the making change problem

There are other optimization problems for which greedy work perfectly well, in this
case greedy is a wonderful algorithm because it is simple and computationally very
efficient (low asymptotic complexity)

Greedy works when a problem satisfies a second condition (beside the optimal
substructure condition) : the greedy choice condition

We will not have time to elaborate on the greedy choice condition.

Minimum Spanning Tree (MST)
Let G = (V , E ) be a connected, weighted graph.

A weighted graph is a graph where a real number called weight is

associated with each edge.

A spanning tree of G is a subgraph T of G which is a tree that spans

all vertices of G . In other words, T contains all of the vertices of G .
Usually there are several spanning trees for a same graph

Figure – Weighted graph and corresponding spanning tree

Minimum Spanning Tree
The weight of a spanning tree T is the sum of the weights of its edges.
That is, X
w (T ) = w (u, v ).
(u,v )∈T

A minimum spanning tree (MST) of G is spanning tree T of minimum

weight.

Figure – Weighted graph and corresponding spanning tree

Minimum Spanning Tree : Examples

There could also be more than one MST for a same graph. In this
example, there are two minimum spanning trees.

4 3 2

9 7 4
3 3
G 5
2
6
4 1

3 2 4 3 2

T1 3 3 T2
3 3
2 2

4 1 1
Constructing an MST

The minimum spanning tree problem can be solved optimally using a

greedy algorithm.

There are actually two common greedy algorithms to construct MSTs :

I Kruskal’s algorithm
I Prim’s algorithm

Both of these algorithms use the same basic ideas, but in a slightly
different fashion.
Kruskal’s Algorithm
Initially makes each node of the graph as a tree with a single node, i.e. a
forest of trees
Then greedily select the shortest edge no making a cycle to be part of the
MST
This edge merge two trees into a single one

Algorithm Kruskal(G )
input : Graph G = (V , E ) ;
output : A minimum spanning tree T ;
Sort E by increasing length ;
n = |V | ;
T = ∅;
For each v ∈ V MakeSet(v)
for i = 1 to |E | do /* Greedy loop */
{u, v } = shortest edge not yet considered ;
if (FindSet(u) 6= FindSet(v)) then
Union(FindSet(u),
S FindSet(v))
T = T {u, v } ;
return T
Kruskal’s Algorithm Example
for i = 1 to |E | do /* Greedy loop */
{u, v } = shortest edge not yet considered ;
if (FindSet(u) 6= FindSet(v)) then
Union(FindSet(u),
S FindSet(v))
T = T {u, v } ;
return T

A 5 4 C A 5 4 C
B 1 B 1
4 2 4 2
D
6 E D
6 E
12 2 12 2
9 7 3 8 9 7 3 8
E F G E F G
11 1 11 1

A 5 4 C A 5 4 C
B 1 B 1
4 2 4 2
D 6 E D 6 E
12 2 12 2
9 7 3 8 9 7 3 8
E F G E F G
11 1 11 1
for i = 1 to |E | do /* Greedy loop */
{u, v } = shortest edge not yet considered ;
if (FindSet(u) 6= FindSet(v)) then
Union(FindSet(u),
S FindSet(v))
T = T {u, v } ;
return T

A 5 4 C A 5 4 C
B 1 B 1
4 2 4 2
D
6 E D
6 E
12 2 12 2
9 7 3 8 9 7 3 8
E F G E F G
11 1 11 1

A 5 4 C
A 5 4 C 4
B 1
B 1 2
4 2 6
6 2 D E
2 D E 12
12 9 7 3 8
9 7 3 8 E F G
E F G 11 1
11 1
for i = 1 to |E | do /* Greedy loop */
{u, v } = shortest edge not yet considered ;
if (FindSet(u) 6= FindSet(v)) then
Union(FindSet(u),
S FindSet(v))
T = T {u, v } ;
return T

5 4 A 5 4 C
A C B 1
4
B 1 4 2
2 6
D
6 E 12 2 D E
12 2
9 8 9 7 3 8
7 3
E F G
E F G 1
11 1 11

A 5 4 C A 5 4 C
B 1 B 1
4 2 4 2
D
6 E D
6 E
12 2 12 2
9 7 3 8 9 7 3 8
E F G E F G
11 1 11 1
for i = 1 to |E | do /* Greedy loop */
{u, v } = shortest edge not yet considered ;
if (FindSet(u) 6= FindSet(v)) then
Union(FindSet(u),
S FindSet(v))
T = T {u, v } ;
return T

A 5 4 C A 5 4 C
B 1 B 1
4 2 4 2
D
6 E D
6 E
12 2 12 2
9 7 3 8 9 7 3 8
E F G E F G
11 1 11 1

A 5 4 C 4
B 1
4 2 2 1
6 4
2 D E
12 2
9 7 3 8 9
E F G
11 1 1
Kruskal’s Algorithm : time complexity analysis

Algorithm Kruskal(G )
input : Graph G = (V , E ) ;
output : A minimum spanning tree T ;
Sort E by increasing length ;
n = |V | ;
I Sort edges : O(E lg E )
T = ∅; I O(n) MakeSet()’s
for each v ∈ V MakeSet(v)
for i = 1 to |E | do
I O(E ) FindSet()’s Union()’s
shortest {u, v } not yet considered ; operations
if (FindSet(u) 6= FindSet(v)) then
Union(FindSet(u),
S FindSet(v))
T = T {u, v } ;
return T
Exercises on Kruskal’s algorithm
Consider the non-oriented weighted graph G below represented using
an adjacency matrix
a b c d e f g h i j k l m
a 1 6 2
b 1 2 3
c 4
d 1 5 3 1
e 1 3 2
f 2
g 4
h 3 1
i 2
j 1
k 1
l 2
m

1. Draw this graph

2. Compute by hand a minimum spanning tree using Kruskal’s
algorithm. Show which edge is selected at each step of the greedy
algorithm and tell whether it is included in the spanning tree or
whether it is rejected
3. Is there more than one minimum spanning for this graph
Exercise on Kruskal’s algorithm

Compute the MST using Kruskal’s algorithm. At each step of the

computation, show the configuration of sub-trees.

1
6 5

1
2 5 5 4

3 3 2
6 4

5 6
6
Prim’s Algorithm
1. Prim selects arbitrary a node A of the graph to be the root of the MST
T
2. Then selects the shortest edge adjacent to A to be the first edge of T
3. Prim grows the MST T by selecting the shortest edge adjacent to a
node of T , not yet in T and not forming a cycle

Prim MST(G , r )
∀u∈G
key [u] = Max Int ;
key [r ] = 0 ;
p[r ] = NIL ;
Q = MinPriorityQueue(V )
while (Q 6= ∅)
u = ExtractMin(Q) ;
for each v adjacent to u
if ((v ∈ Q) & (w (u, v ) < key [v ]))
p[v ] = u ;
key [v ] = w (u, v ) ;
 a 5 c 4 v a b c d e f g h
f 1
4 2
6 k 0 oo oo oo oo oo oo oo
while (Q 6= ∅) 12 2 e h
p nil ? ? ? ? ? ? ?
9 7 3 8
u = ExtractMin(Q) ; b d g
11 1 Q=[a,b,c,d,e,f,g,h]
for each v adjacent to u
5 4
if ((v ∈ Q) a
4
c
2
f 1 v a b c d e f g h
6 k 0 12 5 4 oo oo oo oo
& (w (u, v ) < key [v ])) 12 2 e h
p nil a a
9 3 8 a ? ? ? ?
7
p[v ] = u ; b d g
11 1 Q=[d,c,b,e,f,g,h]
key [v ] = w (u, v ) ;
a 5 c 4 v a b c d e f g h
f 1
4 2
e 6 k 0 11 2 4 7 oo 1 oo
12 2 h
9 8 p nil d d a d ? d ?
7 3
b d g
11 1 Q=[g,c,e,b,f,h]

a 5 c 4 v a b c d e f g h
f 1
4 2
6 k 0 11 2 4 3 8 1 oo
12 2 e h
9 8 p nil d d a g g d ?
7 3
b d g
11 1 Q=[c,e,f,b,h]
 a 5 c 4 v a b c d e f g h
f 1
4 2
6 k 0 9 2 4 2 4 1 oo
while (Q 6= ∅) 12
9
2 e h
p nil c d a c c d ?
7 3 8
u = ExtractMin(Q) ; b d g
11 1 Q=[e,f,b,h]
for each v adjacent to u
5 4
if ((v ∈ Q) a
4
c
2
f 1 v a b c d e f g h
6 k 0 9 2 4 2 4 1 6
& (w (u, v ) < key [v ])) 12 2 e h
p nil c
9 3 8 d a c c d e
p[v ] = u ; 7
b d g
11 1 Q=[f,h,b]
key [v ] = w (u, v ) ;
a 5 c 4 v a b c d e f g h
f 1
4 2
6 k 0 9 2 4 2 4 1 1
12 2 e h
9 8 p nil c d a c c d f
7 3
b d g
11 1 Q=[h,b]
 a 5 c 4 v a b c d e f g h
f 1
4 2
6 k 0 9 2 4 2 4 1 1
while (Q 6= ∅) 12
9
2 e h
p nil c d a c c d f
7 3 8
u = ExtractMin(Q) ; b d
1
g
Q=[b]
11
for each v adjacent to u
5 4
if ((v ∈ Q) a
4
c
2
f 1 v a b c d e f g h
6 k 0 9 2 4 2 4 1 1
& (w (u, v ) < key [v ])) 12 2 e h
p nil c a c
9 3 8 d c d f
7
p[v ] = u ; b d g
11 1 Q=[]
key [v ] = w (u, v ) ;
Prim’s Algorithm : time complexity analysis

Prim MST(G , r )
∀u∈G Priority Queue : O(n)
key [u] = Max Int ; while loop runs n times
key [r ] = 0 ;
I ExractMin cost O(lg n), total
p[r ] = NIL ;
Q = MinPriorityQueue(V ) O(n lg n)
while (Q 6= ∅) I for loop is executed 2|E | times
u = ExtractMin(Q) ;
for each v adjacent to u
(Amortized analysis)
if ((v ∈ Q) & (w (u, v ) < key [v ])) I Each time could potentially
p[v ] = u ; change key [v ], O(lg n)
key [v ] = w (u, v ) ;
I Total cost of for loop is
O(E lg n)
while loop is
O(n lg n + E lg n) ∈ O(E lg n)
Exercise on Prim’s algorithm

Compute the MST using Prim’s algorithm. At each step of the

computation, show the configuration of the partial MST.

1
6 5

1
2 5 5 4

3 3 2
6 4

5 6
6
Exercise on Prim’s algorithm
Compute the MST using Prim’s algorithm. Fill the table at each step.

v a b c d e f
k
P

3
a e
1
9 4

3
b d
1
4
2

c 5
f
The single-source shortest paths problem

Let G = {V , E } be a connected directed graph where V is the set of

nodes and E is the set of arcs.
I Each arc a ∈ E has a nonnegative length.
I One of the node is designated as the source node.
I The problem is to determine the length of the shortest path from
the source node to each of the other nodes of the graph
This problem can be solved by a greedy algorithm called Dijkstra’s
algorithm

10 1 50

5 100 30 2
10 20 5
4 50 3
Greedy aspects of Dijkstra’s algorithm

Step v C D S
10 1 50 init {2,3,4,5} {50,30,100,10} {1}
5 100 30 2 1 5 {2,3,4} {50,30,20,10} {1,5}
10 20 5 2 4 {2,3} {40,30,20,10} {1,4,5}
4 50 3 3 3 {2} {35,30,20,10} {1,3,4,5}
{1,2,3,4,5}

Initially, the path from s to any other node x is the direct edge (s, x)
These edges are sorted in increasing order of their length, greedy algo selects the
shortest edge (s, y ) among them, this become the first shortest path
Then Dijkstra’s algo re-calculate the distance of the path from s to any node other
node x (different from y ) using the shortest path (s, y ) and edge (y , x) if such an
edge exist

Those paths are sorted in increasing order of their length, greedy algo (Dijkstra)
selects the shortest one, this become the second shortest path
Greedy aspects of Dijkstra’s algorithm

Step v C D S
10 1 50 init {2,3,4,5} {50,30,100,10} {1}
5 100 30 2 1 5 {2,3,4} {50,30,20,10} {1,5}
10 20 5 2 4 {2,3} {40,30,20,10} {1,4,5}
4 50 3 3 3 {2} {35,30,20,10} {1,3,4,5}
{1,2,3,4,5}

In general, each time a new shortest path (s, ..., y ) has been found,
I Dijkstra’s algo re-calculate the distance from the source node s to any other
node x for which the shortest path (s, ..., x) is yet to be found
I The re-calculation is obtained by creating a path (s, ..., y , x), if this path is
shortest than the existing path (s, ...x), then the length of (s, ..., y , x)
becomes the lenght of the path from s to x.
I Then Dijkstra selects the shortest of all these paths that link s to a node x for
which the shortest path has not yet be computed
Dijkstra’s algorithm
Step v C D S
10 1 50 init {2,3,4,5} {50,30,100,10} {1}
5 100 30 2 1 5 {2,3,4} {50,30,20,10} {1,5}
10 20 5 2 4 {2,3} {40,30,20,10} {1,4,5}
4 50 3 3 3 {2} {35,30,20,10} {1,3,4,5}
{1,2,3,4,5}

Here each time a new shortest path is computed, the distance from the source node
to all the other nodes is re-calculated and stored into the distance vector D.

Algorithm Dijkstra(G )
C = {2, 3, . . . , n} {S = V \ C }
for i = 2 to n do D[i] = L[1, i]
repeat n − 2 times
v = some element of C minimizing D[v ]
C = C \ {v }
for each w ∈ C do
D[w ] = min(D[w ], D[v ] + L[v , w ])
return D
Dijkstra’s algorithm : time complexity analysis
Algorithm Dijkstra(G )
C = {2, 3, . . . , n} {S = V \ C }
for i = 2 to n do D[i] = L[1, i]
repeat n − 1 times
v = some element of C minimizing D[v ]
C = C \ {v }
for each w ∈ C do
D[w ] = min(D[w ], D[v ] + L[v , w ])
return D

The initialization of C and D cost O(n)

In the repeat loop

I the instruction ”v = some element of C minimizing D[v ]” cost
O(n)
I The for loop is also running in O(n)
Therefore the repeat loop runs in O(n2 ).
Dijkstra’s algorithm : obtaining the shortest paths
To obtain the shortest paths (not just their length), we need a new
array P[2..n] where P[v ] contains the node that precedes v in the
shortest path

To find the shortest path from a node v to the source just follow the
pointers in reverse direction starting at v
Algorithm Dijkstra(G )
C = {2, 3, . . . , n} {S = V \ C }
for i = 2 to n do
D[i] = L[1, i]
P[i] = 1
repeat n − 1 times
v = some element of C minimizing D[v ]
C = C \ {v }
for each w ∈ C do
if D[w ] > D[v ] + L[v , w ] then
D[w ] = min(D[w ], D[v ] + L[v , w ])
P[w ] = v
return D and P
Dijkstra’s algorithm : obtaining the shortest paths
Here are consecutive states of P for the previous example :
Step v C D S
10 1 50 init {2,3,4,5} {50,30,100,10} {1}
5 100 30 2 1 5 {2,3,4} {50,30,20,10} {1,5}
10 20 5 2 4 {2,3} {40,30,20,10} {1,4,5}
4 50 3 3 3 {2} {35,30,20,10} {1,3,4,5}
{1,2,3,4,5}

P 1 2 3 4 5
I v =5
1 1 1 5 1
P 1 2 3 4 5
I v =4
1 4 1 5 1
P 1 2 3 4 5
I v =3
1 3 1 5 1
P 1 2 3 4 5
I v =2
1 3 1 5 1
Exercise : single-source shortest paths
Compute the single-source shortest paths for the oriented graph below.
The source is node s.

Algorithm Dijkstra(G )
C = {2, 3, . . . , n} {S = V \ C }
for i = 2 to n do D[i] = L[1, i]
repeat n − 1 times
v = some element of C minimizing D[v ]
C = C \ {v }
for each w ∈ C do
D[w ] = min(D[w ], D[v ] + L[v , w ])
return D
Exercise : single-source shortest paths
Compute the length as well as the single-source shortest paths for the
oriented graph below. The source is node 1.

9 5
6
2
2
11 6
14 3

9 10
15

7
4
Exercise : single-source shortest paths
Compute the length as well as the single-source shortest paths for the
oriented graph below. The source is node 1.

4
20
10

10
5 5

1
30
30 20
20

2 3
40
Encoding data : Huffman algorithm

Huffman algorithm build prefix codes that are optimal in terms of the
number of bits needed to encode a text

The Huffman algorithm is a greedy algorithm, it is another example of

optimization problem that can be solved optimally using a greedy
algorithm
Fixed-length codes

Alphabetic characters used to be stored in ASCII on computers, which

requires 7 bits per character.

ASCII is a fixed-length code, since each character requires the same

number of bits to store.
Variable length codes

Notice that some characters, (e.g. q, x, z, v) are rare, and others (e.g.
e, s, t, a) are common.

It might make more sense to use less bits to store the common
characters, and more bits to store the rare characters.

An encoding that does this is called a variable length code.

A code is called optimal if the space required to store data with the
given distribution is a minimum.

Optimal codes are important for many applications.

Variable length code example

Assume a file has the following distribution of characters.

Letter A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13

One good encoding might be the following :

Letters A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13
Encoding 10 11 101 1 01 001 110 011

Thus, the string treat is encoded as 110111011

The problem with this encoding is that the string could also be ktve.
Variable length code example

Assume a file has the following distribution of characters.

Letter A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13

One good encoding might be the following :

Letters A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13
Encoding 10 11 101 1 01 001 110 011

With this code, we have to somehow keep track of which letter is

which.
(e.g. 11 01 1 10 11)

To do this requires more space, and may make the code worse than a
fixed-length code. Rather we use a prefix code.
Prefix codes

A code in which no word is a prefix of another word.

To encode a string of data, concatenate the codewords together.
To decode, just read the bits until a codeword is recognized.
Since no codeword is a prefix of another, this works.
Letters A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13
Encoding 00 100 11100 01 101 11101 1111 110

Notice that no codeword is the prefix of another.

Now, we can encode treat as 1001010100100, and it is uniquely
decodable.
Decoding prefix codes

Decode 01111011010010100100 based on the following decoding

table :
Letters A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13
Encoding 00 100 11100 01 101 11101 1111 110

The most obvious way is to read one bit, see if it is a character, read
another, see if the two are a character, etc. : not very efficient.
Decoding prefix codes

Letters A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13
Encoding 00 100 11100 01 101 11101 1111 110

A better way is to represent the encoding of each letter as a path in a

binary tree :
I Each leaf node stores a character.
I A ‘0’ means go to the left child
I A ‘1’ means go to the right child
I The process continues until a leaf is found.
Any code represented this way is a prefix code. Why ?
Decoding prefix code

Decode 01111011010010100100
Letters A T V E R Z K L
Frequency 20 15 3 23 19 2 7 13
Encoding 00 100 11100 01 101 11101 1111 110

We will represent the data by the following binary tree :

0 1
0 1 0 1
A E 0 1 0 1
T R L 0 1
0 1 K
V Z

It is now not too hard to see that the answer is ezrarat.

Constructing codes

Prefix codes make encoding and decoding data very easy.

It can be shown that optimal data compression using a character code

can be obtained using a prefix code.

How can we construct such a code ?

Huffman code is an algorithm to construct prefix codes

Huffman code

A Huffman code can be constructed by building the encoding tree from

the bottom-up in a greedy fashion.

Since the less frequent nodes should end up near the bottom of the
tree, it makes sense that we should consider these first.

We’ll see an example, then the algorithm.

Huffman code example

Suppose I want to store this very long word in an electronic

dictionary : floccinaucinihilipilification.

I want to store it using as few bits as possible.

The frequency of letters, sorted in decreasing order, is as follows :

i c l n f o a t h p u
9 4 3 3 2 2 2 1 1 1 1
Huffman code example

i c l n f o a t h p u
9 4 3 3 2 2 2 1 1 1 1

The algorithm works sort of like this :

I Consider each letter as a node in a not-yet-constructed tree.
I Label each node with its letter and frequency.
I Pick two nodes x and y of least frequency.
I Insert a new node, and let x and y be its children. Let its
frequency be the combined frequency of x and y .
I Take x and y off the list.
I Continue until only 1 node is left on the list.
Huffman example

9:i 4:c 3:l 3:n 2:f 2:o 2:a 1:t 1:h 1:p 1:u

9:i 4:c 3:l 3:n 2:f 2:o 2:a 2 1:t 1:h

1:p 1:u

9:i 4:c 3:l 3:n 2:f 2 2 2:o 2:a

1:t 1:h 1:p 1:u

9:i 4:c 4 3:l 3:n 2 2 2:f

1:t 1:h 1:p 1:u

2:o 2:a
 9:i 5 4:c 4 4 3:n
9:i 4:c 4 4 3:n 3:l 2

2:f 3:l 2 2:o 2:a 2 2:f

2:o 2:a 2 1:t 1:h

1:p 1:u 1:t 1:h 1:p 1:u

9:i 7 5 4:c 4
9:i 5 4:c 4 4 3:n

4 3:n 3:l 2 2:o 2:a

3:l 2 2:o 2:a 2 2:f

2 2:f 1:t 1:h

1:t 1:h 1:p 1:u

1:p 1:u

9:i 8 7 5

4:c 4 4 3:n 3:l 2

2:o 2:a 2 2:f 1:t 1:h

1:p 1:u
9:i 8 7 5 17 12

9:i 8 7 5
4:c 4 4 3:n 3:l 2

4:c 4 3:n 3:l 2

2 2:f 1:t 1:h 4
2:o 2:a
2 2:f 1:t 1:h
1:p 1:u 2:o 2:a

1:p 1:u

12 9:i 8 29

7 5 17 12
4:c 4
7 5
4 3:n 3:l 2 9:i 8
2:o 2:a
4:c 4 3:n 3:l 2
2 2:f 1:t 1:h 4

2 2:f 1:t 1:h

1:p 1:u 2:o 2:a

1:p 1:u

17 12
0 1
9:i 8 7 5
0 1 0 1
4:c 4 3:n 3:l 2 i
4
0 1 0 1 0 1
2 2:f 1:t 1:h c n
2:o 2:a l
0 1 0 1 0 1
1:p 1:u
o a f t h
0 1
p u
We can now list the code :
0 1

0 1 0 1
i
0 1 0 1 0 1
c n l
0 1 0 1 0 1
o a f t h
0 1
p u

i (9) 00 f (2) 1001

c (4) 010 t (1) 1110
n (3) 101 h (1) 1111
l (3) 110 p (1) 10000
o (2) 0110 u (1) 10001
a (2) 0111
Huffman encoding

We are given a list of n characters, each with some frequency.

For each character, we define a Node containing the character,
frequency, left, and right.
The nodes are stored using a data structure that supports the
operations Insert and Extract Min.
A priority queue, which is implemented using a heap, is a good
choice.

The algorithm for Huffman encoding will build a tree from the nodes in
a bottom-up fashion.
Huffman encoding algorithm & complexity analysis

The The List is a n characters list

each character with its own
Huffman Encoding(The List) frequency. Q is a min priority queue
Q = The List ; key on the frequency of the
/*Initialize the min priority queue */ characters
while (Q > 1)
z := New Tree Node ; The most costly operations are Q
x := Extract Min(Q) ; = The List which takes O(n) to
y := Extract Min(Q) ; build the heap, Insert and
left[z] := x ; Extract Min operations which run
right[z] := y ;
in O(log n). The while loop
f [z] := f [x] + f [y ] ;
Insert(Q,z) ;
iterates n − 1 times, therefore the
return Extract Min(Q) ; algorithm runs in O(n log n).
Exercises on Huffman code
1. You are given the following table of letters and their frequencies :
a :1 b :3 c :2 d :9 e :7
I Build the Huffman tree for this set of letters
I Give the optimal Huffman code for these letters
2. What is the optimal Huffman code for the following set of
frequencies : a :1 b :1 c :2 d :3 e :5 f :8 g :13 h :21
3. Write a frequency list of the Huffman code that creates the
following structure
Exercises on Huffman code

4. Encode the following sentence with a Huffman code : ”Common

sense is the collection of prejudices acquired by age eighteen”.
Write the complete construction of the code
5. Write a minimal character-based binary code for the following
sentence : ”in theory, there is no difference between theory and
practice ; in practice, there is”
The code must map each character, including spaces and
punctuation marks, to a binary string so that the total length of
the encoded sentence is minimal. Use a Huffman code and show
the derivation of the code.
Problem 1 : The Job Sequencing Problem

We are given an array of jobs where every job has a deadline and
associated profit if the job is finished before the deadline

Input: Four Jobs with following deadlines and profits

JobID Deadline Profit
a 4 20
b 1 10
c 1 40
d 1 30

Every job takes a single unit of time, so the minimum possible deadline
for any job is 1. The objective is to maximize the total profit when only
one job can be scheduled at a time

Design a greedy algorithm to solve this problem

The Job Sequencing Problem

Using your greedy algorithm, solve the following job sequencing

problem

Input: Five Jobs with following deadlines and profits

JobID Deadline Profit
a 2 100
b 1 19
c 2 27
d 1 25
e 3 15
problem 2 : Activity scheduling problem

Assume we have a set S of n activities with each of them being

represented by a start time si and finish time fi :

i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 8 9 10 11 12 13 14
Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi
(the two activities do not overlap).

The optimization problem is to maximize the number of

non-conflicting activities. Application : select the maximum number of
activities that can be performed by a single person or machine.

Design a greedy algorithm to solve this problem

Activity scheduling problem : a greedy algorithm

Greedy algo : Sort the activities in increasing order of their finish time
(greedy criterion). Then :
I Select the activity with the earliest finish
I Eliminate the activities that overlap with the selected activity
I Repeat !
Activity scheduling problem
i 1 2 3 4 5 6 7 8 9 10 11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 8 9 10 11 12 13 14

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Activity scheduling problem : greedy choice property

Let S = {1, 2, . . . , n} be the set of activities ordered by finish time.

Assume that A ⊆ S is an optimal solution, also ordered by finish time.

Assume the index of the first activity in A is k 6= 1, i.e., this optimal

solution does not start with the greedy choice.

We show that B = (A \ {k}) ∪ {1} which begins with the greedy

choice (activity 1), is another optimal solution.

Since f1 ≤ fk , and the activities in A are disjoint by definition, the

activities in B are also disjoint. Since B has the same number of
activities as A, that is |A| = |B|, then B is also optimal.
Activity scheduling problem : optimal substructure

Once the greedy choice is made, the problem reduces to finding an

optimal solution for a subproblem.

If A is an optimal solution to the original problem S, then A0 = A \ {1}

is an optimal solution to the activity-selection problem
S 0 = {i ∈ S : si ≥ f1 }.

Otherwise, if we could find a solution B 0 to S 0 with more activities

then A0 , adding 1 to B 0 would yield a solution B to S with more
activities than A, contradicting the optimality assumption of A.
Problem 3 : minimize average completion time

This is a scheduling problem which consists to minimize the average completion

time of tasks.

Given a set S = {t1 , t2 , . . . , tn } of tasks, where task ti requires pi units of processing

time to complete, once it has started. There is one computer on which to run these
tasks, and the computer can run only one task at a time. Let fi be the completion
time of task ti , that is, the time at which task ti completes processing. The
optimization
Pn problem is to minimize the average completion time, i.e. minimize
i=1 fi
n
.

Example : two tasks, t1 and t2 , p1 = 3 and p2 = 5. Assume t2 runs first, followed by

t1 . Then f2 = 5, f1 = 8, and the average completion time is 5+8
2
= 6.5. If task t1
runs first, then f1 = 3, f2 = 8, and the average completion time is 3+8
2
= 5.5

Give a greedy algorithm that schedules the tasks to minimize the average
completion time. Each task runs non-preemptively, once task ti starts, it must run
continuously for pi units of time.