- Show what would happen after running the Floyd-Warshall algorithm on one or two numerical examples of your choice. You can use the following numerical example.
- (Optional) Derive the recurrence for the maximum subsequence problem discussed in class. Test your algorithm using a numerical example.
- Solve the following knapsack problem for integer values of b from 0 to infinity. First, fix a relatively small value of b and calculate the table produced by the dynamic programming algorithm to find the optimal values of x1, x2, and x3. Second, solve the problem for all values of b and turn in a table that exhibits the periodic nature of the solution. Make sure you report the value of x1, x2, x3, total value V, total weight W, and gain g for each value of b.
-
Show your understanding of the knapsack problem by solving the following numerical example, using the O(n*w_1) algorithm that we discussed in class. In your report, state the problem and turn in a table showing the periodic solution of the problem, reporting the value of b and optimal gain g at the critical boundary for all threads T_0 to T_{w_1-1}. For the table, you can just report n rows, where the kth row represents the periodic solution using the first k items. Include calculation details to get partial credit.
Max 8x_1 + 17x_2 + 13x_3
Sub 8x_1 + 17x_2 + 14x_3 <= b
x_j >= 0, integers