Washington State University Greedy Algorithm Correctness and Limitation Design Project

1. [60 pts] Solve the following exercises:Alsuwaiyel, Chapter 5, Exer: 16, 18, 32, 37(c, show steps).
Alsuwaiyel, Chapter 6, Exer: 8, 10, 21, 29(a,b), 30.
Alsuwaiyel, Chapter 7, Exer: 1, 2.
Total: 11 exercises.
Note: Your answers should be typed and saved as a pdf file for submission. Please
write your name and ID (in the header or cover page). Also make a side-header for
each question, like: Alsuwaiyel, Chapter 1, Exer 8:
2. [20 pts] Implement the recursive Fibonacci algorithm, FibRec(n). Test your algorithm
of some small values like n = 1 through 10 and make sure it is correct.
a. Experiment with large values of n like 50, 100, 150, … and so on, and monitor
the time it takes to run the algorithm (you may use a stopwatch or system
timer).
b. Plot the time graph for each different values of n.
c. What is the largest value of n you can compute in reasonable amount of time
(say 10 minutes).
3. [20 pts] Now implement the Fibonacci algorithm, Fib(n) using dynamic programming,
where you store and update the last two Fibonacci numbers, fi and ₤2, and then
compute fn=fi+f2. Repeat the same experiment you did in (2), and if possible,
increase the range you got in (2.b). Plot the graph and compare it with the one you got
in 2. Comment on the largest value you might compute using this algorithm.