Above and beyond

Warning: The material in this section won't (directly) earn you any marks.

Your course notes describe the similarity between the matrix chain multiplication problem and the optimal BST problem, however the suggested solution is iterative and doesn't qualify for this assignment. Algorithms by Cormen, Leiserson and Rivest (CL&R) describes the similarity between polygon triangulation, matrix chain multiplication, and parse trees. Be warned that CL&R use slightly different notation, so the formula for $c[i][k]$ might be off-by-one from this handout. CL&R also describe a single algorithm that solves an entire class of DP problems (CL&R, Section 26.4). You need some familiarity with abstract algebra to read this section.

The similarity of these three problems is discussed in www.ics.uci.edu/ $\tilde{\quad}$eppstein/260/011023/, where all three are reduced to triangulations. Be warned that my formulation of the optimal BST structure allows keys to occupy all nodes (both internal and leaves), whereas on this page the keys occur only at the leaves.