Search:

Labs

Homeworks

# HW7: Due Friday 30th March before Midnight

Q1. (10 points) Given a undirected, weighted graph G=(V,E). Assume that no two edges have the same weight. Prove that there is a unique minimum spanning tree (MST) for such a graph.

Q2. (10 points) Consider the following algorithm for finding a MST. Given a graph G=(V,E), sort the edges in decreasing order of their weights. Pick each edge e in sorted order, and if e creates a cycle in G, remove it from G. Note that each time you remove an edge, you are modifying the graph, so that the next check for a cycle will be on the reduced graph. Prove that this method is correct, and analyze its running time.

Q3. (10 points) Consider the problem of a constrained MST. Given a weighted, undirected graph G=(V,E), and given a subset of vertices $$C \subseteq V$$, describe a method to find a constrained MST such that vertices in C only appear as leaves in the constrained MST. What is the running time of your algorithm? Note that for some choice of C, it may be the case that the constraint cannot be satisfied, i.e., it may be the case that there is at least one vertex in C that cannot be made a leaf node. In these cases, you can output that the constraint cannot be satisfied.

Q4. (15 points) Given an alphabet with n characters. Let the characters be numbered from 1 to n, and let the frequency of character $$i$$ be $$f_i = \frac{1}{2^i}$$ for $$i=1,2,...,n-1$$, with the last character $$n$$ having frequency $$f_n = \frac{1}{2^{n-1}}$$. For example, if n=6, then the frequencies of the first five characters are 1/2, 1/4, 1/8, 1/16, 1/32, respectively, and the frequency of the last character is 1/32. Answer the following questions:
a) (5 points) Show that the frequencies of all characters sum to 1 (as they should) for any $$n$$.
b) (5 points) Show what the huffman encoding is for each character. In building the encoding tree, the larger frequency child should be on the left, and if there are two groups of characters with the same frequency, the one with the smaller index should be on the left.
c) (5 points) What is the expected number of bits per character? Let the encoding length of character $$i$$ be denoted as $$l_i$$, then the expected or average number of bits for the encoding is computed as $$\sum_{i=1}^n l_i \cdot f_i$$. Use this formula to derive an closed form expression (for any n).