Algorithms: COMP3121/9101
THE UNIVERSITY OF
NEW SOUTH WALES
Algorithms:
COMP3121/9101
Aleks Ignjatović
School of Computer Science and Engineering
University of New South Wales
6. THE GREEDY METHOD
COMP3121/3821/9101/9801 1 / 47
The Greedy Method
Activity selection problem.
Instance: A list of activities ai, (1 ≤ i ≤ n) with starting times si and finishing
times fi. No two activities can take place simultaneously.
Task: Find a maximum size subset of compatible activities.
si fi
ai a1 an
an-1 a2
Attempt 1: always choose the shortest activity which does not conflict with the
previously chosen activities, remove the conflicting activities and repeat?
!
The above figure shows this does not work…
(chosen activities in green, conflicting in red)
COMP3121/3821/9101/9801 2 / 47
The Greedy Method
Activity selection problem.
Instance: A list of activities ai, (1 ≤ i ≤ n) with starting times si and finishing
times fi. No two activities can take place simultaneously.
Task: Find a maximum size subset of compatible activities.
Attempt 2: Maybe we should always choose an activity which conflicts with
the fewest possible number of the remaining activities? It may appear that in
this way we minimally restrict our next choice….
!
As appealing this idea is, the above figure shows this again does not work …
COMP3121/3821/9101/9801 3 / 47
The Greedy Method
The correct solution: Among the activities which do not conflict with the
previously chosen activities always chose the one with the earliest end time.
COMP3121/3821/9101/9801 4 / 47
Proving optimality of a greedy solution
Show that any optimal solution can be transformed into the greedy solution with
equal number of activities:
Find the first place where the chosen activity violates the greedy choice.
Show that replacing that activity with the greedy choice produces a non
conflicting selection with the same number of activities.
Continue in this manner till you “morph” your optimal solution into the
greedy solution, thus proving the greedy solution is also optimal.
!
COMP3121/3821/9101/9801 5 / 47
The Greedy Method
What is the time complexity of the algorithm?
We represent activities by ordered pairs of their starting and their
finishing times and sort them in an increasing order of their finishing
time (the second coordinate).
This takes O(n log n) time.
We go through such a sorted list in order, looking for the first activity
whose starting time is after the finishing time of the last taken activity.
Every activity is handled only once, so this part of the algorithm takes
O(n) time.
Thus, the algorithm runs in total time O(n log n).
COMP3121/3821/9101/9801 6 / 47
The Greedy Method
Activity selection problem II
Instance: A list of activities ai, (1 ≤ i ≤ n) with starting times si and
finishing times fi = si + d; thus, all activities are of the same duration.
No two activities can take place simultaneously.
Task: Find a subset of compatible activities of maximal total duration.
Solution: Since all activities are of the same duration, this is equivalent
to finding a selection with a largest number of non conflicting activities,
i.e., the previous problem.
Question: What happens if the activities are not all of the same
duration?
Greedy strategy no longer works – we will need a more sophisticated
technique.
COMP3121/3821/9101/9801 7 / 47
More practice problems for the Greedy Method
Along the long, straight road from Loololong to Goolagong houses are
scattered quite sparsely, sometimes with long gaps between two
consecutive houses. Telstra must provide mobile phone service to people
who live alongside the road, and the range of Telstra’s cell base station is
5km. Design an algorithm for placing the minimal number of base
stations alongside the road, that is sufficient to cover all houses.
COMP3121/3821/9101/9801 8 / 47
More practice problems for the Greedy Method
Once again, along the long, straight road from Loololong (on the West)
to Goolagong (on the East) houses are scattered quite sparsely,
sometimes with long gaps between two consecutive houses. Telstra must
provide mobile phone service to people who live alongside the road, and
the range of Telstras cell base station is 5km.
One of Telstra’s engineer started with the house closest to Loololong and
put a tower 5km away to the East. He then found the westmost house
not already in the range of the tower and placed another tower 5 km to
the East of it and continued in this way till he reached Goolagong.
His junior associate did exactly the same but starting from the East and
moving westwards and claimed that his method required fewer towers.
Is there a placement of houses for which the associate is right?
COMP3121/3821/9101/9801 9 / 47
More practice problems for the Greedy Method
Minimising job lateness
Instance: A start time T0 and a list of jobs ai, (1 ≤ i ≤ n), with duration
times ti and deadlines di. Only one job can be performed at any time; all jobs
have to be completed. If a job ai is completed at a finishing time fi > di then
we say that it has incurred lateness li = fi − di.
Task: Schedule all the jobs so that the lateness of the job with the largest
lateness is minimised.
Solution: Ignore job durations and schedule jobs in the increasing order of
deadlines.
Optimality: Consider any optimal solution. We say that jobs ai and jobs aj
form an inversion if job ai is scheduled before job aj but dj < di.
!
!
!
!
!
!
dj# di#
fi# fj#
T0#
fi(1# fj(1#
COMP3121/3821/9101/9801 10 / 47
More practice problems for the Greedy Method
Minimising job lateness
We will show that there exists a scheduling without inversions which is also
optimal.
Recall the BubbleSort: if we manage to eliminate all inversions between
adjacent jobs, eventually all the inversions will be eliminated.
!
!
!
!
!
!
di+1% di%
fi% fi+1%
di+1%
di% fi%fi+1%
T0%
fi)1%
fi)1%
Note that swapping adjacent inverted jobs reduces the larger lateness!
COMP3121/3821/9101/9801 11 / 47
More practice problems for the Greedy Method
Tape storage
Instance: A list of n files fi of lengths li which have to be stored on a tape.
Each file is equally likely to be needed. To retrieve a file, one must start from
the beginning of the tape and scan it until the file is found and read.
Task: Order the files on the tape so that the average (expected) retrieval time
is minimised.
Solution: If the files are stored in order l1, l2, . . . ln, then the expected time is
proportional to
l1 + (l1 + l2) + (l1 + l2 + l3) + . . . + (l1 + l2 + l3 + . . . + ln) =
nl1 + (n− 1)l2 + (n− 2)l3 + . . . + 2ln−1 + ln
This is minimised if l1 ≤ l2 ≤ l3 ≤ . . . ≤ ln.
COMP3121/3821/9101/9801 12 / 47
More practice problems for the Greedy Method
Tape storage II
Instance: A list of n files fi of lengths li and probabilities to be needed pi,∑n
i=1
pi = 1, which have to be stored on a tape. To retrieve a file, one must
start from the beginning of the tape and scan it until the file is fund and read.
Task: Order the files on the tape so that the expected retrieval time is
minimised.
Solution: If the files are stored in order l1, l2, . . . ln, then the expected time is
proportional to
p1l1 + (l1 + l2)p2 + (l1 + l2 + l3)p3 + . . . + (l1 + l2 + l3 + . . . + ln)pn
We now show that this is minimised if the files are ordered in a decreasing
order of values of the ratio pi/li.
COMP3121/3821/9101/9801 13 / 47
More practice problems for the Greedy Method
Let us see what happens if we swap to adjacent files fk and fk+1.
The expected time before the swap and after the swap are, respectively,
E =l1p1 + (l1 + l2)p2 + (l1 + l2 + l3)p3 + . . . + (l1 + l2 + l3 + . . . + lk−1 + lk)pk
+ (l1 + l2 + l3 + . . . + lk−1 + lk + lk+1)pk+1 + . . . + (l1 + l2 + l3 + . . . + ln)pn
and
E
′
=l1p1 + (l1 + l2)p2 + (l1 + l2 + l3)p3 + . . . + (l1 + l2 + l3 + . . . + lk−1 + lk+1)pk+1
+ (l1 + l2 + l3 + . . . + lk−1 + lk+1 + lk)pk + . . . + (l1 + l2 + l3 + . . . + ln)pn
Thus, E − E′ = lkpk+1 − lk+1pk, which is positive just in case
lkpk+1 > lk+1pk, i.e., if pk/lk < pk+1/lk+1.
Consequently, E > E′ if and only if pk/lk < pk+1/lk+1, which means that the
swap decreases the expected time just in case pk/lk < pk+1/lk+1, i.e., if there is
an inversion: a file fk+1 with a larger ratio pk+1/lk+1 has been put after a file
fk with a smaller ratio pk/lk.
For as long as there are inversions there will be inversions of consecutive files
and swapping will reduce the expected time. Consequently, the optimal
solution is the one with no inversions.
COMP3121/3821/9101/9801 14 / 47
More practice problems for the Greedy Method
Let X be a set of n intervals on the real line. We say that a set P of
points stabs X if every interval in X contains at least one point in P ; see
the figure below. Describe and analyse an efficient algorithm to compute
the smallest set of points that stabs X. Assume that your input consists
of two arrays XL[1..n] and XR[1..n], representing the left and right
endpoints of the intervals in X.
Is it a good idea to stab the largest possible number of intervals?
Hint: the interval which ends the earliest has to be stabbed.
What is the best place to stab it?
COMP3121/3821/9101/9801 15 / 47
The Greedy Method
0-1 knapsack problem
Instance: A list of weights wi and values vi for discrete items ai, 1 ≤ i ≤ n,
and a maximal weight limit W of your knapsack.
Task: Find a subset S of all items available such that its weight does not
exceed W and its value is maximal.
Can we always choose the item with the highest value per unit weight?
Assume there are just three items with weights and values: (10kg, $60),
(20kg, $100), (30kg, $120) and a knapsack of capacity W = 50kg.
Greedy would choose (10kg, $60) and (20kg, $100), while the optimal solution
is to take (20kg, $100) and (30kg, $120)!
So when does the Greedy Strategy work??
Unfortunately there is no easy rule...
COMP3121/3821/9101/9801 16 / 47
More practice problems for the Greedy Method
Assume you are given n sorted arrays of different sizes.
You are allowed to merge any two arrays into a single new sorted array
and proceed in this manner until only one array is left.
Design an algorithm that achieves this task and uses minimal total
number of moves of elements of the arrays and give an informal
justification why your algorithm is optimal.
This problem is somewhat related to the next application of the Greedy
method, which is, arguably, among the most important applications of
the greedy method!
COMP3121/3821/9101/9801 17 / 47
The most important applications of the Greedy Method:
The Huffman Code
Assume you are given a set of symbols, for example the English alphabet plus
punctuation marks and a blank space (to be used between words).
You want to encode these symbols using binary strings, so that sequences of
such symbols can be decoded in an unambiguous way.
One way of doing so is to reserve bit strings of equal and sufficient length,
given the number of distinct symbols to be encoded; say if you have 26 letters
plus 6 punctuation symbols, you would need strings of length 5 (25 = 32).
To decode a piece of text you would partition the bit stream into groups of 5
bits and use a lookup table to decode the text.
However this is not an economical way: all the symbols have codes of equal
length but the symbols are not equally frequent.
One would prefer an encoding in which frequent symbols such as ’a’, ’e’, ’i’ or
’t’ have short codes while infrequent ones, such as ’w’,’x’ and ’y’ can have
longer codes.
However, if the codes are of variable length, then how can we partition a
bitstream UNIQUELY into segments each corresponding to a code?
One way of insuring unique readability of codes from a single bitstream is to
ensure that no code of a symbol is a prefix of a code for another symbol.
Codes with such property are called the prefix codes.
COMP3121/3821/9101/9801 18 / 47
The most important applications of the Greedy Method:
The Huffman Code
We can now formulate the problem:
Given the frequencies (probabilities of occurrences) of each symbol, design an
optimal prefix code, i.e., a prefix code such that the expected length of an
encoded text is as small as possible.
Note that this amounts to saying that the average number of bits per symbol
in an “average” text is as small as possible.
We now sketch the algorithm informally; please see the textbook for details
and the proof of optimality.
COMP3121/3821/9101/9801 19 / 47
Greedy Method applied to graphs
There are n radio towers for broadcasting tsunami warnings. You are
given the (x, y) coordinates of each tower and its radius of range. When
a tower is activated, all towers within the radius of range of the tower
will also activate, and those can cause other towers to activate and so on.
You need to equip some of these towers with seismic sensors so that
when these sensors activate the towers where these sensors are located all
towers will eventually get activated and send a tsunami warning.
The goal is to design an algorithm which finds the fewest number of
towers you must equip with seismic sensors.
COMP3121/3821/9101/9801 20 / 47
Greedy Method applied to graphs
Someone has proposed the following two algorithms:
1 Algorithm 1: Find the unactivated tower with the largest radius (if
multiple with the same radius, pick the any of them). Activate this
tower. Find and remove all activated towers. Repeat.
2 Algorithm 2: Find the unactivated tower with the largest number of
towers within its range. If there is none, activate the leftmost tower.
Repeat.
Give examples which show that neither Algorithm 1 nor Algorithm 2
solve the problem correctly.
Design an algorithm which correctly solves the problem.
Solving this problem involves several important concepts which we now
revisit.
COMP3121/3821/9101/9801 21 / 47
Greedy Method applied to graphs
Given a directed graph G = (V,E) and a vertex v, the strongly connected
component of G containing v consists of all vertices u ∈ V such that
there is a path in G from v to u and a path from u to v.
How do we find a strongly connected component C ⊆ V containing u?
Construct another graph Grev = (V,Erev) consisting of the same set of
vertices V but with the set of edges Erev obtained by reversing the
direction of all edges E of G.
Use BFS to find the set D ⊆ V of all vertices in V which are reachable in
G from v.
Find also the set R ⊆ V of all vertices which are reachable in Grev from
v.
The strongly connected component C of G containing v is just the set
C = D ∩R.
Clearly, distinct strongly connected components are disjoint sets.
COMP3121/3821/9101/9801 22 / 47
Greedy Method applied to graphs
Let SG be the set of all strongly connected components of a graph G.
We define a graph Σ = (SG, E
∗) with vertices SG and directed edges E
∗
between the strongly connected components so that if σ1 ∈ SG and
σ2 ∈ SG and σ1 6= σ2 then there exists an edge from σ1 to σ2 in E∗ just
in case there exist a vertex u1 ∈ σ1 and a vertex u2 ∈ σ2 so that there
exists and edge from u1 to u2 in E.
Clearly, Σ = (SG, E
∗) is a directed acyclic graph, and thus allows a
topological sorting of vertices.
Topological sort of a directed acyclic graph is a linear ordering
(enumeration) of its vertices σi ∈ SG such that if there exists an edge
(σi, σj) ∈ E∗ then vertex σi precedes σj in such an ordering , i.e., i < j.
How do we topologically sort a directed acyclic graphs?
COMP3121/3821/9101/9801 23 / 47
Topological sorting
L← Empty list that will contain ordered elements
S ← Set of all nodes with no incoming edge
while S is non-empty do
remove a node u from S;
add u to tail of L;
for each node v with an edge e = (u, v) from u to v do
remove edge e from the graph;
if v has no other incoming edges then insert v into S;
if graph has edges left, then return error (graph has at least one cycle)
else return L (a topologically sorted order)
Now it should be easy to use the Greedy Strategy to solve the problem of
finding the fewest number of towers which you must equip with seismic
sensors, so that all emergency transmission towers get activated.
COMP3121/3821/9101/9801 24 / 47
An augmented Priority Queue
We will need a priority queue which allows an efficient change of the key
of an element in the queue, so we first need to extend the Heap data
structure.
We will use heaps represented by arrays; the left child of A[i] is stored in
A[2i] and the right child in A[2i+ 1].
We will store in heaps vertices of graphs with keys computed in various
ways; if a graph has n vertices we will label them with positive integers 1
to n.
Thus, every element of A is of the form (i, k(i)) where k(i) is the key of
element i.
Besides the array A which represents the heap, we will use another array
P of the same length which stores the position of elements in the heap;
thus A[P [i]] = (i, k(i)).
Changing the key of an element i is now an O(log n) operation: we look
up its position P [i] in A, change the key of the element in A[P [i]] and
then perform the Heappify operation to make sure the Heap property is
being preserved.
COMP3121/3821/9101/9801 25 / 47
An augmented Priority Queue
i8
10
i6
1
i4
2
i2
3
i5
6
i3
9
1 2 3 4 5 6 7 8
i1
7
i7
11
I8
10
Item
priority
i2
3
i7
11
i1
7
i3
9
i5
6
i4
2
i6
1
i1 i2 i3 i4 i5 i6 i7 i8
6 4 5 2 3 1 7 8
Heap Array Index Array
COMP3121/3821/9101/9801 26 / 47
Greedy Method applied to graphs: Shortest Paths
Some of the most important applications of the Greedy Strategy are in
graph algorithms.
Assume we are given a directed graph G = (V,E) with non-negative
weight w(e) ≥ 0 assigned to each edge e ∈ E.
We are also given a vertex v ∈ V .
For simplicity, we will assume that for every u ∈ V there is a path from v
to u.
The task is to find for every u ∈ V the shortest path from v to u.
This is accomplished by a very elegant greedy algorithm by Edsger
Dijkstra already in 1959!
COMP3121/3821/9101/9801 27 / 47
Greedy Method applied to graphs: Shortest Paths
We first prove a simple fact about shortest paths.
Consider a shortest path p in G from a vertex v to a vertex z (shown in
dark blue).
v z
w
path p
path p’
We claim that for every vertex w on that path, the shortest path from v
to w is just the truncation of the shortest path from v to z, ending at w.
Assume the opposite, that there is a shorter path from v to w (shown in
dashed light blue) which is not an initial segment of the shortest path
from v to z.
However, in that case we could remove the part of the shortest path
between v and z which is between v and w and replaced it with the light
blue shorter path from v to w, thus obtaining a shorter path from v to z.
Contradiction!
COMP3121/3821/9101/9801 28 / 47
Dijkstra’s Shortest Paths Algorithm
The algorithm builds a set S of vertices for which the shortest path has
been already established, starting with a single source vertex S = {v}
and adding one vertex at a time.
At each stage of the construction, we add the element u ∈ V \ S which
has the shortest path from v to u with all intermediate vertices already
in S.
v
u
z
G
S before
adding u
S after
adding u
COMP3121/3821/9101/9801 29 / 47
Dijkstra’s Shortest Paths Algorithm
Why does this produce a shortest path from v to u in G?
Assume the opposite, that there exists a shorter path from v to u in G.
By our choice of u such a path cannot be entirely in S
Let z be the first vertex outside S (as it was just prior to addition of u)
on such a shortest path.
v
u
z
G
S after
adding u
S before
adding u
Since there are no negative weight edges the path from v to such z would
be shorter than the path from v to u, contradicting our choice of u.
COMP3121/3821/9101/9801 30 / 47
Dijkstra’s Shortest Paths Algorithm
How is this construction done efficiently?
Initially all vertices except v are placed in a heap based priority queue
with additional Position array, with the weight w(v, u) if (v, u) ∈ E or ∞
as the key;
As we progress, the key of each element u will be updated with length
lhS,v(u) of the shortest path from v to u which has all intermediate
vertices on such a path in S.
v
u
z G
S after
adding u S before
adding u
We always pop the element u from the priority queue which has the
smallest key and add it to set S.
We then look for all elements z ∈ V \ S for which (u, z) ∈ E and if
lhS,v(u) + w(u, z) < lhS,v(z) we update the key of z to the value
lhS,v(u) + w(u, z).
COMP3121/3821/9101/9801 31 / 47
Dijkstra’s Shortest Paths Algorithm
Why is this enough; i.e., why the only shortest paths which could have
changed have u as the last vertex in S?
v
u
z G
x
y
Assume opposite that the shortest path to a vertex x has changed when
u was added, and that instead of u another node y was the last vertex
before x on such a new shortest path.
However, this is not possible because it would produce a shortest path to
y with a vertex u on that path not belonging to set S before adding u.
If graph G has n vertices and m edges, then each edge is inspected only
once, when it is an outgoing edge from the most recently added vertex;
updating a vertex key takes O(log n) many steps.
Thus, in total, the algorithm runs in time O(m log n).
COMP3121/3821/9101/9801 32 / 47
Greedy Method for graphs: Minimum Spanning Trees
Definition: A minimum spanning tree T of a connected graph G is a
subgraph of G (with the same set of vertices) which is a tree, and among
all such trees it is of minimal total length of all edges in T .
Lemma: Let G be a connected graph with all lengths of edges E of G
distinct and S a non empty proper subset of the set of all vertices V of
G. Assume that e = (u, v) is an edge such that u ∈ S and v 6∈ S and is of
minimal length among all the edges having this property. Then e must
belong to every minimum spanning tree T of G.
Proof:
S
p
q
v u
Assume opposite, that there exists a
minimum spanning tree which does not
contain such an edge e = (u, v).
Since T is a spanning tree, there exists a
path from u to v within such a tree.
COMP3121/3821/9101/9801 33 / 47
Greedy Method for graphs: Minimum Spanning Trees
S
p
q
v u
Since u ∈ S and v 6∈ S, this
path must have left S at a
certain point.
Assume that p is the last
vertex on this path which
is in S and q 6∈ S the
vertex immediately after p
on that path.
However, the edge (p, q) belongs
to T and must have a length
larger than the edge (u, v) (which
is the minimal length edge with
one end in S and one end outside
S.
Adding the edge e = (u, v) to
such a path from u to v produces
a loop which is removed by
removing the edge (p, q).
However, since by assumption the
weight of edge (u, v) is smaller
than the weight of edge (p, q), this
would result in a spanning tree of
smaller weight, contradicting our
assumption that T is a minimum
spanning tree.
COMP3121/3821/9101/9801 34 / 47
Greedy Method for graphs: Minimum Spanning Trees
The Kruskal Algorithm
We order the edges E in a non-decreasing order with respect to their
weights.
We build a tree by adding edges, one at each step of construction.
An edge ei is added at a round i of construction whenever its addition
does not introduce a cycle in the graph constructed thus far.
If adding an edge does introduce a cycle, that edge is discarded.
The process terminates when the list of all edges has been exhausted.
COMP3121/3821/9101/9801 35 / 47
Minimum Spanning Trees: the Kruskal Algorithm
Claim: The Kruskal algorithm produces a minimal spanning tree, and if all
weights are distinct, then such a Minimum Spanning Tree is unique.
Proof: We consider the case when all weights are distinct.
Consider an arbitrary edge e = (u, v) added in the course of the Kruskal
algorithm.
Consider the set S of all vertices w such that there exists a path from u
to w using only the subset of edges that have been added by the Kruskal
algorithm until just before the edge e = (u, v) has been added.
Then clearly u ∈ S but v 6∈ S.
Until this moment no edge with one end in S and the other outside S
has been considered because otherwise it would have been added, not
forming a cycle.
Consequently, edge e = (u, v) is the shortest one with such a property
and by the previous lemma it must belong to every spanning tree.
Thus, the set of edges produced by the Kruskal algorithm is a subset of
the set of edges of every spanning tree.
But the structure produced by the Kruskal algorithm is clearly cycle-free
and it spans the graph, otherwise another edge could be added.
COMP3121/3821/9101/9801 36 / 47
Efficient implementation of the Kruskal Algorithm
To efficiently implement the Kruskal algorithm, we need a useful data
structure for storing sets of elements, called the Union-Find.
Such a data structure has to support three operations:
1 MakeUnionFind(S), which, given a set S returns a strucure in
which all elements are placed into distinct singleton sets. Such an
operation should run in time O(n) where n = |S|.
2 Find(v), which, given an element v returns the (label of the) set to
which v belongs. Such operation should run either in time O(1) or
time O(log n) as we explain later.
3 Union(A,B), which, given (the labels of) two sets A,B changes the
data structure by replacing sets A and B with the set A ∪B. A
sequence of k consecutive Union operations should run in time
O(k log k).
COMP3121/3821/9101/9801 37 / 47
Efficient implementation of the Kruskal Algorithm
Note that we do not give the run time of a single Union operation but of
a sequence of k consecutive such operations.
Such time complexity analysis is called amortized analysis; it
(essentially) estimates average cost of an operation in a sequence of
operations, in this case log k.
We will label each set by one of its elements. Since we will use the
Union-Find data structure to keep track of sets of vertices of graphs, we
can assume that the underlying set S is of the form S = {1, 2, . . . , n}.
The simplest implementation of the Union-Find data structure consists
of:
1 an array A such that A[i] = j means that i belongs to set labeled j;
2 an array B such that B[i] contains the number of elements in the
set labeled by i (which can be 0) and pointers to the first and last
element of a linked list of elements of the set labeled by i.
COMP3121/3821/9101/9801 38 / 47
Efficient implementation of the Kruskal Algorithm
Union(i,j) of two sets labeled by i and j, respectively, is defined as
follows:
if number of elements in the set labeled by i is larger or equal to the
number of elements in the set labeled by j then labels in array A of
all elements in the set labeled by j is changed to i and array B is
updated accordingly;
if the set labeled by j has more elements than the set labeled by i,
then the labels of all elements in the set labeled by i are changed to
j and array B is updated accordingly.
Note that this definition implies that if Union(i, j) changes the label of
the set containing an element m, then the new set containing m will have
at least twice the number of elements of the set which contained m
before the Union(i, j) operation.
COMP3121/3821/9101/9801 39 / 47
Efficient implementation of the Kruskal Algorithm
Any sequence of k initial consecutive Union operations can touch at
most 2k elements of S (which happens if all Union operations were
applied to singleton sets).
Thus, the set containing an element m after k initial consecutive Union
must have at most 2k elements.
Since every Union operation which changes the label of the set
containing m at least doubles the size of the set containing that element,
the label of the set containing m could change fewer than log 2k many
times.
Thus, since we have at most 2k elements, any sequence of k initial
consecutive Union operations will have in total fewer than 2k log 2k
many label changes in A and each Union operation changes just a few
pointers in B and adds up the sizes of sets.
COMP3121/3821/9101/9801 40 / 47
Efficient implementation of the Kruskal Algorithm
Thus, every sequence of k initial consecutive Union operations has time
complexity of O(k log k).
Such Union-Find data structure is good enough to get the sharpest
possible bound on the run time of the Kruskal algorithm.
See the textbook for an Union-Find data structure based on pointers and
path compression, which further reduces the amortised complexity of the
Union operation at the cost of increasing the complexity of the Find
operation from O(1) to O(log n).
COMP3121/3821/9101/9801 41 / 47
Efficient implementation of the Kruskal Algorithm
We now use the previously described Union-Find data structure to
efficiently implement the Kruskal algorithm on a graph G = (V,E) with
n vertices and m edges.
We first have to sort m edges of graph G which takes time O(m logm).
Since m ≤ n2, this step of the algorithm also takes
O(m log n2) = O(m log n).
As we progress through the Kruskal algorithm execution, we will be
making connected components which will be merged into larger
connected components until all vertices belong to a single connected
component. For this purpose we use Union-Find data structure to keep
track the connected components constructed thus far.
For each edge e = (v, u) on the sorted list of edges we use two Find
operations, Find(u) and Find(v) to determine if vertices u and v belong
to the same component.
COMP3121/3821/9101/9801 42 / 47
Efficient implementation of the Kruskal Algorithm
If they do not belong to the same component, i.e., if Find(u) = i and
Find(v) = j, j 6= i, we add edge e = (u, v) to the spanning tree being
constructed and perform Union(i, j) to place u and v into the same
connected component.
In total we perform 2m Find operations, each costing O(1), in total
costing O(m).
We also perform n− 1 Union operations which in total cost O(n log n).
Initial sorting of edges takes O(m logm) = O(m log n2) = O(m log n)
operations; thus, we obtain an overall time complexity of O(m log n).
COMP3121/3821/9101/9801 43 / 47
More applications of the Greedy Method
k-clustering of maximum spacing
Instance: A complete graph G with weighted edges representing distances
between the two vertices.
Task: Partition the vertices of G into k disjoint subsets so that the minimal
distance between two points belonging to different sets of the partition is as
large as possible. Thus, we want a partition into k disjoint sets which are as
far apart as possible.
Solution: Sort the edges in an increasing order and start performing the usual
Kruskal’s algorithm for building a minimal spanning tree, but stop when you
obtain k connected components, rather than a single spanning tree.
Proof of optimality: Let d be the distance associated with the first edge of
the minimal spanning tree which was not added to our k connected
components; it is clearly the minimal distance between two vertices belonging
to two of our k connected. Clearly, all the edges included in k many connected
components produced by our algorithm are of length smaller or equal to d.
COMP3121/3821/9101/9801 44 / 47
The Greedy Method
k-clustering of maximum spacing
Consider any partition S into k subsets different from the one produced by our
algorithm.
This means that there is a connected component produced by our algorithm
which contains vertices vi and vm such that vi ∈ Sj for some Sj ∈ S and
vm 6∈ Sj .
vi vp
vp+1
vm
Sj
Sq
Since vi and vm belong to the same connected component, there is a path in
that component connecting vi and vm.
Let vp and vp+1 be two consecutive vertices on that path such that vp belongs
to Sj and vp+1 6∈ Sj .
Thus, vp+1 ∈ Sq for some q 6= j.
COMP3121/3821/9101/9801 45 / 47
The Greedy Method
Note that d(vp, vp+1) ≤ d which implies that the distance between these
two clusters Sj , Sq ∈ S is smaller or equal to the minimal distance d
between the k connected components produced by our algorithm.
Thus, such a partition cannot be a more optimal clustering than the one
produced by our algorithm.
What is the time complexity of this algorithm?
We have O(n2) edges; thus sorting them by weight will take
O(n2 log n2) = O(n2 log n).
While running the (partial) Kruskal algorithm we use the Union-Find
data structure which requires O(n2 log n) steps.
So the grand total for the whole algorithm is O(n2 log n) many steps.
COMP3121/3821/9101/9801 46 / 47
PUZZLE!!
Bob is visiting Elbonia and
wishes to send his teddybear to
Alice who is staying at a different
hotel. Both Bob and Alice have
boxes like the one shown on the
picture as well as padlocks which
can be used to lock the boxes.
However, there is a problem.
The Elbonian postal service mandates
that boxes to be sent, if not empty,
must be locked, but they do not allow
keys to be sent. The key must remain
with the sender. You can send padlocks
only if they are locked. How can Bob
safely send his teddybear to Alice?
Hint: The way how the boxes are
locked (via a padlock) is important as
well as that both Bob and Alice have
padlocks and boxes. They can also
communicate over the phone to agree
on the strategy. There are two possible
solutions; one can be called the “AND”
solution, the other can be called the
“OR” solution. The “AND” solution
requires 4 mail one way services while
the “OR” solution requires only 2.
COMP3121/3821/9101/9801 47 / 47