Description
1. Design a greedy algorithm for arranging the queuing order in a supermarket. Suppose there are n
customers come to the counter at the same time, noted as c1, c2, . . . , cn, the time to service i-th customer
is si
, i = 1, 2, . . . , n, and the absolute time to finish i-th customer is Ti
, i = 1, 2, . . . , n.
Your goal is to
decide a queuing order of n customers to minimize the accumulated completion time (waiting time +
service time) of all n customers, that is, to minimize Pn
i=1 Ti
.
(a)
Provide an algorithm to solve this issue;
(b) Prove the correctness of your algorithm by showing the greedy choice property and optimal substructure;
(c) Justify the running time of your algorithm.
2. How many bits are required to encode the message ”aaabccxxxyyyyzz” using Huffman Codes? Please
show the coding tree you build.
3. Consider the following graph.
(a) If we run Kruskal’s algorithm in the graph, what will be the sequence in which edges are added to
the MST?
(b) Demonstrate Prim’s algorithm in the graph with A as the source.
4. Let G be an n-vertex connected undirected graph with costs on the edges, and the number of edges is
m = O(n
2
). Assume that all the edge costs are distinct.
(a) Prove that G has a unique MST;
(b) Give an algorithm to find a cycle in G such that the maximum cost of edges in the cycle is minimum
among all possible cycles. The time complexity of your algorithm should be O(m log n). Assume
that the graph has at least one cycle, and finding MST takes O(m log n) time.
