We are given a checkerboard which has 4 rows and n columns, and has an integer...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
We are given a checkerboard which has 4 rows and n columns, and has an integer C[i, j] written in each square, where i€ [4] and j = [n]; We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is fine). (a) Determine the number of legal patterns that can occur in any column (in isola- tion, ignoring the pebbles in adjacent columns) and describe these patterns. (You can draw pictures.) Call two patterns compatible if they can be placed on adjacent columns to form a legal placement. Let us consider subproblems consisting of the first k columns 1 < k < n. Each subproblem can be assigned a type, which is the pattern occurring in the last column. (b) Using the notions of compatibility and type, give an O(n)-time dynamic pro- gramming algorithm for computing an optimal placement. We are given a checkerboard which has 4 rows and n columns, and has an integer C[i, j] written in each square, where i€ [4] and j = [n]; We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is fine). (a) Determine the number of legal patterns that can occur in any column (in isola- tion, ignoring the pebbles in adjacent columns) and describe these patterns. (You can draw pictures.) Call two patterns compatible if they can be placed on adjacent columns to form a legal placement. Let us consider subproblems consisting of the first k columns 1 < k < n. Each subproblem can be assigned a type, which is the pattern occurring in the last column. (b) Using the notions of compatibility and type, give an O(n)-time dynamic pro- gramming algorithm for computing an optimal placement.
Expert Answer:
Answer rating: 100% (QA)
a Determine the number of legal patterns in any column and describe these patterns In each column there are 4 rows To satisfy the adjacency constraint ... 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 programming questions
-
What is a branch delay slot and why does it arise? [7 marks] How can branch delays be avoided? If a processor exhibited one branch delay slot how would you reorder (and possibly modify) the...
-
The new line character is utilized solely as the last person in each message. On association with the server, a client can possibly (I) question the situation with a client by sending the client's...
-
According to Electronic Designs 2012 Engineering Salary Survey, the mean base salary of a software engineering manager is $126,417the highest mean among all types of engineers. In contrast, a...
-
In clinical trials of the allergy medicine Clarinex (5 mg), 3307 allergy sufferers were randomly assigned to either a Clarinex group or a placebo group. It was reported that 50 out of 1655...
-
Describe the various ways that earned value can be found.
-
Why are grooming and attire so important in selling? How do you know if you are dressed appropriately for a customer?
-
Bobs Country Kitchen, a small family-owned restaurant in northern New York, has seen a drop in profitability over the past three years and the owners want to know why. Bobs has been a local favorite...
-
Alexis and Tomas meet with their insurance agent, Pat. After a thorough needs analysis, Pat recommends that Alexis set up a spousal RRSP tot Tornas Pat has them complete a risk tolerance...
-
4. The table below shows the daily closing values of the S&P 500 index, along with the daily prices for the S&P 500 futures contract with maturity date October 29 of the same year. The futures...
-
A video camera, of mass 2.0 kg, is mounted on the top of a bank building for surveillance. The video camera is fixed at one end of a tubular aluminum rod whose other end is fixed to the building. The...
-
The Providence Hotel has 800 guest rooms and 625 were occupied last night. Today there are 300 scheduled to depart the hotel and with a convention in the city 575 are expected to arrive. Historical...
-
What are examples of decisiveness abilities during the monthly evaluations?
-
6) Due 11/13(M) i Saved Help Save & E In 2024, KP Building Incorporated began work on a four-year construction project (called Cincy One). The contract price is $365 million. KP recognizes revenue on...
-
How can the design team ensure that the database schema for the e-learning platform facilitates effective course enrollment, progress tracking, and assessment management for both instructors and...
-
a response to A cost-benefit analysis is a financial instrument used to determine the economic viability of a proposed solution. It entails quantifying both the costs and advantages of each proposal....
-
As the external audit, Identify and explain the inherent audit risks for the following financial statements. You are an auditor with Buoy & Alex (B&A). B&A has just been appointed as the...
-
Which of the followingcarbocations is the least stable? CH3CH2 . CH3CHCH3 CH3 I . CH3C0 T CH3 IV. V. CH3 CH3CCH2 CH3
-
Show all legal B-trees of minimum degree 2 that represent {1, 2, 3, 4, 5}.
-
The following code fragment implements Horner?s rule for evaluating a polynomial The following code fragment implements Horner?s rule for evaluating a polynomial given the coefficients a 0, a 1 ??.,a...
-
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition af (n/b) cf (n) for some constant c < 1 implies that there exists a constant > 0 such that f (n) =...
-
Distinguish between a heat engine, a heat pump, and a refrigerator.
-
Sketch and explain split air conditioner?
-
With a neat sketch of a room air-conditioner, explain its working principle.
Study smarter with the SolutionInn App