Consider the following greedy strategy for the rod cutting problem: define the density of a rod...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider the following "greedy" strategy for the rod cutting problem: define the density of a rod of length i to be p/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, which has the maximum density. It then continues by applying the greedy strategy to the remaining piece of length n - i. a. Write pseudocode for this Greedy strategy for Rod Cutting Problem b. Fill out the density values in the following table Length i (inch) Price (dollar) Density 1 2 a 13. 20 5 21 a 24 c. According to the greedy strategy, if we are to cut a rod of length 6, what is the length of the first piece to cut off? What is the resulting revenue of the greedy solution? Is this the maximum revenue amongst all possible ways of cut (You can represent a way of cut by summation expression, e.g., 6 = 1 + 2 + 3, etc) d. If we are to cut a rod of length 5, what is the solution given by the greedy strategy? (represent it with a summation expression). Does it give the maximum revenue? If not, what is optimal way to cut? Consider the following "greedy" strategy for the rod cutting problem: define the density of a rod of length i to be p/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, which has the maximum density. It then continues by applying the greedy strategy to the remaining piece of length n - i. a. Write pseudocode for this Greedy strategy for Rod Cutting Problem b. Fill out the density values in the following table Length i (inch) Price (dollar) Density 1 2 a 13. 20 5 21 a 24 c. According to the greedy strategy, if we are to cut a rod of length 6, what is the length of the first piece to cut off? What is the resulting revenue of the greedy solution? Is this the maximum revenue amongst all possible ways of cut (You can represent a way of cut by summation expression, e.g., 6 = 1 + 2 + 3, etc) d. If we are to cut a rod of length 5, what is the solution given by the greedy strategy? (represent it with a summation expression). Does it give the maximum revenue? If not, what is optimal way to cut?
Expert Answer:
Answer rating: 100% (QA)
Lets address each part of the question stepbystep a Write pseudocode for this Greedy strategy for Rod Cutting Problem Here is a simple pseudocode for ... View the full 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 algorithms questions
-
the bank simulation on east coast bank discussed during week 1's lecture revealed the following: positive total earning assets and credit quality ratios, managements raising additional capital to...
-
Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p i /i, that is, its value...
-
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...
-
How do standard costs illustrate the trade-off between decision making and control?
-
A gamma-ray photon produces an electron and a positron, each with a kinetic energy of 285 keV. Determine the energy and wavelength of the photon.
-
What special roles do the Budget Committees of the House of Representatives and the Senate play in creating fiscal policy?
-
On September 1, 2008, Cano & Company, a U.S. corporation, sold merchandise to a foreign firm for 250,000 euros. Terms of the sale require payment in euros on February 1, 2009. On September 1, 2008,...
-
Billy's Bank is the only bank in a small town in Arkansas. On a typical Friday an average of 10 customers per hour arrive at the bank to transact business. There is one single teller at the bank, and...
-
On July 31, 2020, Sandhill Company paid $ 2,700,000 to acquire all of the common stock of Conchita Incorporated, which became a division (a reporting unit) of Sandhill. Conchita reported the...
-
Which series has the highest beta. BraveNewCoin Liquid Index for Bitcoin 1D BNC Trading Brave Ne Yellow Green Blue Orange
-
Cash in bank account $ 8,540 Petty cash $ 250 Short-term investment $ 10,400 Checks from customers $ 1,350 Equipment $ 805 Treasury bill maturing in 60 days $ 10,000 Money orders $ 290 A three-year...
-
Use the following year-end footnote information from Cisco Systems, Inc.s 10-K report to anfied swer parts a and b. ($ millions) Cost of available-for-sale investments securities. Gross unrealized...
-
If an asset declines in value, which of the following must be true? a. A liability also declines. b. Equity also declines. c. Either a liability or equity also declines or another asset increases in...
-
Which of the following is true about accrual accounting? a. Accrual accounting requires that expenses always be recognized when cash is paid out. b. Accrual accounting is required under GAAP. C....
-
Which of the following options accurately identifies the effects a cash sale of an iPhone has on Apples accounts? a. Accounts receivable increases, sales revenue increases, cost of goods sold...
-
Indicate whether each of the following accounts normally has a debit balance or a credit balance. a. Unearned Revenue b. Service Revenue c. Dividends d. Land e. Accounts Receivable f. Cash g. Common...
-
Question 4 (1 point) $1,000 semiannual bond has a coupon rate of 6.5%, matures in 10 years, and is selling today at $950.70. The yield to maturity of this bond is 5.6% 6.3% 6.8% 7.2%
-
Portal Manufacturing has total fixed costs of $520,000. A unit of product sells for $15 and variable costs per unit are $11. a). Prepare a contribution margin income statement showing predicted net...
-
The diameter of a tree T = (V, E) is defined as max u, V (u, ), that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and...
-
Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST(root) which, given the table root, outputs the structure of an optimal binary search tree. For the example in Figure 15.10, your procedure...
-
Show that the call to PIVOT in line 12 of SIMPLEX never decreases the value of .
-
Moontan Ltd has an operating profit for the year ended 31 December 2002, before dealing with the following items, of 200,000. Complete the profit and loss account. (a) The standard rate of income tax...
-
Camden Lock Ltd has just finished its second year of trading to 31 December 2007. Balances from Question need to be brought forward into this question. Tax rates are the same as for 2006. The...
-
Corporation tax for the tax years 2007, 2008, and 2009 was 40 per cent and income tax foreach year was 20 per cent. (A) Skim-Ltds draft profit and loss account for the year ended 31 December 2008...
Study smarter with the SolutionInn App