## 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