CS代考 COMP3121/9101

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