Your job

You'll need to download testChain.cpp, chain.h, Makefile. You should be able to click (or shift-click) on the appropriate link.

Once you've downloaded the appropriate files, you have these tasks:

1. Implement minPartition(int i, int k) (see chain.h). This returns a minimal partition (a list of components, see below) of the range i...k of a chain. Some definitions:

   range i...k

   For a polygon, this means the (sub)polygon from vertex i to vertex k. For a matrix chain, this means the (sub)chain from matrix i to matrix k-1. For a BST this means the (sub)BST from node i+1 to node k-1.

   component $i j k$

   A triple of integers that specify a component of a partition. For a polygon this specifies the triangle with vertices vertex $i$, vertex $j$, and vertex $k$. For a matrix chain this specifies the parenthesization of matrices $i$ through $j-1$ and then of matrices $j$ through $k-1$. For a BST this specifies that node $j$ is the root of a (sub)tree with left child comprised of nodes $i+1$ through $j-1$ and right child comprised of nodes $j+1$ through $k-1$.

   $w(i,j,k)$

   The weight of component $i j k$. For a polygon, this is the perimeter of the triangle with vertices vertex $i$, vertex $j$, and vertex $k$. For a chain of matrices this is the product $r_i r_j c_{k-1}$, where $r_i$ is the number of rows in matrix $i$, $r_j$ the number of rows in matrix $j$, and $c_{k-1}$ the number of columns in matrix $k-1$. For a BST this is the sum of frequencies $f_{i+1} + \cdots + f_{k-1}$.

   link

   The basic unit of a chain. For a vertexChain, this is a vertex with a pair of double values for its coordinates. For a matrixChain, this is a single matrix with a pair of doubles describing its dimensions (number of rows, number of columns). For a bstChain, this is a node with a pair of doubles representing its key and frequency.

2. Implement partitionTally(componentNode *partitionList) (see chain.h). This returns the sum of the weights $w(i,j,k)$ of components in the linked list partitionList.

3. Implement constructors for classes chain in a file called chain.cpp, vertexChain in a file called vertexChain.cpp, matrixChain in a file called matrixChain.cpp, and bstChain in a file called bstChain.cpp.

4. Implement any other functions, constants, or types needed to make testChain.cpp work when it is provided with input of the form described below. You may not change testChain.cpp. You may add to chain.h, but you may not change any functions or types originally declared there.

For a chain with $n$ links (e.g. a polygon with $n$ sides, a chain of $n$ matrices, a BST with $n$ nodes), your code should have worst-case $O(n^3)$ running time. Your solution should combine a recursive algorithm with memoization. Your solution should use generic code, rather than three repetitive solutions.

Here is what testChains.cpp expects on standard input:

1. One of the strings polygon, matrix, or bst, followed by white space. This indicates the type of chain that is being partitioned.
2. An integer (we'll call it $n$) followed by white space. This indicates the number of links in the chain.
3. $n$ pairs of double literals, separated and followed by white space. These are the values of the links.
4. A single double literal, followed by white space. This represents the (approximate) calculated minimum value for partitioning this chain.

As an example, look at triangle.chn or any of the other examples in ../Code/TestChains. Once your code is working, you should be able to see the following test result:

./testChains < triangle.chn
Chain type: polygon     Minimal partition