Labs Homeworks |
## HW7## HW7: Due Friday 30th March before MidnightQ1. (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: |

Page last modified on March 25, 2018, at 10:12 PM