Computers and Technology, 30.07.2021 04:40 DASASDAEDWEDA

We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. 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 isolation, ignoring the pebbles in adjacent columns) and describe these patterns. 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 programming algorithm for computing an optimal placement.

Answers: 2

Show answers

Other questions on the subject: Computers and Technology

Computers and Technology, 22.06.2019 17:30, glocurlsprinces

Rachel completed typing an official document with a word processing program. she wants to make sure that her document has no typographical errors. she also wants all headings to have the same font. which features in a word processing program should she use? rachel should use the feature in a word processing program to find typographical errors. she should apply to have uniform headings.

Answers: 1

continue

Computers and Technology, 23.06.2019 15:30, jokerr6323

1. ask the user how many questions are in the quiz. 2. ask the user to enter the key (that is, the correct answers). there should be one answer for each question in the quiz, and each answer should be an integer. e. g., 34 7 13 100 81 3 9 10 321 12 might be the key for a 10-question quiz. you will need to store the key in an array. 3. ask the user to enter the answers for the quiz to be graded. there needs to be one answer for each question. note that these answers do not need to be stored; each answer can simply be compared to the key as it is entered. 4. when the user has entered all of the answers to be graded, print the number correct and the percent correct. 5. add a loop so that the user can grade any number of quizzes with a single key. after the results have been printed for each quiz, ask "grade another quiz? (y/n)." note: you only have one array (the key). you are not creating a new key for each set of quiz answers.

Answers: 3

continue

Computers and Technology, 23.06.2019 16:30, vitothebest1

You have read about the beginnings of the internet and how it was created. what was the internet originally created to do? (select all that apply) share research. play games. communicate. share documents. sell toys

Answers: 1

continue

Computers and Technology, 23.06.2019 18:30, bsept1018

Report all segments of identity by descent longer than 20 polymorphisms between pairs of individuals in the following cohort of 15 individuals across 49 polymorphisms: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 numeric input 2 points possible (graded) you have 2 attempts to complete the assignment below. for example if the sequence is "bcd", which occurs in "abcdef" , the starting point would be 2 (b), and the finishing point would be 4(d). individuals 7,10 between positions

Answers: 1

continue

You know the right answer?

We are given a checkerboard which has 4 rows and n columns, and has an integer written in each squar...