Skip to content

Week 8 - Greedy Algorithms

Assignment - Due 11/17/2018

Credit: source code of questions are from walkccc.

16.1-1

Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence \text{(16.2)}. Have your algorithm compute the sizes c[i, j] as defined above and also produce the maximum-size subset of mutually compatible activities.

Assume that the inputs have been sorted as in equation \text{(16.1)}. Compare the running time of your solution to the running time of \text{GREEDY-ACTIVITY-SELECTOR}.

16.1-2

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

16.1-3

Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time.

16.1-5

Consider a modification to the activity-selection problem in which each activity a_i has, in addition to a start and finish time, a value v_i. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set A of compatible activities such that \sum_{a_k \in A} v_k is maximized. Give a polynomial-time algorithm for this problem.

16.2-1

Prove that the fractional knapsack problem has the greedy-choice property.

16.2-2

Give a dynamic-programming solution to the 0-1 knapsack problem that runs in O(nW) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack.

16.3-1

Explain why, in the proof of Lemma 16.2, if x.freq = b.freq, then we must have a.freq = b.freq = x.freq = y.freq.

16.3-2

Prove that a binary tree that is not full cannot correspond to an optimal prefix code.

16.3-3

What is an optimal Huffman code for the following set of frequencies, based on
the first 8 Fibonacci numbers?

a:1 \quad b:1 \quad c:2 \quad d:3 \quad e:5 \quad f:8 \quad g:13 \quad h:21

Can you generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers?

16.3-4

Prove that we can also express the total cost of a tree for a code as the sum, over all internal nodes, of the combined frequencies of the two children of the node.