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. Note that in addition to reading from the book, you should read about bubble sort and selection sort, for example at http://en.wikipedia.org/wiki/Bubble_sort and http://en.wikipedia.org/wiki/Selection_sort .
  3. Complete Reading Quiz 9 on ANGEL.
  4. 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..
  5. Do the following written problem.  You can write them by hand, or do them on your computer and  print them out.  Bring a printed copy to the Day 26 class.
     

(15 points) In Weiss exercise5.8, you examined the efficiency of computing XN, 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, X11 = X1*X2*X8 (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 power to get the original X to those powers of 2.   Only multiply X^(2^i) into the product if the ith  bit of the binary representation of N is 1.   Your program should ask the user for X and N, and print XN. 

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.