Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 78
Текст из файла (страница 78)
A faster implementation is given in Problem 16-4.Figure 16.7 gives an example of a problem of scheduling unit-time tasks with deadlinesand penalties for a single processor. In this example, the greedy algorithm selects tasksa1, a2, a3, and a4, then rejects a5 and a6, and finally accepts a7. The final optimalschedule isa2, a4, a1, a3, a7, a5, a6 ,which has a total penalty incurred of w5 + w6 = 50.Taskai1234567di4243146wi70605040302010Figure 16.7: An instance of the problem of scheduling unit-time tasks with deadlines and penalties fora single processor.Exercises 16.5-1Solve the instance of the scheduling problem given in Figure 16.7, but with each penaltywi replaced by 80 - wi.Exercises 16.5-2Show how to use property 2 of Lemma 16.12 to determine in time O(|A|) whether or not agiven set A of tasks is independent.Problems 16-1: Coin changingConsider the problem of making change for n cents using the fewest number of coins.Assume that each coin's value is an integer.a.
Describe a greedy algorithm to make change consisting of quarters,dimes, nickels, and pennies. Prove that your algorithm yields anoptimal solution.b. Suppose that the available coins are in the denominations that arepowers of c, i.e., the denominations are c0, c1, ..., ck for some integersc >; 1 and k ≥ 1.
Show that the greedy algorithm always yields anoptimal solution.c. Give a set of coin denominations for which the greedy algorithm doesnot yield an optimal solution. Your set should include a penny so thatthere is a solution for every value of n.d. Give an O(nk)-time algorithm that makes change for any set of kdifferent coin denominations, assuming that one of the coins is apenny.Problems 16-2: Scheduling to minimize average completion timeSuppose you are given a set S = {a1, a2, ..., an} of tasks, where task ai requires pi units ofprocessing time to complete, once it has started. You have one computer on which to runthese tasks, and the computer can run only one task at a time.
Let ci be the completiontime of task ai , that is, the time at which task ai completes processing. Your goal is tominimize the average completion time, that is, to minimize. For example,suppose there are two tasks, a1 and a2, with p1 = 3 and p2 = 5, and consider the schedulein which a2 runs first, followed by a1. Then c2 = 5, c1 = 8, and the average completion timeis (5 + 8)/2 = 6.5.a. Give an algorithm that schedules the tasks so as to minimize theaverage completion time.
Each task must run non-preemptively, thatis, once task ai is started, it must run continuously for pi units of time.Prove that your algorithm minimizes the average completion time,and state the running time of your algorithm.b. Suppose now that the tasks are not all available at once. That is,each task has a release time ri before which it is not available to beprocessed. Suppose also that we allow preemption, so that a taskcan be suspended and restarted at a later time. For example, a taskai with processing time pi = 6 may start running at time 1 and bepreempted at time 4. It can then resume at time 10 but be preemptedat time 11 and finally resume at time 13 and complete at time 15.Task ai has run for a total of 6 time units, but its running time hasbeen divided into three pieces.
We say that the completion time of aiis 15. Give an algorithm that schedules the tasks so as to minimizethe average completion time in this new scenario. Prove that youralgorithm minimizes the average completion time, and state therunning time of your algorithm.Problems 16-3: Acyclic subgraphsa. Let G = (V, E) be an undirected graph. Using the definition of amatroid, show that (E,ℓ) is a matroid, where A ∈ℓ if and only if A isan acyclic subset of E.b. The incidence matrix for an undirected graph G = (V, E) is a |V | ×|E| matrix M such that Mve = 1 if edge e is incident on vertex v, andMve = 0 otherwise. Argue that a set of columns of M is linearlyindependent over the field of integers modulo 2 if and only if thecorresponding set of edges is acyclic.
Then, use the result ofc.Exercise 16.4-2 to provide an alternate proof that (E,ℓ) of part (a) ismatroid.Suppose that a nonnegative weight w(e) is associated with eachedge in an undirected graph G = (V, E). Give an efficient algorithm tofind an acyclic subset of E of maximum total weight.d. Let G(V, E) be an arbitrary directed graph, and let (E,ℓ) be defined sothat A ∈ℓ if and only if A does not contain any directed cycles. Givean example of a directed graph G such that the associated system(E,ℓ) is not a matroid.
Specify which defining condition for a matroidfails to hold.e. The incidence matrix for a directed graph G = (V, E) is a |V |×|E|matrix M such that Mve = -1 if edge e leaves vertex v, Mve = 1 if edgee enters vertex v, and Mve = 0 otherwise.
Argue that if a set ofcolumns of M is linearly independent, then the corresponding set ofedges does not contain a directed cycle.f. Exercise 16.4-2 tells us that the set of linearly independent sets ofcolumns of any matrix M forms a matroid. Explain carefully why theresults of parts (d) and (e) are not contradictory.
How can there fail tobe a perfect correspondence between the notion of a set of edgesbeing acyclic and the notion of the associated set of columns of theincidence matrix being linearly independent?Problems 16-4: Scheduling variationsConsider the following algorithm for the problem from Section 16.5 of scheduling unit-timetasks with deadlines and penalties.
Let all n time slots be initially empty, where time slot iis the unit-length slot of time that finishes at time i. We consider the tasks in order ofmonotonically decreasing penalty. When considering task aj , if there exists a time slot ator before aj 's deadline dj that is still empty, assign aj to the latest such slot, filling it. Ifthere is no such slot, assign task aj to the latest of the as yet unfilled slots.a. Argue that this algorithm always gives an optimal answer.b.
Use the fast disjoint-set forest presented in Section 21.3 to implementthe algorithm efficiently. Assume that the set of input tasks hasalready been sorted into monotonically decreasing order by penalty.Analyze the running time of your implementation.Chapter notesMuch more material on greedy algorithms and matroids can be found in Lawler [196]and Papadimitriou and Steiglitz [237].The greedy algorithm first appeared in the combinatorial optimization literature in a1971 article by Edmonds [85], though the theory of matroids dates back to a 1935article by Whitney [314].Our proof of the correctness of the greedy algorithm for the activity-selection problem isbased on that of Gavril [112]. The task-scheduling problem is studied in Lawler [196],Horowitz and Sahni [157], and Brassard and Bratley [47].Huffman codes were invented in 1952 [162]; Lelewer and Hirschberg [200] surveysdata-compression techniques known as of 1987.An extension of matroid theory to greedoid theory was pioneered by Korte and Lovász[189, 190, 191, 192], who greatly generalize the theory presented here.Chapter 17: Amortized AnalysisOverviewIn an amortized analysis, the time required to perform a sequence of data-structure operationsis averaged over all the operations performed.
Amortized analysis can be used to show thatthe average cost of an operation is small, if one averages over a sequence of operations, eventhough a single operation within the sequence might be expensive. Amortized analysis differsfrom average-case analysis in that probability is not involved; an amortized analysisguarantees the average performance of each operation in the worst case.The first three sections of this chapter cover the three most common techniques used inamortized analysis. Section 17.1 starts with aggregate analysis, in which we determine anupper bound T (n) on the total cost of a sequence of n operations.
The average cost peroperation is then T (n)/n. We take the average cost as the amortized cost of each operation, sothat all operations have the same amortized cost.Section 17.2 covers the accounting method, in which we determine an amortized cost of eachoperation. When there is more than one type of operation, each type of operation may have adifferent amortized cost. The accounting method overcharges some operations early in thesequence, storing the overcharge as "prepaid credit" on specific objects in the data structure.The credit is used later in the sequence to pay for operations that are charged less than theyactually cost.Section 17.3 discusses the potential method, which is like the accounting method in that wedetermine the amortized cost of each operation and may overcharge operations early on tocompensate for undercharges later. The potential method maintains the credit as the "potentialenergy" of the data structure as a whole instead of associating the credit with individualobjects within the data structure.We shall use two examples to examine these three methods.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
