Algorithms COMP3121/9101
THE UNIVERSITY OF
NEW SOUTH WALES
Copyright By PowCoder代写 加微信 powcoder
Algorithms
COMP3121/9101
School of Computer Science and Engineering
University of Wales Sydney
6. THE GREEDY METHOD
COMP3121/9101 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.
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/9101 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/9101 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/9101 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/9101 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/9101 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
Greedy strategy no longer works – we will need a more sophisticated
technique.
COMP3121/9101 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/9101 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 TelstraÕs 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/9101 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.
fi(1# fj(1#
COMP3121/9101 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
Recall the BubbleSort: if we manage to eliminate all inversions between
adjacent jobs, eventually all the inversions will be eliminated.
di% fi%fi+1%
Note that swapping adjacent inverted jobs reduces the larger lateness!
COMP3121/9101 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/9101 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
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/9101 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
=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/9101 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/9101 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/9101 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/9101 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/9101 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/9101 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/9101 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.
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
COMP3121/9101 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
Find also the set R ⊆ V of all vertices which are reachable in Grev from
The strongly connected component C of G containing v is just the set
Clearly, distinct strongly connected components are disjoint sets.
COMP3121/9101 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 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/9101 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/9101 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
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/9101 25 / 47
An augmented Priority Queue
1 2 3 4 5 6 7 8
i1 i2 i3 i4 i5 i6 i7 i8
6 4 5 2 3 1 7 8
Heap Array Index Array
COMP3121/9101 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
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/9101 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).
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/9101 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
COMP3121/9101 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.
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/9101 30 / 47
Dijkstra’s Shortest Paths Algorithm
How is this construction done efficientl
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com