A bank manager has n clients waiting to be served, all of whom arrived at the...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
A bank manager has n clients waiting to be served, all of whom arrived at the same time. Let us call the time at which these clients arrive to be 0. The manager estimates that client i requires t; time units of service. They also know the clients well and assign each client a weight according to how important the client is to the bank (say, the outstanding balance of their bank account): client i has weight w;. The manager would like to determine a good order in which to serve the clients. In a given order, define the delay of client i to be the time at which client i starts getting served. The total weighted delay of a given order is the sum, over each client i, of the product of w; and the delay of i. The goal of this problem is to determine an order to serve the clients that minimizes the total weighted delay. For example, consider 4 clients with t = 5, t = 2, t3 = 7, t4 = 4. And weights w = 1, w = 3, w3 = 2, and w4 = 2. Consider the order 1,3,2,4. The delay for client 1 is 0, for client 2 is t + t3 = 5 + 7 = 12, for client 3 is t = 5, and for client 4 is t +13 + t = 5+7 +2 = 14. The total weighted delay of the order is then 1.0+3.12+2.5+214=36+10+28 = 74. (a) Describe precisely what your algorithm is given as input and what it needs to output. (b) Prove the following greedy choice property for the problem of finding an order that minimizes the total weighted delay: there exists an optimal solution in which the first client to be served is the client i that has the smallest value of t;/w;. (Hint: Start by proving the statement when there are only two clients. Extend to the general case using an exchange argument.) (c) Based on the claim of part (b), give a greedy algorithm to determine an order that mini- mizes total weighted delay. Describe your algorithm in pseudocode. (d) Analyze the worst-case running time of your algorithm. A bank manager has n clients waiting to be served, all of whom arrived at the same time. Let us call the time at which these clients arrive to be 0. The manager estimates that client i requires t; time units of service. They also know the clients well and assign each client a weight according to how important the client is to the bank (say, the outstanding balance of their bank account): client i has weight w;. The manager would like to determine a good order in which to serve the clients. In a given order, define the delay of client i to be the time at which client i starts getting served. The total weighted delay of a given order is the sum, over each client i, of the product of w; and the delay of i. The goal of this problem is to determine an order to serve the clients that minimizes the total weighted delay. For example, consider 4 clients with t = 5, t = 2, t3 = 7, t4 = 4. And weights w = 1, w = 3, w3 = 2, and w4 = 2. Consider the order 1,3,2,4. The delay for client 1 is 0, for client 2 is t + t3 = 5 + 7 = 12, for client 3 is t = 5, and for client 4 is t +13 + t = 5+7 +2 = 14. The total weighted delay of the order is then 1.0+3.12+2.5+214=36+10+28 = 74. (a) Describe precisely what your algorithm is given as input and what it needs to output. (b) Prove the following greedy choice property for the problem of finding an order that minimizes the total weighted delay: there exists an optimal solution in which the first client to be served is the client i that has the smallest value of t;/w;. (Hint: Start by proving the statement when there are only two clients. Extend to the general case using an exchange argument.) (c) Based on the claim of part (b), give a greedy algorithm to determine an order that mini- mizes total weighted delay. Describe your algorithm in pseudocode. (d) Analyze the worst-case running time of your algorithm.
Expert Answer:
Related Book For
Auditing a risk based approach to conducting a quality audit
ISBN: 978-1133939153
9th edition
Authors: Karla Johnstone, Audrey Gramling, Larry Rittenberg
Posted Date:
Students also viewed these programming questions
-
Read the case study "Southwest Airlines," found in Part 2 of your textbook. Review the "Guide to Case Analysis" found on pp. CA1 - CA11 of your textbook. (This guide follows the last case in the...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
11. Identify the location of oxidation in an electrochemical cell. A) the salt bridge B) the socket C) the cathode D) the electrode E) the anode 12. Determine the cell notation for the redox reaction...
-
Brain weight B as a function of body weight W in fish has been modeled by the power function B = 0.007W2/3, where B and W are measured in grams. A model for body weight as a function of body length L...
-
How do the average credit scores of people living in various American cities differ? The file Credit Scores is an ordered array of the average credit scores of people living in 143 American cities....
-
Consider the following cash flow profile and assume MARR is 10 percent/year. a. What does Descartes' rule of signs tell us about the IRR(s) of this project? b. What does Norstrom's criterion tell us...
-
Suppose the Xs in the following table indicate locations where fire sprinkler heads need to be installed in an existing building. The S indicates the location of the water source to supply these...
-
Describe persistence design under NoSQL technologies.? What is NoSQL polyglot persistence?
-
Pats Pizzeria produces three types of deli style pizzas: Thin Crust, Deep Dish, and Stuffed Crust. Pats anticipated sales mix is 4:5:6 Thin:Deep:Stuffed. Current sales are 1,500 bundles per year....
-
Die sequence (5) As Integer sequence (1) 2 sequence(0) 10 For i As Integer sequence (1) Next 2 To sequence.Length - 1 sequence(12) sequence(i-1) Write ONLY 1 line of code that declares the array and...
-
The quarter century that was completely dominated by the great industrialists like Andrew Carnegie and John D. Rockefeller began in the year ________. .
-
The law of diminishing returns, diseconomies of scale, and factor suitability each provide an explanation for the law of ____________.
-
Employment discrimination is most closely related to ______. a) specialization b) technology c) unemployment d) underemployment
-
Can you think of any decisions you have recently made that incurred opportunity costs?
-
In the presidential campaign of 1992, candidate Bill Clintons campaign coined the slogan Its the economy, stupid! Which 2012 presidential candidate might have benefited most by using the same slogan?...
-
What is the best measure of central tendency for nominal data? Average, but as long as the data is not skewed. Median. Mode. Mean.
-
For what reason might an exporter use standard international trade documentation (letter of credit, draft, order bill of lading) on an intrafirm export to its parent or sister subsidiary?
-
Define audit quality. What are the five primary drivers of audit quality as articulated by the Financial Reporting Councils Audit Quality Framework?
-
Define the following terms: (a) Misstatement, (b) Factual misstatement, (c) Projected misstatement, (d) Tolerable misstatement, (e) Expected misstatement.
-
Describe the forces that continue to cause audit firms to experience high rates of litigation.
-
Compare and contrast the conceptual and physical properties of money.
-
Compare and contrast monetary policy and fiscal policy.
-
Compare and contrast open market operations and reserve requirement.
Study smarter with the SolutionInn App