Due to the tragic news that a much-beloved queen has passed, her citizens have put together...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Due to the tragic news that a much-beloved queen has passed, her citizens have put together an organising committee for the funeral. As the death was sudden, the committee has little time. Tradition dictates that the monarch's funeral service must feature richly embroidered carpet that covers the length of the church aisle. That is, it must be exactly T = 200 metres long, no more or no less. The organisers have searched through their inventory and discovered that they have a very large collection of embroidered carpets that are suitable. Each carpet is of integer length (in metres). Due to the time constraints, the organisers have decided that they will simply line these carpets end-to-end to achieve the desired length. Cutting them to size is not an option because of their immense value; nor is overlapping the carpets, as this would not allow the embroidery to be on full display. However, the committee cannot be sure if this strategy will indeed exactly cover the desired length of the church. In a panic, they summon Professor Smart at the local university to see if she can help determine its feasibility. (a) [5 pt] Let n be the number of carpets in their collection. If the committee were to exhaustively check all possible selections from their carpet collection, how many selections would they encounter? (b) [5 pt] Give a sub-problem definition using suffixes that Professor Smart can use to devise (using Dynamic Programming) an algorithm that answers the committee's question. Hint: The committee's question is a decision problem having True or False outputs. (c) [5 pt] Using the sub-problem definitions from part (b), characterise the optimal substructure of the problem by giving the sub-problem relation. Justify, in words, why the sub-problem relation holds. Provide the base case(s) of your sub-problem relation. (d) [5 pt] Provide the pseudo-code for a bottom-up algorithm that will tell Professor Smart whether the com- mittee's plan is feasible or not in O(nT) time. Due to the tragic news that a much-beloved queen has passed, her citizens have put together an organising committee for the funeral. As the death was sudden, the committee has little time. Tradition dictates that the monarch's funeral service must feature richly embroidered carpet that covers the length of the church aisle. That is, it must be exactly T = 200 metres long, no more or no less. The organisers have searched through their inventory and discovered that they have a very large collection of embroidered carpets that are suitable. Each carpet is of integer length (in metres). Due to the time constraints, the organisers have decided that they will simply line these carpets end-to-end to achieve the desired length. Cutting them to size is not an option because of their immense value; nor is overlapping the carpets, as this would not allow the embroidery to be on full display. However, the committee cannot be sure if this strategy will indeed exactly cover the desired length of the church. In a panic, they summon Professor Smart at the local university to see if she can help determine its feasibility. (a) [5 pt] Let n be the number of carpets in their collection. If the committee were to exhaustively check all possible selections from their carpet collection, how many selections would they encounter? (b) [5 pt] Give a sub-problem definition using suffixes that Professor Smart can use to devise (using Dynamic Programming) an algorithm that answers the committee's question. Hint: The committee's question is a decision problem having True or False outputs. (c) [5 pt] Using the sub-problem definitions from part (b), characterise the optimal substructure of the problem by giving the sub-problem relation. Justify, in words, why the sub-problem relation holds. Provide the base case(s) of your sub-problem relation. (d) [5 pt] Provide the pseudo-code for a bottom-up algorithm that will tell Professor Smart whether the com- mittee's plan is feasible or not in O(nT) time.
Expert Answer:
Answer rating: 100% (QA)
Answer a There are 2n possible selections of carpets that the committee could make b Professor Smart ... View the full answer
Related Book For
Business Research Methods
ISBN: 978-0073521503
12th edition
Authors: Donald R. Cooper, Pamela S. Schindler
Posted Date:
Students also viewed these operating system questions
-
This exercise is related to the Lawlor Lawn Service situation started in Chapter 1. Lawlor has decided to start a pressure washing business with her buddy Tanya. This will be a separate business from...
-
This problem is related to the Draper Consulting situation started in Chapter 1. Colin Draper, Dave Tau, and Sandi Williams decide to form a graphic design partnership. Colin figures this graphic...
-
This question is related to the use of output quotas in the milk market in the previous question. Suppose the government used a quota system instead of direct price supports to assist milk producers....
-
Determine whether the following taxpayers have gross income from the payment of their expenses: a. Julia's mother, Henrietta, is short of cash when it comes time to pay her property taxes. Julia pays...
-
If you included a bibliography in your report, would you also need to include in-text citations? Please explain.
-
Net free cash flow is best described as free cash flow after: A. taxes. B. financing costs. C. financing costs and taxes.
-
The mean square value of the response of a machine, \(E\left[y^{2} ight]\), subject to the force shown in Fig. 14.29, is given by (see Problem 14.26): \[E\left[y^{2} ight]=\sum_{n=0}^{N-1}...
-
The following changes took place last year in Pavolik Companys balance sheet accounts: Long-term investments that had cost the company $ 6 were sold during the year for $ 16 and land that had cost $...
-
The Dougherty Furniture Company manufactures tables. In March, the production department had budgeted allocation base (i.e. cost driver) of 4,000 machine-hours. The budgeted manufacturing overheads...
-
The Electro-Poly Corporation is the world's leading manufacturer of slip rings. A slip ring is an electrical coupling device that allows current to pass through a spinning or rotating connectionsuch...
-
The average annual return on an Index from 1996 to 2005 was 19.31 percent. The average annual T-bill yield during the same period was 3.91 percent. What was the market risk premium during these ten...
-
what is the output? #include using namespace std; int main () { for (int i = 0; i <5; ++i); cout < < i; return 0; }
-
Given these survey results, What is P(a child's favorite food is fruit)?
-
Evaluate the limit using the following table 23-8 x2+ 32-9 2.1 0000 2.01 2.001 2.0001 2.00001 2.000001 From the numerical estimation table, we conclude th lim 23 - 8 -12+ 3-9
-
What are the factors of 64x + 125y?
-
Cost of Goods Manufactured and Sold LeMans Company produces specialty papers at its Fox Run plant. At the beginning of June, the following information was supplied by its accountant: Direct materials...
-
Explain Super's life roles, career maturity, life space, and work-life-balance in career development.
-
To help you become familiar with the accounting standards, this case is designed to take you to the FASBs Web site and have you access various publications. Access the FASBs Web site at...
-
Propose one or more hypotheses for each of the following variable pairs, specifying which the IV is and which is the DV. Then develop the basic hypothesis to include at least one moderating variable...
-
Suggest situations where the researcher should be more concerned with Type II error than with Type I error. a) How can the probability of a Type I error be reduced? A Type II error? b) How does...
-
During the 2010 Super Bowl, the Snickers candy bar campaign was voted the best ad by women 18 or older, men 18 or older, and youth 17 or younger. This ad features a neighborhood football game in...
-
How do children learn language?
-
Discuss the relationship between language and culture.
-
In the 1890 s, L. L. Zamenhof believed that different language was a key source of strife between people. He created Esperanto, which he hoped would be a universal language, to foster peace and...
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App