Interval DP

Questions 1 to 5 of 8

1. 1. The matrix chain code loops over range lengths from 2 up to n, and for each range it tries every split point k. For a chain of 4 matrices, how many (range, split point) pairs does the code try in total?

   Type a number.

2. 2. The matrix chain has sizes 10 x 30, 30 x 5 and 5 x 60. Using the order (A1 x A2) x A3, how many scalar multiplications does the whole chain take?

   Type a number.

3. 3. What does this program print? ``cpp #include <iostream> #include <vector> int main() { std::vector<long long> dims = {40, 20, 30, 10, 30}; long long c = dims[1] * dims[2] * dims[3]; std::cout << c << '\n'; } ``

   120002600060008000
4. 4. What does this program print? ``cpp #include <iostream> #include <vector> int main() { std::vector<int> nums = {3, 1, 5, 8}; std::vector<int> a; a.push_back(1); a.insert(a.end(), nums.begin(), nums.end()); a.push_back(1); std::cout << a.size() << ' ' << a[1] * a[2] * a[3] << '\n'; } ``

   5 156 156 36 40
5. 5. Put the steps for filling the matrix chain table in the order the code runs them.

   Use the arrows to put the steps in order.

   1. 1.Loop over range lengths from 2 up to n↑↓
   2. 2.Read the answer for the whole chain from cost[1][n]↑↓
   3. 3.For each range of that length, try every split point k and keep the smallest total↑↓
   4. 4.Set the cost of every range of one matrix to 0↑↓