Description
1 Minimum Spanning Tree
Let G be an edge-weighted graph with n vertices and m edges satisfying the condition that all the
edge weights in G are distinct.
(a) Prove that G has a unique MST. (Hint: Use induction on the edges of MST computed by
Kruskal’s algorithm taught in the class). [5 marks]
(b) If it is given that G has at most n + 8 edges, then design an algorithm that returns a MST of
G in O(n) running time. [15 marks]
2 Huffman Encoding
(a) What is the optimal binary Huffman encoding for n letters whose frequencies are the first
n Fibonacci numbers? (For example: The frequency vector F is [1, 1, 2, 3, 5, 8, 13, 21] for
n = 8). What will be the encoding of the two letters with frequency 1, in the optimal binary
Huffman encoding? [10 marks]
(b) Suppose you aim to compress a file with 16-bit characters such that the maximum character frequency is strictly less than twice the minimum character frequency. Prove that the
compression obtained by Huffman encoding, in this case, is same as that of the ordinary
fixed-length encoding. [10 marks]
1
3 Graduation Party of Alice
(a) Alice wants to throw a graduation party and is deciding whom to call. She has n people to
choose from, and she has made up a list of which pairs of these people know each other. She
wants to pick a largest subset of n people, subject to two constraints: at the party, each person
should have at least five other people whom they know and five other people whom they don’t
know. Present an efficient algorithm that takes as input the list of n people along with the list
of pairs who know each other and outputs the best choice of party invitees. Give the running
time in terms of n. [15 marks]
(b) Suppose finally Alice invited n0 out of her n friends to the party. Her next task is to set a
minimum number of dinner tables for her friends under the constraint that each table has a
capacity of ten people and the age difference between members of each dining group should
be at most ten years. Present a greedy algorithm to solve this problem in O(n0) time assuming
the age of each person is an integer in the range [10, 99]. [5 marks]
2