CSCI 3104: Algorithms
Homework 6
1. Given the graph above, use Kruska’s algorithm and Prim’s algorithm to find the minimum spanning tree. Break ties using alphabetical order (e.g., if edges have the same
cost, pick (A, D) over (A, G) and pick (A, H) over (C, F). Show the order of the edges
added by each algorithm.
2. Given two sets A and B, each containing n positive integers, your goal is to reorder the
value in each set such that Qn
i=1 a
bi
i
is maximized, where ai and bi are the i-th value in
each set after reordering. Design a greedy algorithm and show that it is optimal.
3. A long string consists of the six characters A, B, C, D, E, F, G; they appear with
frequency 21%, 11%, 8%, 17%, 5%, 23%, and 15%, respectively.
(a) Draw the Huffman encoding tree of these six characters.
(b) What is the Huffman encoding of these six characters?
(c) If this encoding is applied to a string consisting of one million characters with the
given frequencies, what is the length of the encoded string in bits?
4. Given n jobs, the i-th job starts at time si and finishes at time fi
. Two jobs are
considered compatible if they do not overlap in time. Our goal is to find the maximum
subset of jobs that are mutually compatible. A greedy algorithm can be designed which
considers the jobs in a certain order and selects a job if and only if it is compatible
with the jobs that have already been selected. For each of the following three ordering
methods, determine if the greedy algorithm guarantees the optimal solution or not. If
yes, show a brief proof. If not, give a counter example.
(a) Earliest start time: Considers jobs in ascending order of si
.
(b) Earliest finish time: Considers jobs in ascending order of fi
.
(c) Shortest interval: Considers jobs in ascending order of fi − si
.
