College life is hard. You are given n assignments a,..., an in your courses. Each assign-...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
College life is hard. You are given n assignments a,..., an in your courses. Each assign- ment a; = (di, t;) has a deadline d; when it is due and an estimated amount of time it will take to complete, t. You would like to get the most out of your college education, and so you plan to finish all of your assignments. Let us assume that when you work on one assignment, you give it your full attention and do not work on any other assignment. In some cases, your outrageous professors demand too much of you. It may not be possi- ble to finish all of your assignments on time given the deadlines d,..., dni indeed, some assignments may have to be turned in late. Your goal as a sincere college student is to minimize the lateness of any assignment. If you start assignment a; at time si, you will finish at time fi = S; +ti. The lateness value denoted 'l;' for a; is the value fi-di 0 if fi > di otherwise Devise a polynomial time algorithm that computes a schedule O that specifies the order in which you complete assignments which minimizes the maximum 1; for all assignments, i.e., min max 1; Oi (1) In other words, you do not want to turn in any assignment too late, so you minimize the lateness of the latest assignment you turn in. Discuss in detail or explain that your algorithm produces an optimal schedule. Analyze the running time of your algorithm. Hint: The solution is very similar to the scheduling problem discussed in class. 3 points for the algorithm, 2 points for explanation. College life is hard. You are given n assignments a,..., an in your courses. Each assign- ment a; = (di, t;) has a deadline d; when it is due and an estimated amount of time it will take to complete, t. You would like to get the most out of your college education, and so you plan to finish all of your assignments. Let us assume that when you work on one assignment, you give it your full attention and do not work on any other assignment. In some cases, your outrageous professors demand too much of you. It may not be possi- ble to finish all of your assignments on time given the deadlines d,..., dni indeed, some assignments may have to be turned in late. Your goal as a sincere college student is to minimize the lateness of any assignment. If you start assignment a; at time si, you will finish at time fi = S; +ti. The lateness value denoted 'l;' for a; is the value fi-di 0 if fi > di otherwise Devise a polynomial time algorithm that computes a schedule O that specifies the order in which you complete assignments which minimizes the maximum 1; for all assignments, i.e., min max 1; Oi (1) In other words, you do not want to turn in any assignment too late, so you minimize the lateness of the latest assignment you turn in. Discuss in detail or explain that your algorithm produces an optimal schedule. Analyze the running time of your algorithm. Hint: The solution is very similar to the scheduling problem discussed in class. 3 points for the algorithm, 2 points for explanation.
Expert Answer:
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these human resource management questions
-
Adds a runner to the object array called arrayRunners. I want to make it so that if the object parameter (the runner) already exists in the array it returns an error message which is below. My code...
-
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...
-
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...
-
John Black is considering to purchasing a land from Real Estate Ltd for $1,000,000. The terms of the agreement are, 10% down payment, and the balance is to be repaid at 20% interest for duration of...
-
What country produces most of the worlds other gemstones (ruby, sapphire, and others)?
-
PC Connection is a leading mail-order retailer of personal computers. A recent financial report issued by the company revealed the following information. Merchandise inventory (beginning of the...
-
The following table presents residual heat flows in the enthalpy cascade of a process computed at \(\Delta T_{\text {min }}=10^{\circ} \mathrm{C}\) (Smith, 2005): (a) It is desired to efficiently...
-
Alice Guth operates a low-impact aerobics studio. Alice has been in business for three years and has always had her financial statements prepared on a cash basis. This year, Alices accountant has...
-
Describe the situation from either your professional experience or your research in which unethical or fraudulent behavior occurred. If you are describing an example from experience, please do not...
-
Refer to the Big Rig Rental Company case. Design a spreadsheet that will allow the firm to determine the Net Present Value of cash flows over the five-year period. The following exercises refer to...
-
The use of values as used in standards and limits purposely to protect a large number of workers from experiencing the health effects due to hazards. (a) Briefly explain the differences between...
-
Failure to follow the directions will lead to a grade deduction o The Exam must be handwritten o You are to choose and handwrite 2 essays for the exam from the list below Each essay will have a...
-
"A bottle of water can be 50 cents at a supermarket. $2 at the gym, $3 at the movies and $6 on a plane. Same water! Only thing that changed its value was the place." Please use what you've learned in...
-
Given functions f(x) = notation. f(x) Domain of : g(x) and g(x) = x-4, state the domains of the following functions using interval Domain of f(g(x)) (-00,-2) u (2,00) Domain of g(f(x)) (0,0)
-
Prepare the user documentation using the flowcharts created. User documentation should include an overview of menus and data entry screens, contents, options, and processing instructions. Review the...
-
How do advances in process intensification and microfluidic technologies enable the development of compact and modular separation systems with reduced footprint and improved efficiency, suitable for...
-
Which of the following statements about network economics is not true? OA. The law of diminishing returns does not always apply to every situation. OB. In network economics, the marginal cost of...
-
Assume you are the accountant for Catalina Industries. John Catalina, the owner of the company, is in a hurry to receive the financial statements for the year ended December 31, 20X1, and asks you...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
In the 2012 tax year, Michelle paid the following amounts relating to her 2010 tax return: Tax deficiency..........................................$5,000 Negligence...
-
Quince Corporation has taxable income of $450,000 for its 2012 calendar tax year. Calculate the corporation's income tax liability for 2012 before tax credits. $_________
-
Scores for the California Peace Officer Standards and Training test are normally distributed, with a mean of 50 and a standard deviation of 10. An agency will only hire applicants with scores in the...
-
1. Find the z-score that corresponds to a cumulative area of 0.3632. 2. Find the z-score that has 10.75% of the distributions area to its right.
-
Find the z-score that corresponds to each percentile. 1. P 5 2. P 50 3. P 90
Study smarter with the SolutionInn App