CSSE 220 -- Object-oriented Software Development

Homework 25 Due at 8:05 AM on Day 26

Written problems due at the beginning of your class meeting Day 26.
 

1. Complete the assigned reading for the next session (see the course schedule). If there is something you do not understand, make a note of it so you can ask about it in class. 
2. Continue thinking about and writing the spell checker program.  Work with your team.  You should have something working to demonstrate in class on Day 27.
3. Do the following written problems.  Bring printed copies to the Day 26 class.

a. (15 pts) Write a recursive method to compute the Nth number in the Fibonacci sequence. The 0th Fibonacci number is 0, the 1st Fib # is 1, and each successive one is defined as the sum of the two previous ones. Thus the sequence is: 0 1 1 2 3 5 8 13 21 34 55 89 ... (If you compute Fib(10) == 55, you don't have any off-by-one errors.)

b. (15 points) In Weiss exercise 5.8, you examined the efficiency of computing X^N, where X is a double value and N is an integer.  That algorithm is O(N) if we ignore the increasing size of the numbers to be multiplied.  It turns out we can do a lot better; there is an algorithm that is O(log N).  Write and test code that does this. Hint:  Base your algorithm on the binary representation of N.  For example, X¹¹ = X¹*X²*X⁸ (Note that 11has one-bits representing 1, 2, and 8).   So you can write N as a sum of powers of 2.  Start with power=X,  and keep squaring powers to get the original X to those powers of 2. Only multiply X^(2^i) into the product if the i^th  bit of the binary representation of N is 1.   Your program should ask the user for X and N, and print X^N. 

You can just write the code out by hand if you wish, but I recommend getting it working in Eclipse and printing out your code.

Bonus (10 points): implement this same algorithm recursively! It's not that hard, actually!