Scheduling to minimize average completion time Suppose you

Coin changing Consider the problem of making change for n cents using the fewest number of coins. Assume that each coins value is an integer. a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution. Problems for Chapter 16 447 b. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c0; c1;:::;ck for some integers c>1 and k 1. Show that the greedy algorithm always yields an optimal solution. c. Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n. d. Give an O.nk/-time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny.

Scheduling to minimize average completion time Suppose you are given a set S D fa1; a2;:::;ang of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai , that is, the time at which task ai completes processing. Your goal is to minimize the average completion time, that is, to minimize .1=n/Pn iD1 ci. For example, suppose there are two tasks, a1 and a2, with p1 D 3 and p2 D 5, and consider the schedule in which a2 runs first, followed by a1. Then c2 D 5, c1 D 8, and the average completion time is .5 C 8/=2 D 6:5. If task a1 runs first, however, then c1 D 3, c2 D 8, and the average completion time is .3 C 8/=2 D 5:5. a. Give an algorithm that schedules the tasks so as to minimize the average completion time. Each task must run non-preemptively, that is, once task ai starts, 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 cannot start until its release time ri. Suppose also that we allow preemption, so that a task can be suspended and restarted at a later time. For example, a task ai with processing time pi D 6 and release time ri D 1 might start running at time 1 and be preempted at time 4. It might then resume at time 10 but be preempted at time 11, and it might 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 has been divided into three pieces. In this scenario, ais completion time is 15. Give an algorithm that schedules the tasks so as to minimize the average completion time in this new scenario. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

Acyclic subgraphs a. The incidence matrix for an undirected graph G D .V; E/ is a jV j jEj matrix M such that M e D 1 if edge e is incident on vertex , and M e D 0 otherwise. Argue that a set of columns of M is linearly independent over the field of integers modulo 2 if and only if the corresponding set of edges is acyclic. Then, use the result of Exercise 16.4-2 to provide an alternate proof that .E; / of part (a) is a matroid. b. Suppose that we associate a nonnegative weight w.e/ with each edge in an undirected graph G D .V; E/. Give an efficient algorithm to find an acyclic subset of E of maximum total weight. c. Let G.V; E/ be an arbitrary directed graph, and let .E; / be defined so that A 2 if and only if A does not contain any directed cycles. Give an example of a directed graph G such that the associated system .E; / is not a matroid. Specify which defining condition for a matroid fails to hold. d. The incidence matrix for a directed graph G D .V; E/ with no self-loops is a jV j jEj matrix M such that M e D 1 if edge e leaves vertex , M e D 1 if edge e enters vertex , and M e D 0 otherwise. Argue that if a set of columns of M is linearly independent, then the corresponding set of edges does not contain a directed cycle. e. Exercise 16.4-2 tells us that the set of linearly independent sets of columns of any matrix M forms a matroid. Explain carefully why the results of parts (d) and (e) are not contradictory. How can there fail to be a perfect correspondence between the notion of a set of edges being acyclic and the notion of the associated set of columns of the incidence matrix being linearly independent?

Scheduling variations Consider the following algorithm for the problem from Section 16.5 of scheduling unit-time tasks with deadlines and penalties. Let all n time slots be initially empty, where time slot i is the unit-length slot of time that finishes at time i. We consider the tasks in order of monotonically decreasing penalty. When considering task aj , if there exists a time slot at or before aj s deadline dj that is still empty, assign aj to the latest such slot, filling it. If there 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 implement the algorithm efficiently. Assume that the set of input tasks has already been sorted into monotonically decreasing order by penalty. Analyze the running time of your implementation.

Off-line caching Modern computers use a cache to store a small amount of data in a fast memory. Even though a program may access large amounts of data, by storing a small subset of the main memory in the cachea small but faster memoryoverall access time can greatly decrease. When a computer program executes, it makes a sequence hr1; r2;:::;rni of n memory requests, where each request is for a particular data element. For example, a program that accesses 4 distinct elements fa; b; c; dg might make the sequence of requests hd; b; d; b; d; a; c; d; b; a; c; bi. Let k be the size of the cache. When the cache contains k elements and the program requests the .k C 1/st element, the system must decide, for this and each subsequent request, which k elements to keep in the cache. More precisely, for each request ri , the cache-management algorithm checks whether element ri is already in the cache. If it is, then we have a cache hit; otherwise, we have a cache miss. Upon a cache miss, the system retrieves ri from the main memory, and the cache-management algorithm must decide whether to keep ri in the cache. If it decides to keep ri and the cache already holds k elements, then it must evict one element to make room for ri. The cache-management algorithm evicts data with the goal of minimizing the number of cache misses over the entire sequence of requests. Typically, caching is an on-line problem. That is, we have to make decisions about which data to keep in the cache without knowing the future requests. Here, however, we consider the off-line version of this problem, in which we are given in advance the entire sequence of n requests and the cache size k, and we wish to minimize the total number of cache misses. We can solve this off-line problem by a greedy strategy called furthest-in-future, which chooses to evict the item in the cache whose next access in the request sequence comes furthest in the future. a. Write pseudocode for a cache manager that uses the furthest-in-future strategy. The input should be a sequence hr1; r2;:::;rni of requests and a cache size k, and the output should be a sequence of decisions about which data element (if any) to evict upon each request. What is the running time of your algorithm? b. Show that the off-line caching problem exhibits optimal substructure. c. Prove that furthest-in-future produces the minimum possible number of cache misses.