Helena Wong, 2001

1. 
   We have studied a recursive strategy (step 2 of dynamic programming), a dynamic programming approach and a greedy strategy approach that solve the activity-selection problem. Describe how these approaches work, using the following example:
   

Activities sorted in increasing order of finish time:

start_time_i 0 3 4 6 5 9 10 11

finish_time_i 3 4 7 8 11 11 12 14

2. 
   For the activity-selection problem, suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm.
   

3. 
   a.) State the key ingredients of dynamic programming.
   

2. 
   State the key ingredients of greedy algorithms.
   
3. 
   Given an optimization problem, how do you determine an appropriate approach to solve it?
   

4. Give a dynamic-programming solution to the 0-1 knapsack problem.

5. Give a greedy-algorithm solution to the fractional knapsack problem.

6. Fibonacci numbers are defined by the following recurrence:

F₀ = 1, F₁ = 1, F_i = F_i-1 + F_i-2
What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers? Describe your observation.

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