Submission instructions

- Due date: Friday, Nov. 18, 11:59 pm Central Time (i.e. local time in Chicago)

- Late submissions and submissions violating these instructions will NOT be accepted.

- Absolutely no handwritten submissions. No credit will be givenfor such submissions.

- Teamwork is allowed (max. 4 students/team). Individual submissions are also OK.

- Upload thefollowingfiles to Blackboard:

- (1) your HW report (pdf format only; the reports in formats other than pdf will be disregarded); - (2) the source codes of your programs.

The Beacon students: upload your submissions to LMS.

- One submission per team only. Write down names, A#, and section numbers (i.e. live, online, Beacon) of all the team members on the front page. Do not submit multiple copies of your assignment (e.g. by each team member). It is very confusing and will be penalized. Clearly indicate how each team members contributed to your teamwork.

- If you use any additional materials to solve the HWproblems (e.g. textbooks, research papers, websites, etc.), reference them.

- Hao Ding (hding9@hawk.iit.edu) is responsible for grading this assignment. Feelfree to ask questions if you have any doubts but don't send him or me:

- Your partial solutions with inquiries  “Is that what you expect?”.

- Questions the answers to, may give explicit hints on how to solve the problems.

1.   The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … is defined for n ≥ 2 by the recurrence F(n)=F(n-1)+F(n-2) with F(0)=0 and F(1)=1.

(a) (2 points) Calculate recursively F(n) by applying the top-down procedure Fib() which calls itself.  Use  your  favorite  programming  language  to  write  Fib( ).  Test  Fib( )  for  different numerical values  of n to make  sure that Fib(n) correctly calculates F(n). You can use the formula for F(n) given in item (f) below to check your numerical results.

(b) (2 points) Draw the recursion tree for Fib(5). Let's denote by T(n) the total number of calls to Fib() needed to calculate F(n) (note that T(n) includes the original call to Fib(n) at the root). What is the value of T(5)?

(c) (4 points) What is the recurrence for T(n)? What are the initial conditions of this recurrence?

(d) (2 points) Use Fib() to empirically verify that T(n)=2F(n+1)-1.

(e) (4 points) Given the recurrence for T(n) found in item (c) above, prove by induction that the formula T(n)=2F(n+1)-1 is correct.