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.

1. Show that it is possible to multiply two n×n 0/1 (boolean) matrices in o(n³) without using any of the fast matrix multiplication algorithms such as Strassen's algorithm.

   In general the multiplication of two matrices is performed as:

   $$\begin{array}{ccc}{c}_{i,j}& =& \sum _{x=1}^n{a}_{i,x}{b}_{x,j}\end{array}$$

   Naive matrix multiplication of a n×m by a m×p matrix produces a n×p matrix, each element of which requires m multiplications. The number of calculations then is npm. For a symmetric n×n matrix, this is n³.

   For a boolean matrix, each value is constrained to a point that a productive quantity of the possible operations can be precomputed in a reasonable amount of space. The problem is divided into "microsets" where every possible combination of a recurring computation is precomputed and simply looked up rather than computed. In this situation, consider a n×n table. Each row and column is one permutation of a log₂n length bit string.

   For a series of elements in the original n×n boolean matrices, the multiplications can be then done in $logn$ sized chunks which are looked up from the table in constant time. So the computation of the entire matrix will be:

   $$\begin{array}{ccccc}nn\frac{n}{logn}& =& O\left(\frac{n^3}{logn}\right)& =& o\left(n^3\right)\end{array}$$

2. Design a code for at least three characters which is not uniquely decipherable, but has the property that if any character is deleted it is uniquely decipherable.

   A simple code is:

   • a ⇒ '0'
   • b ⇒ '1'
   • c ⇒ '01'

3. Show that if elements are given to you sorted by weight, Huffman codes can be computed in O(n) rather than O(n log n) time.

   For a non-sorted list of elements, a Huffman code can be generated by iteratively building a tree. At each iteration the two elements with the smallest weights are combined in a binary tree. This tree is then readded to the list as a single element with a weight equal to the combined weight of the elements comprising it.

   If the elements are presented in a sorted order then finding the smallest ones becomes simple. A pattern forms from the first few iterations:

   1. The first iteration the first two elements in the list are the smallest. The resultant node is added to a separate queue.
   2. The next iteration the smallest node is either going to be the new node just placed on the queue or two more nodes from the list. If it is two nodes from the list, a new node will be formed. Because it was formed by two nodes that are greater than the nodes that formed the node at the head of the queue, it's value will be greater. It is added to the back of the queue and the queue stays ordered.
   3. Out of the set of possible nodes, the two smallest will always be some combination of the first two in the list and the first two in the queue. When a new node is created, it can always be put at the back of the queue and the queue will stay sorted because the elements used to form it are always increasing in value.

   The algorithm runs until the list is empty and there's a single element on the queue. There was never more than four comparisons for the formation of any element, so the algorithm is O(n).

4. An optimal binary search tree on an alphabetically ordered, weighted set of elements is a binary search tree which minimizes the sum w_il_i where w_i and l_i are the weight and depth of the i^th element respectively. Using a Huffman type strategy where the three elements with the smallest total value are combined into an optimal tree which is then treated as an node with respect to the rest of the tree.

   For this example, depth counting begins at 1. This makes it simpler to illustrate however the ranks of scores for tree configurations will be the same regardless of the depth the configuration occurs.

   Consider the following weighted elements: (there have to be at least four because the algorithm by definition makes the best three-element tree)

   A	B	C	D
   3	2	3	1

   The first iteration, the algorithm will combine B, C and D because 3 + 2 + 3 > 2 + 3 + 1. The optimal tree for these will place C (the weightiest element) at the top:

   When combining this tree with A, there are two options that will maintain the alphabetic ordering of the tree, both of which have a total score of 18.

   An alternative tree has a score of 17, so the algorithm does not produce optimal trees: