Skip to main content

Advanced DP and Optimization Clinic

Budget 8–11 hours across P11–P20. A justified recurrence and worked trace are required; implementations beyond the core lab APIs are depth options. Consult separate solutions after attempting each problem.

P11: matrix chain​

Dimensions are [5,2,4,3]. Evaluate all parenthesizations, derive the general split recurrence and increasing-length order, then verify an output tree by its leaf order, dimensions and scalar multiplication count.

P12: optimal search tree model​

Two ordered keys have successful-query frequencies 3 and 1. With root depth 1 and no unsuccessful-query costs, compare both trees. Write the interval recurrence and specify how the model differs from one with gap-query frequencies.

P13: tree boundary state​

A star has center weight 7 and three leaves of weight 3. Compute take/skip and reconstruct an independent set. Repeat with every weight negative and empty selection allowed. Give a graph with n-1 edges that is not a tree.

P14: rerooting​

Derive the sum-of-distances reroot equation on a unit-edge tree. Apply it to path 0-1-2-3 and explain why the algorithm needs only linear work. Identify the extra implementation risk of recursive DFS on a long chain.

P15: subset state and closing edge​

Solve TSP for [[0,1,4],[3,0,2],[1,5,0]]. Remove edge 2->0 and solve again. State all bases, the impossible-tour output, and how signed edge costs affect the simple-tour contract. Explain the n=0 and n=1 lab conventions separately.

P16: transition counting and memory​

Prove there are 3^n (mask,submask) pairs including empty submasks. Estimate slots and eight-byte payload for a rectangular n=20 Held-Karp table. List at least three storage costs omitted by that payload estimate.

P17: bounded digit count​

Count digit sum 1 in [0,100], digit sum 0 in the same range, and digit sum 3 in [10,25]. Specify tight transitions, terminal conditions and cache lifetime. Explain why a "contains digit zero" extension needs different padding handling.

P18: dominance with a changed objective​

For one processed item prefix, states (weight,value) are (2,5),(3,4),(4,7). Which can be dropped for at-most capacity maximization? Give an exact-fill case that invalidates that pruning and explain its effect on counting tied optima.

P19: greedy or weighted DP?​

Jobs are (0,2,3),(2,4,3),(0,4,7). Prove earliest-finish greedy for maximum cardinality, demonstrate weighted failure here, and derive the compatible-prefix DP. Change the final job value to 6 and specify accepted tied witnesses.

P20: DAG initialization​

Find source-0 longest paths in 0->1:-5,0->2:-2,1->3:1,2->3:-1, with isolated vertex 4. Give distances and a path to 3. Explain which question would instead be answered by initializing every vertex to 0. Explain why an interval split combining two children is not simply one-predecessor path relaxation.