Divide and conquer and Knuth

Questions 1 to 5 of 8

1. 1. An AI assistant wrote a divide and conquer solver. Each block costs (sum of its weights) squared. The solver is run on the weights -3 -9 -6 -6 7 0, cut into k = 3 blocks. It prints 169. Brute force over all cuts gives 115. The solver printed no warning. What is the most likely cause?

   The sums overflow a 64-bit integer, so the printed numbers are wrong.The square cost satisfies the quadrangle inequality for every integer input, so the bug must be in the loop bounds, not in the cost.The proof that the square cost satisfies the quadrangle inequality uses non-negative weights. Negative weights break the sign argument, so the best splits can move left and the search misses them.The brute-force checker is at fault, because no cut of these weights costs 115.
2. 2. Four piles hold 4, 1, 3 and 2 stones, in that row. You may merge two neighbouring piles, and each merge costs the total stones in the new pile. What is the smallest total cost to merge all four into one pile?

   Type a number.

3. 3. Which statements about Knuth's bound for interval DP are true? Select all that apply.

   Pick every answer that is true.

   The bound says opt[l][r - 1] ≤ opt[l][r] ≤ opt[l + 1][r], so each scan covers only the splits between those two values.The bound is safe for any cost table, because it only compares split points.Summed over one interval length, the scan sizes telescope, so the whole DP is O(n^2).The bound needs the quadrangle inequality on the cost. When that fails, the two ends of the scan can cross, and the answer can be wrong.
4. 4. Put these steps in the order to follow before you trust a divide and conquer speed-up for a layered DP.

   Use the arrows to put the steps in order.

   1. 1.Check the quadrangle inequality by algebra or over every quadruple a ≤ b ≤ c ≤ d↑↓
   2. 2.Compare the fast solver with a brute-force checker on small random inputs↑↓
   3. 3.Use the fast solver on the full input size↑↓
   4. 4.Write the block cost as a function w(j, i)↑↓
5. 5. Match each DP to its work bound. Here n is the number of items and k is the number of blocks.

   Choose the matching item for each row.

   Plain interval DP over piles, with every split triedChoose…O(n^2)O(k n log n)O(k n^2)O(n^3)Interval DP with Knuth's boundChoose…O(n^2)O(k n log n)O(k n^2)O(n^3)Plain layered DP for k blocksChoose…O(n^2)O(k n log n)O(k n^2)O(n^3)Layered DP with divide and conquerChoose…O(n^2)O(k n log n)O(k n^2)O(n^3)