CS 100J Honours Autumn 2005 h/w 4 ... due Tuesday Nov 8 

1. Write a recursive program to compute terms of the Fibonacci sequence (initialise this with a[1] = 1 and a[2] = 1 as in lecture). Demonstrate its effectiveness by displaying both the answer and the numbers of 0's-9's in the answer (display this so that it's easier to see if your answer might be correct!). You should test this with the 100th term, a[100], of the sequence (ie display its value and its associated distribution of digits).

   You should also make a chart of the run times under various conditions. In particular, use the Calendar class (as done in lecture) to measure the run time of your program for a[30], a[40], a[50], a[60], a[70], a[80], a[90] when your method is couched in terms of long, and java's BigInteger class (long will only handle the answer up to a[93]). You might also like to see how far you can go using BigInteger, once you've cleaned up the recursive method, before your computer really starts complaining.

2. Think about the list and list iterator interfaces/classes used in the previous homework. What are their weaknesses and how might they be improved? Now make those improvements, and then do the same for queues, stacks, and binary trees. For binary trees, provide an appropriate iterator interface and class, checking that they work by building
   1. an explicitly tree-based recursive implementation of the heap sort described in the notes, and
      
   2. an explicitly tree-based binary search tree with recursive methods for the addition and removal of data
      
   (We will discuss removal of data from a binary search tree in Tuesday's lecture.)
   
   
3. Induction proof exercises. Prove each of the following by induction:
   1. The sum of the squares of the integers from 1 to n equals  n(n+1)(2n+1)/6  for n positive.
      
   2. The sum of the first n odd numbers equals  n^2  for n positive.
      
   3. A set having n elements has exactly  n(n-1)/2  subsets having exactly 2 elements.
      
   4. A polygon is said to be convex if every line joining two points of the polygon lies within the polygon (the boundary is treated as part of the polygon). Prove that the sum of the interior angles of a convex polygon with n sides is equal to  (n-2)π  if n is at least 3.
      
   
   
4. You should be thinking ahead more about the banking/commerce exercise from h/w 2 since this will be a major question on a next homework. Aim to improve the separation and modularity of classes, have interfaces and appropriate abstract classes, think about security and authentication schemes, ensure that classes and entities are as private as you can make them, think about ways of avoiding information leakage, and try to ensure that transactions are performed in such a way that money is neither lost nor created and that if a transaction fails for some reason, data intergrity is maintained. (Nothing to turn in on this question yet!) You will find the material on threads helpful, and you will be able to implement a decent GUI for interacting with the program as part of this future assignment.