NEW SOUTH WALES
Algorithms: COMP3121/9101
Aleks Ignjatovi ́c
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.
an-1
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)
a2
a1 ai an
si fi
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: Co!nsider 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.
!
T0#
fi(1# di#
fi# fj(1#
dj#
fj#
COMP3121/3821/9101/9801
10 / 47
More practice problems for the Greedy Method
Minimising job lateness
We will show that t!here exists a scheduling without inversions which is also
! ! !
!
T0%
optimal. RecalltheBubbleSo!rt:ifwemanagetoeliminateallinversionsbetween
adjacent jobs, eventually all the inversions will be eliminated.
di+1%
di%
fi)1%
fi%
di% fi)1% di+1%
fi+1%
fi+1%
fi%
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
Thisisminimisedifl1 ≤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, ni=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
LetX beasetofnintervalsontherealline. WesaythatasetP 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 ̸=σ2 thenthereexistsanedgefromσ1 toσ2 inE∗ 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
i6
1
Item
priority
i5
6
i4
2
i7
11
i2
3
i3
9
i1
7
I8
10
Heap Array Index Array
12345678
i1
i2
i3
i4
i5
i6
i7
i8
6
4
5
2
3
1
7
8
i6
i4
i5
i2
i3
i1
i7
i8
1
2
6
3
9
7
11
10
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).
path p’
path p
w
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!
v
z
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.
S after adding u
S before adding u
u
G
v
z
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.
S after adding u
S before adding u
G z
v
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.
S before adding u
S after adding u
u
z
G
v
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?
y v
x
u
z
G
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 ̸∈ 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:
p
q
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.
S
u
v
COMP3121/3821/9101/9801
33 / 47
Greedy Method for graphs: Minimum Spanning Trees
q
S
p
v
Since u ∈ S and v ̸∈ 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 ̸∈ 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.
u
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 ̸∈ 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 log m). 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 ̸= 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 log m) = 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 ̸∈Sj.
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 ̸∈ Sj.
Thus, vp+1 ∈ Sq for some q ̸= j.
COMP3121/3821/9101/9801 45 / 47
vm
vi
vp
Sj
vp+1
Sq
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