CS 310: Design and Analysis of Algorithms

All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.

I discussed ideas for numbers 1 and 2 with Jeff Green. I also sent him a copy of the questions from the version I had transcribed into the computer. If there are any common misunderstandings in our submissions, it is because my original transciption of the assignment (which included minor edits for clarity) was incorrect.

1. You are working with a board with markings where it needs to be cut. The charge is $k to cut a board k feet long. Design an algorithm to minimize the total cost. For example, consider the following board:

   If the cuts are made in the order A, B, C, the cost is $16 + $13 + $8 = $37. If the cuts are made in the order B, A, C, the cost is $16 + $8 + $8 = $32.

   The board consists of a number of pieces:

   Any set of cuts is going to include those pieces a varying number of times. The simplest cut is when there are two pieces. When there is only one piece, there is no cut. The counts can be represented as a matrix:

   {P}1

   =

   P1 Inclusions 0

   {P}2

   =

   P1 P2 Inclusions 1 1

   The process is iterative. Subsequent counts can be expressed as combinations of previous cuts plus a constant added to each entry. The base possibilities for {P}₃ are:

   {P}3

   =

   P1 P2 P3 Inclusions 1 2 2 2 2 1

   For a given board, it could be the product of some previous number of cuts. An "added matrix" connotes the idea that a previous number of cots took place before a board was produced. For example, an added matrix based off {P}₃ would be:

   {P}3 + 1

   =

   P1 P2 P3 Inclusions 2 3 3 3 3 2

   {P}₃ then can be expressed as:

   {P}3

   =

   P1 P2 P3 Inclusions {P}1 + 1 {P}2 + 1 {P}2 + 1 {P}1 + 1

   Four pieces, {P}₄, then includes {P}₃ + 1 and {P}₂ + 1:

   {P}4

   =

   P1 P2 P3 P4 Inclusions {P}1 + 1 {P}3 + 1 {P}1 + 1 {P}2 + 1 {P}2 + 1 {P}3 + 1 {P}1 + 1 {P}1 + 1

   {P}5

   =

   P1 P2 P3 P4 P5 Inclusions {P}1 + 1 {P}4 + 1 {P}1 + 1 {P}1 + 1 {P}1 + 1 {P}1 + 1 {P}2 + 1 {P}3 + 1 {P}2 + 1 {P}3 + 1 {P}2 + 1 {P}2 + 1 {P}4 + 1 {P}1 + 1 {P}1 + 1 {P}1 + 1 {P}1 + 1 {P}1 + 1

   The issue that makes an efficient algorithm difficult is that for any row in {P}_k there exists a set of lengths of pieces such that the optimal cutting produces those counts. A simple way to eliminate cuts is not readily apparent.

   The width of the table of counts will always be the number of pieces. The height unfortunately grows more quickly, specifically:

   $$\begin{array}{ccc}H\left(k\right)& =& \sum _{i=1}^{\frac{k}{2}}2H\left(k-\mathrm{i}\right)\end{array}$$

   This is growing faster than 2ⁿ, so even though the generation of the table can incorporate some caching to be generated more quickly, to actual test the possibilities is θ(n2ⁿ).

   The question then is how to properly choose the counts such that combination of weights and counts is minimized. Consider two very similar sets of pieces with different optimal cuttings:

   The graph represents the first split is between 2 and 2, then there are cuts between 2 and 4 on the ends. Consider a very similar set of pieces with a different optimal cutting:

   The difference between these is that the decision to make a cut increases the count for each of the two pieces on either side of the cut. (If those pieces are composites, the counts of each of the constituent pieces will increase in a regular recursive way as described above with the sets {P}_k.) This set of possibilities does grow exponentially, but the trick is they don't all need to be computed.

   Consider the idea of composite pieces, for example P_1,2,3 is the combination of the pieces P₁, P₂ and P₃. Assume for a moment that they are joined to form P_1,2,3 before P₃ is joined to P₄. There is a cost for that join and it will vary depending on whether P₁ is joined with P_2,3 or if P₃ was joined to P_1,2. (The two pieces that were joined previously will have their pieces counted twice.) The options are:

   $$\begin{array}{ccccccc}{P}_{1,2,3}& =& \left\{\begin{array}{c}{P}_1+2P_{2,3}\\ \text{or}\\ 2P_{1,2}+P_3\end{array}\right.& =& \left\{\begin{array}{c}{P}_1+2\left(P_2+P_3\right)\\ \text{or}\\ 2\left(P_1+P_2\right)+P_3\end{array}\right.& =& \left\{\begin{array}{c}\sum _{i=1}^3{P}_i+P_{2,3}\\ \text{or}\\ \sum _{i=1}^3{P}_i+P_{1,2}\end{array}\right.\end{array}$$

   Both of these solutions don't need to be stored however. If, at some point in an optimal cutting strategy, P_1,2,3 is produced, the minimum cost strategy is the one that will be used to cut it apart. Therefore, for P_1,2,3 is is only necessary to store:

   $$\begin{array}{ccc}{P}_{1,2,3}& =& \sum _{i=1}^3{P}_i+min\left(P_{1,2},P_{2,3}\right)\end{array}$$

   The summation makes sense because each piece is included in the composite piece and then the constituent pieces need to be cut apart. This same strategy can be used to develop P_1,2,3,4:

   $$\begin{array}{ccc}{P}_{1,2,3,4}& =& \left\{\begin{array}{c}\sum _{i=1}^4{P}_i+P_1+P_{2,3,4}\\ \text{or}\\ \sum _{i=1}^4{P}_i+P_{1,2}+P_{3,4}\\ \text{or}\\ \sum _{i=1}^4{P}_i+P_{1,2,3}+P_4\end{array}\right.\end{array}$$

   Which, by the same logic about optimal cuttings is:

   $$\begin{array}{ccc}{P}_{1,2,3,4}& =& \sum _{i=1}^4{P}_i+min\left(P_1+P_{2,3,4},P_{1,2}+P_{3,4},P_{1,2,3}+P_4\right)\end{array}$$

   Where single span pieces are defined as having a weight of 0 (P_i = P_i,i = 0). This form can be generalized as:

   $$\begin{array}{ccc}{P}_{i,j}& =& \sum _{k=i}^j{P}_k+min\left(\left\{P_{i,\dots ,k}+P_{k+1,\dots ,j}\forall k\ni i\le k<j\right\}\right)\end{array}$$

   These methods can be cached in a table which will ultimately derive the answer:

   P1,1	P2,2	P3,3	P4,4	…	Pn-3,n-3	Pn-2,n-2	Pn-1,n-1	Pn,n
   P1,2	P2,3	P3,4	P4,5	…	Pn-2,n-1	Pn-1,n	Pn-1,n
   P1,3	P2,4	P3,5	P4,6	…	Pn-3,n-1	Pn-2,n
   P1,4	P2,5	P3,6	P4,7	…	Pn-3,n
   …
   P1,n

   At each level of the table it is necessary to track which combination was made to minimize the cut. This combination of n - 1 cuts is the solution.

   Also, the computation of $\sum _{k=i}^j{P}_k$ can be built in a table using dynamic programming.

   $$\begin{array}{ccc}\sum _{k=i}^j{P}_k& =& \sum _{k=i}^{j-1}{P}_k+P_j\end{array}$$

2. In a variant of the minimum spanning tree problem, you want to create a spanning tree T for a graph G such that the largest edge in T is as small as possible. The sum of the edge weights is not a concern. Design an O(m + n) algorithm for this variant. (Consider divide and conquer.)

   There are three main algorithms commonly employed for building minimum spanning trees:

   • Kruskal's — Order the edges and go through them one at a time. For each one if it connects two edges otherwise unconnected by a previously examined edge then use it in the solution. Once n - 1 edges have been added there's a tree. This will run in O(m log m)
   • Prim's — Start with a node and grow a tree by iteratively adding a minimum cost edge connecting to the tree. This will run in O(m log n)
   • Borůvka's — For each node add the minimum edge and compact the resultant tree. Each iteration will combine at least half the nodes and so the algorithm will run in O(m log n)

   Unfortunately none of these seems particularly well suited to solving this problem.

   Another tact in trying to find a solution is looking at operations that are likely to be useful that can be done in constant time. Particularly when considering divide and conquer solutions, partitioning on the median is a common one. The basic algorithm is:

   1. Divide the list into sets of 5
   2. Find the median for each set (O(c) = O(1))
   3. Recursively find the median for the resultant set of medians

   The list can then be split around the median in O(n) time.

   The question could also be considered as finding the minimum edge, m_i, that partitions the set of edges such that all edges with weight ≤ w_i that edge contain a spanning tree. Using the median finding algorithm and a binary search, it is possible to find that partitioning edge in O(m log m) time.

   At each iteration though it is necessary to determine if set L_i contains a spanning tree or not. An option for making this determination is a relaxed version of Borůvka's algorithm. One node at a time, union that node with a node connected to and compress those two elements into a single node. Then repeat on the results of that. This will have to be done at most log n times since each iteration joins at least half the trees. If the nodes will reduce to a single node, the edges used to form that node are a spanning tree. If the Union-Find style tree with path compression is used, this operation can be performed in O(n α(n)) time.

   Unfortunately this algorithm seems to be O(m log(m) n α(n)).

3. Minimize the following deterministic finite autonoma using an O(n log n) algorithm.

   An O(n log n) algorithm is partitioning. At each iteration the set of states is divided into meaningful non-intersecting subsets. When this is no longer possible the remaining states may be grouped into a minimal set of required states. The first step is to divide final and non-final states:

   Now the algorithm will iterate to form partitions. The basis for a partition is a transition can be made to a distinguished state. There's only one patritionable set and one distinguished state currently, so transitions are considered there:

   This forms a new partition:

   Non-meaningful transitions are not shown. For example, B and H both go to G on 0, so that will not cause a partition. The separating transitions are:

   Which produces a new partition:

   At this point all states within a partition transition to the same external partition, so no further partitioning is possible and a minimum dfa is:

4. To achieve the O(n log n) time bound for DFA minimization, we need to be able to perform the following operation. Consider the set of states X that have a transition to state i on input a. Divide each current set of states S in the current partition into S ∩ X and S - X. Describe the data structures necessary for storing sets of states and an algorithm that allows you to subdivide all current sets of states in the partition in O(|X|) time.

   Store the sets of shallow trees of depth 2 where the root represents the partition and the leaves represent states in the dfa.

   For a given set of states X, create a new partition and for each element of X if the parent of the state is S then move it to the new partition. At the end of this operation S will now be S - X and the new state will be S ∩ X.

   This will take O(|X|) time.