Supplementary Exercises:
When too much DAT is barely enough!

Recursive Performance Analysis

1. In Exercise Sheet 5 you implemented a data structure StackCharLinked for holding a stack of chars. Modify this to provide a more general stack StackLinked of Objects.

2. In a new class called HoldsWhat, write a recursive class method:
   • isStackOfStrings(Object ob): returns true if Object ob is a StackLinked of Strings, and false otherwise.

   Thus the method should return false if it is passed a null reference, an object other than a StackLinked, or if the stack holds anything other than Strings. (You are not expected to optimise the code.)

   Hint: Look at the code for Pair.equals() in the DAT Notes for inspiration.

   Write a small test program to ensure that your method works as expected.

3. Perform an asymptotic time analysis of your isStackOfStrings method. Note any assumptions you make. You should find a recurrence relation and a closed form expression for the time taken with respect to stack size. What is the time complexity (smallest `big O') of the method?

Trees

1. Write a method toString (and any supporting methods needed) that returns a string representation of your tree, where each subtree is indented by two more spaces than its parent.

   Thus the tree:

   		                  a
   		               /     \
   		             q         r
   		           /   \      /  \
   		         w      e   null  null
   		       /   \   /  \
   		   null  null null null
   	    

   would be printed out as:

   a
     q         // a's first subtree starts here
       w       // q's first subtree 
       e       // q's second subtree
     r         // a's second subtree starts here
   	    

   As usual test your method by creating some trees and printing them out.

   Note that this is the easiest way to print a tree, as it corresponds to a depth-first traversal. The easiest way of implementing toString is of course, therefore, recursively.

   Hint: Delegate the printing of each TreeCell to the TreeCell itself!

   If you are having trouble with this, start by printing a non-indented version, so the above tree would print:

   a
   q 
   w 
   e 
   r 
   	    

   Once you have done this try adding the indentation.

2. A Royal Tree can be built by associating, with each person in a royal family, their next eldest sibling (if any), and their eldest offspring (if any). For example, the following diagram shows part of the Royal Tree for a typical royal clan:

      liz -> null
       |
       v
     chuck -> anne -> andy -> eddie -> null
       |        |       |       |
       |        v       v       v
       |       null    null    null
       v
      bill -> hank -> null
       |        |
       v        v
      null     null

   Store this or your own family tree using your BinTree ADT and modify your toString method so that it prints the tree out in the following form:

   --> liz
      --> none
      --> chuck
         --> anne
            --> andy
               --> eddie
                  --> none
                  --> none
               --> none
             --> none
          --> bill
             --> henry
                --> none
                --> none
             --> none

3. *Challenge*

   Finally, modify your toString method(s) so that it prints out trees in the following, more elegant and readable, form:

--> liz
     |
     +--> none
     |
     +--> chuck
           |
           +--> anne
           |     |
           |     +--> andy
           |     |     |
           |     |     +--> eddie
           |     |     |     |
           |     |     |     +--> none
           |     |     |     |
           |     |     |     +--> none
           |     |     |
           |     |     +--> none
           |     |     
           |     +--> none
           |      
           +--> bill
                 |
                 +--> henry
                 |     |
                 |     +--> none
                 |     |
                 |     +--> none
                 |
                 +--> none

Binary Search

1. Write code for a method needed(n) which returns the maximum number of calls to bSearch (from the DAT Notes section on Maps) needed to search for an item in a block of size n.

2. We have shown in the Maps section of the Notes that the number of calls to bsearch for a list of size n is given by T_n = log₂ n + 1 for cases where n is a power of 2. For cases where n is not a power of 2, T_n is greater than log₂ n +1. For example, T₇ = T₈ = log₂ 8 + 1 = 4. However log₂7 < log₂8, so T₇ > log₂ 7 + 1. Show that, despite this, T_n is O(log₂ n).

   Hint: Compare T_n with log₂ n + 2. To deal with the `2' you might use the fact that 1 < log₂ n for n > 2.

Arrays

1. Part of an implementation for a 2-dimensional Array using a lexicographic ordering was covered in an exercise in Section 11 of the DAT Notes. Complete this implementation.

2. Re-implement your Array ADT using a shell-ordered addressing function.

3. Change your constructors so that they reserve blocks which are four times the size required to accommodate the array dimensions. (This is rather artificial - the idea is to simulate the availability of a larger block of memory.)

   Now add to each of your arrays a method extend(m,n) that increases the number of rows in the array to m and the number of columns to n and throws an exception if the change cannot be accommodated. (Your method must of course relocate any items as necessary. Your test program should check that the items can be accessed at the correct addresses in the resulting array.)

Hash Tables

Store this information in a Hashtable (from java.util) with an initial size of 4 and a load factor of 0.5, using the Artist/Group as a key. Add some of your own records. Then retrive all the records and print them out in a list.

Hint: Java's Hashtable stores keys along with objects containing the "record" of information. (There are of course no records in Java as there are in Pascal. There is no need for them - objects are far more versatile.) Create a class Record to bundle up the information to be stored alongside the key.