MATH/CSCI 2113
Assigment 7
Due Wednesday, March 13.

Read Sections 12.2, 12.3 and 12.4 of the text book.

1. Do problem 12.2.6, page 579, of the text book.

2. Do problem 12.2.18 on page 570 of the text book.

3. Given is the following adjacency matrix of a graph $G=(V,E)$, where $V=\{ v_1,\dots ,v_{10}\}$ (rows are columns correspond to vertices in order of increasing indices) :

   
   

   $$A=\left[ \begin{array}{cccccccccc} 0&1&0&0&0&1&0&0&0&0\\ 1&... ...0&0&1&0&1&1&0&0&0\\ 0&0&0&0&1&0&1&1&0&0\\ \end{array}\right]$$
   
   

   (a) Find a dept-first spanning tree and a breadth-first spanning tree for this graph, with the given vertex order.
   

   (b) Find a breadth-first spanning tree for this graph when the vertices are ordered $v_{10},v_9,v_8,\dots,v_1$.

4. Do problem 12.3.2 on page 574 of the text book.

5. Use Huffman coding to construct an optimal prefix code for the symbols $a,b,\dots i,j$ that occur with respective frequencies $79,4,49,21,31,122,38,29,17,78$. Calculate the average length of your Huffman code.

6. For each of the following sequences of lengths, does there exist a prefix code with the codewords of the following prescribed lengths? If so, give such a code. If not, give proof that it doesn't exist.
   

   (a) $6,5,4,4,3,1$.
   (b) $1,2,3,3,3$.
   (c) $2,2,3,3,3,4,4$.