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...
-
The Cost Department of Benjamin Products Company prepared the following flexible budget for Department 2 for June: Factory overhead is charged to production at the rate of $3.30 per direct labor...
-
For the following exercises, determine the angle that will eliminate the xy term and write the corresponding equation without the xy term. x 2 + 4xy + y 2 2x + 1 = 0
-
Tennessee law imposes durational-residency requirements on persons and companies wishing to operate retail liquor stores, requiring applicants for an initial license to have resided in the state for...
-
Bradburn Corporation was formed 5 years ago through a public subscription of common stock. Daniel Brown, who owns 15% of the common stock, was one of the organizers of Bradburn and is its current...
-
Find the distance 'x' in this figure, accurate to 3 decimal places (i.e. 0.001"). (Hint: Locate two important points to form the required right-triangle to solve the question. The circle center is...
-
You have a 9 9 grid of squares, each of which can be colored red or blue. The grid is initially colored all blue, but you can change the color of any square any number of times. Imagining the grid...
-
Describe your understanding of the term International law. What does that term mean?
-
The following is a set of activity-coefficient data for a binary liquid system as determined from VLE data: Inspection of these experimental values suggests that they are noisy, but the question is...
-
(a) Fit the Margules two-parameter equation to the n-pentane(1) + acetone(2) system P-x-y data below at 1 bar (Lo et al. 1962. J. Chem. Eng. Data 7:32) by fitting to x 1 = 0.503. Plot the resultant...
-
Match the definition of the keywords with their terms. 1. A standard format for data files and fields typically needed to support an external audit 2. Datasets that are too large and complex for...
-
After fitting the two-parameter Margules equation to the data below, generate a P-x-y diagram at 78.15 C. Data at 78.15C: psat = 1.006 bar 1 psat = 0.439 bar = 1.6931; 2 = 1.9523
-
Weve approached only personal leadership so fardeveloping skills to lead yourself and avoid being reactive. Before we work on leading others, reflect on what leadership means to you now. Some...
-
how globalization affects the human resource management and skill 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...
-
On rare occasions, an organism may have three copies of a chromosome and therefore three copies of the genes on that chromosome (instead of the usual number of two copies). The alleles for each gene...
-
Explain how the miR-200 family of miRNAs behave as tumorsuppressor genes. What happens when their expression is blocked or decreased?
-
Outline the steps that occur when piRITS or piRISC silences transposable elements by repressing transcription and by directly inhibiting TE RNAs, respectively. What is the role of piRNAs in this...
Study smarter with the SolutionInn App