Checkboard problem. You are given a checkboard which has 3 rows and n columns, and has an integer written in each square. You are allowed to select a number from each column so as to maximize the sum of the selected numbers. There is one constraint: any two squares you select from consecutive columns must share at least one corner. For example, given the checkboard below, you can select 6, 7, 3, 10 or 5, 7, 6, 7, among other possibilities. However 6, 7, 9, 10 is not a legal selection, since the last two numbers were selected from two non-adjacent squares. The optimal selection is 5, 9, 6, 10 (or 6, 7, 9, 8), which sums to 30. a. A simple idea is to select the largest number in the first column, and then for the remaining columns, always select the square with the largest number that shares at least one corner with the square selected in the preceding column. Show that this algorithm does not correctly solve this problem, by giving an example of a 3 times 3 checkboard on which the algorithm does not return the correct answer. b. Let F(i, j) represents the sum of the optimal selections for the first j columns if you must select the i-th square in the j-th column. Write down recurrence for computing F(i, j). (It might be easier to write down the recurrence for F(1, j), F(2, j), and F(3, j) separately.) Which F(i, j) would give you the optimal solution for the complete checkboard? c. Show how to use the recurrence above and dynamic programming to solve the following checkboard. Its running time should be Theta(n)