Description
Problem 1 (30 Points) In a Fibonacci sequence, each number is the sum of the two preceding ones, starting from 0 and 1. The first 12 numbers of the sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Write a C++ program to find the nth number in a Fibonacci sequence using two different approaches. Each approach is implemented by a function that takes n as its only parameter. One function solves the problem only recursively. The other function solves the problem recursively but with the support of dynamic programming. For the dynamic programming implementation, you are allowed to define the needed array as a global variable. You are not allowed to use any loop in your functions. The only loop you will need in your program is the one in the main() function, right before calling the dynamic version function. You need this loop to initialize all elementsin the array to an invalid Fibonacci number (e.g., ‐1) to keep track of the array elements that do not have a Fibonacci number calculated yet. Test your code with n values 5, 10, 20, 30, 40 Submit your test program and in your report answer the following questions: a) Comment on the running time of each function. b) For each function, find the big O asymptotic notation of its running time growth rate. EECE7205 – ‐ Homework 6 3 / 4 Problem 2 (40 Points) Write a C++ program to compare the Recursive implementation of the Rod Cutting problem with the Dynamic Programming implementation of the same problem. The comparison should be in terms of each implementation running time for rod sizes: 5, 10, 15, …… , 40, 45, and 50 inches. Use the C++ clock function to measure the time consumed by each implementation in micro‐seconds. (Reference: http://www.cplusplus.com/reference/ctime/clock/) Use the following formula to calculate the price of each cut of length L inches: 2 if L = 1 Price = floor(L*2.5) if 1 < L < rod size (L*2.5)‐1 if L = rod size where floor is a C++ function that returns the largest integral value that is not greater than the value of its parameter. (Reference: http://www.cplusplus.com/reference/cmath/floor/ ) Based on the results from your program, fill the following table: (Note: if a run takes more than 2 minutes to finish, just terminate it and report in the table “no solution”). Rod Size Recursive Time Recursive Max Revenue Dynamic Time Dynamic Max Revenue 5 10 15 20 25 30 35 40 45 50 EECE7205 – ‐ Homework 6 4 / 4 Problem 3 (30 Points) Find the Huffman encoding tree and hence the Huffman code for each of the letter shown in the following letter‐frequency table: Letter Z K M C U D L E Frequency 2 7 24 32 37 42 42 120
