Bob is given n assignments to do, each with a length and a deadline. That is,...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Bob is given n assignments to do, each with a length and a deadline. That is, assignment i corresponds to a length , and a deadline d; (both positive integers; you can assume all deadlines are distinct). But Bob doesn't multitask well, and must do his assignments one after the other: he cannot start an assignment unless he's done with the one he was working on before (and, of course, cannot start earlier than day 1). Unfortunately, if any of the assignments is completed more than k days after its deadline, Bob gets 0 on that assignment which he wants to avoid! So he needs to come up with an ordering of the assignments (i.e., in which order to do the n assign- ments), such that no assignment is completed more than k days after its deadline, it one exists. (Bob does not rest between assignments: he starts a new one as soon as the previous is done...) Example: If the assignments are (₁,d₁) = (2,6), (l2, d2) = (4,4), and (3, d3) = (3,10) (so, n = 3) and k = 1, then a feasible schedule exists and could be (2,1,3), since starting with A2 on day 1 means finishing on day 1+ ₂ = 5 ≤ d₂ + k, then starting A1 on day 5 means finishing on day 5+ 1 = 7 ≤ d₁+k, and starting A3 on day 7 means finishing on day 7+ 3 = 10 ≤ 11=d3 +k. Day 1 (start) 4 days A2, due on Day 4 2 days A1, due Day 6 Day 5 Day 7 3 days A3, due Day 10 Day 10 Note that if in the above example we change k to 0, there would no longer exist a feasible ordering, as A2 cannot be completed before its deadline plus k = 0 days. a) Describe your algorithm in plain English. b) Prove the correctness of your algorithm. c) Analyze the time complexity of your algorithm. Your task is to give an algorithm for this problem that runs in O(n logn) time (i.e., its running time does not depend on k) and returns such an ordering, if it exists. If no ordering exists, you should report that as well. Remember to: Bob is given n assignments to do, each with a length and a deadline. That is, assignment i corresponds to a length , and a deadline d; (both positive integers; you can assume all deadlines are distinct). But Bob doesn't multitask well, and must do his assignments one after the other: he cannot start an assignment unless he's done with the one he was working on before (and, of course, cannot start earlier than day 1). Unfortunately, if any of the assignments is completed more than k days after its deadline, Bob gets 0 on that assignment which he wants to avoid! So he needs to come up with an ordering of the assignments (i.e., in which order to do the n assign- ments), such that no assignment is completed more than k days after its deadline, it one exists. (Bob does not rest between assignments: he starts a new one as soon as the previous is done...) Example: If the assignments are (₁,d₁) = (2,6), (l2, d2) = (4,4), and (3, d3) = (3,10) (so, n = 3) and k = 1, then a feasible schedule exists and could be (2,1,3), since starting with A2 on day 1 means finishing on day 1+ ₂ = 5 ≤ d₂ + k, then starting A1 on day 5 means finishing on day 5+ 1 = 7 ≤ d₁+k, and starting A3 on day 7 means finishing on day 7+ 3 = 10 ≤ 11=d3 +k. Day 1 (start) 4 days A2, due on Day 4 2 days A1, due Day 6 Day 5 Day 7 3 days A3, due Day 10 Day 10 Note that if in the above example we change k to 0, there would no longer exist a feasible ordering, as A2 cannot be completed before its deadline plus k = 0 days. a) Describe your algorithm in plain English. b) Prove the correctness of your algorithm. c) Analyze the time complexity of your algorithm. Your task is to give an algorithm for this problem that runs in O(n logn) time (i.e., its running time does not depend on k) and returns such an ordering, if it exists. If no ordering exists, you should report that as well. Remember to:
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
sExplore the relationship between deadlock and resource management policies. How can proper resource management help in reducing the likelihood of deadlock in large-scale systems?
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
The Crazy Eddie fraud may appear smaller and gentler than the massive billion-dollar frauds exposed in recent times, such as Bernie Madoffs Ponzi scheme, frauds in the subprime mortgage market, the...
-
What is the potential difference across one wire of a 30-m extension cord made of 16-gauge copper wire carrying a current of 5.0 A?
-
You are a sales representative who is contacting a prospective client you have never met. You want to introduce yourself and your product or service via email and set up a time to discuss things...
-
Lane Confectioners produces special orders of sugar candies and chocolates for airlines and hotels. During March, Lane purchased, on credit, 2,100 pounds of confectioners sugar at $.80 per pound,...
-
Mama Leona s Frozen Pizza Inc. has determined from its production budget the following estimated production volumes for 12 and 16 frozen pizzas for August: Prepare a direct materials purchases budget...
-
The production department in a process manufacturing system completed 191,500 units of product and transferred them to finished goods during a recent period. Of these units, 31,500 were in process at...
-
LG3 LG4 P11-11 Calculating initial cash flow Vastine Medical Inc. is replacing its computer system, which was purchased two years ago at a cost of $325,000. The system can be sold today for $200,000....
-
Phil Williams and Liz Johnson are 60% and 40% partners, respectively, in Williams & Johnson Partnership. Their beginning basis is $33,000 for Phil and $31,000 for Liz. The partnership had the...
-
You pay $58 to rent a hotel room, but if you rent more than one room, you get a discount of $5 per room for each additional room rented. (a) If you rent 3 rooms, how much will each one cost? $ 48 (b)...
-
Modern Golf (MG) is investigating the takeover of Pure Club Design (PCD). MG is using the discounted cash flow technique for determining PCD's takeover value and expects to achieve economies of scale...
-
Alice is going on a picnic and is aware that it will be easier to carry the picnic basket if it balances at the center where the handle is attached. She has placed a 1.75-kg container of potato salad...
-
The following statements about "adjusted ordinary gross income" ( AOGI ) are all true, except: a . If AOGI is less than twice adjusted rent, the rent is not PHCI. b . AOGI is the base in the 6 0...
-
Solve the polynomial equation in the complex numbers. x+6x3+6x+6x+5=0 The solution set is (Type an exact answer, using radicals as needed. Express complex numbers in terms of i. Use a comma to...
-
8. Find the reference angle ref if = 240. 17 9. Find the reference angle ref if = 10 10. Find the least positive coterminal angle if 0 = 1895.
-
Required precision: 2 digits after decimal point for money (dollar) calculation; 4 digits after decimal point for other (year and ratio etc.) calculations and correspondingly, 2 digits after decimal...
-
Wimot Trucking Corporation uses the units-of-production depreciation method because units-of-production best measures wear and tear on the trucks. Consider these facts about one Mack truck in the...
-
Is the operation of deletion "commutative" in the sense that deleting x and then y from a binary search tree leaves the same tree as deleting y and then x? Argue why it is or give a counterexample.
-
Using Figure 8.2 as a model, illustrate the operation of COUNTING-SORT on the array A = ?6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2?. Figure 8.2 1 2 3 4 5 6 7 8 1 2 3 4 6 7 8 A 2 53 02 3 0 3 0 1 2 3 4 5 c 2 2 4...
-
During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. We call such a set persistent. One way to implement a persistent set is...
-
Critic Ivor Smallbrain is watching the horror movie Salamanders on a Desert Island. In the film, there are 30 salamanders living on a desert island: 15 are red, 7 blue and 8 green. When two of a...
-
Find \(n\), given that both \(n\) and \(\sqrt{n-2}+\sqrt{n+2}\) are positive integers.
-
Environmental Business Consultants, LLC (EBC) has a contract with Terrabean Coffee, a large retail coffee company with 5,000 shops across North America, to manage the companys waste disposal and...
Study smarter with the SolutionInn App