Goals

Huffman’s coding, network flow, NP-completeness and reducibility

Questions

1.  Huffman Coding:

(a)  Show the Huffman trie that results from the following distributions (frequencies in parentheses):

colon  (100),  space  (605),  comma  (705),  0  (431),  1  (242),  2  (176),  3  (59),  4  (185),  5  (250),  6 (174).  (To make the trie fully-specified, put the lower-weight subtree on the right on each merge operation.  Start by listing the weights in increasing order from left to right, with their symbols below them on the next line, leaving space above to build trees.

(b) What is the resulting binary code for the most frequent symbol? The least frequent?

(c) With the coding scheme above, code the 7-symbol text  “04:  12,” .  Show the binary string and the bytes in hex.

(d) With the coding scheme above, decode 011101001011001.

2.  Max-Flow-Min-Cut:  K&T 7.2:  Given the following flow network on which an s-t flow has been computed. The capacity of each edge appears as a label on the edge, and the numbers in parentheses give the amount of flow sent on each edge.  (Edges without parentheses – specifically, the four edges of capacity 3 – have no flow being sent on them.)

(a) What is the value of this flow? Is this a maximum (s,t) flow in this graph?     (b)  Find a minimum s-t cut in the flow network and also say what its capacity is.

3.  Max-Flow-Min-Cut:  K&T 7.3:  Given the following flow network on which an s-t flow has been computed. The capacity of each edge appears as a label on the edge, and the numbers in parentheses give the amount of flow sent on each edge.  (as before, edges with no parentheses have no flow being sent on them.)