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?
-
Your car is traveling behind a jeep. Both are moving at the same speed, so the velocity of the jeep relative to you is zero. A spare tire is strapped to the back of the jeep. Suddenly the strap...
-
Which of these statements about share dividends is true? (a) A credit entry should be made to retained earnings for the dollar amount of the shares issued. (b) A share dividend increases share...
-
Under all methods except MACRS, an asset purchased in any month other than January has first-year and last-year depreciation amounts that are prorated from the month the asset was purchased....
-
What difference does it make to the VaR calculated in Example 22.2 if the exponentially weighted moving average model is used to assign weights to scenarios as described in Section 13.3?
-
shown. Describe the transformation. (Example 4) L(0, 0) L'(0, 0) M(-4, 1)M'(-4, -1) N(-1, 3)N'(-1,-3)
-
Jane Company purchased merchandise . The following information is available: Terms: 15/10 n /60 Original purchase amount: $ 7,000 Return amount: $ 1,000 (2 days after purchase ) Payment of cash: Paid...
-
Regression analysis was performed on Demographics data using unemployment rate as the dependent variable and cost of living index as the independent variable. Compute and analyze the residuals to...
-
Management functions would not be complete without the activities of the human resource department. Important to the function of the organization is the human resource management activities. It is...
-
My name is Liynnette Cruz, I am the mother of two children named Giezy and Lily. Classify each sentence as simple, compound, complex, or compound-complex. Compound Complex Simple Compound-Complex
-
The following transactions took place in the books of Techno during September 2 0 2 3 : Techno, a registered VAT vendor, is a technology company that deals with the purchasing and selling of tech...
-
How can OB concepts be applied and extended to solve the problem? What specific action steps should the organization take to solve the problem? What changes should be implemented? Using data from...
-
"Discuss the evolution of business management systems in the context of technological advancements and their impact on organizational efficiency and competitiveness. Analyze the transition from...
-
A pet store has recently renovated in order to have more space to stock a wider selection of products. They'd like to add another brand of dog food to their available offerings. They want the new...
-
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...
-
The payback period of the investment proposal presented in question 4 is: a. 0.37 years b. 0.50 years c. 2.00 years d. 2.67 years
-
The Pepper Shop is evaluating a capital expenditure proposal with the following predicted cash flows: At a discount rate of 12 percent, the project's net present value is: a. $2,375 b. \($5,555\) C....
-
The accounting rate of return on the initial investment presented in question 4 is: a. 0.125 b. 0.156 C. 0.219 d. 0.375
Study smarter with the SolutionInn App