Assignment 7 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

• Have your name, UF ID, and discussion session number as comments at the top of your code.
• ONLY SOFT copy is REQUIRED.
• Jar all the files directly WITHOUT the dataStructures folder.
• For coding problems, put the complexity analysis and other non-coding parts of THIS question (if it has) in comments at the beginning of your code.
• For pen-paper questions, we only accept the following format file: Plain TEXT, PDF and DOC. Plain TEXT format is preferred. Name it as Qx.txt, where x is the sequence number of this question. For example, if Question 1 is a pen-paper question, put your solution to the file "Q1.txt"
• Getting correct results for the given test cases does not necessarily mean your implementation does not have any bugs; your code will be tested with additional test cases during grading.
• Grading rules of coding problems are available.
• Please download and check your jar file after your submission. Make sure the submission is correct.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial, if you have trouble with the classpath settings you could try reading this tutorial.

Unless stated otherwise, you are not allowed to use any classes from the dataStructures or the java.util packages.

For any coding question below, even in cases where you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
   super();
} 

public ALLExtended( int n ){
   super(n);
}

---

1. Hash Table

Given a hash table with 13 buckets (b = 13), and a hash function f(k) = k % b, insert the elements whose keys are: 52, 53, 114, 128, 12, 105, 147, 60, 139, 27, 92  in this order. Use linear probing to resolve collisions.

a) Draw the hash table after the last insert.

b) What is the loading density of your table after the last insert?

c) What is the maximum number of buckets examined in an unsuccessful search of your table?

d) What is the maximum number of buckets examined in a successful search?

e) Draw the hash table after the operation remove(53).

2. In previous homeworks, you have implemented some recursive methods. For some problems, they are effective. However, recursive methods usually consume a lot of program stack space, because they have to store all the local variables and the return address. To avoid this, we can implement them in a non-recursive way. (Each recursive method can be implemented in a non-recursive way)

In this problem you will turn two recursive methods into non-recursive implementations by using stacks.

PLEASE use one java files for one sub-question. Name them NonRecursiveFb.java and NonRecursiveFa.java respectively.

a) Implement a method int nonRecursive(int n), which computes the value of the nth term in a Fibonacci array without recursive calls.

The Fibonacci array is defined as

                       1                              if n=1;

Fb(n) =      1                              if n=2;  

Fb(n-1)+Fb(n-2)           otherwise

Hint: First, you push n into the stack, representing Fb(n). Then whenever you pop m out of stack, push m-1 and m-2 into the stack, unless you get the value of Fb(m).

The template is:

(There is a recursive implementation recursive(int n) given in the template to help you test your results.)

package dataStructures;

public class NonRecursiveFb {

ArrayStack stack_;

public int recursive(int n)

{

if(n < 1)

{

return -1;

}

if(n == 1)

{

return 1;

}

if(n == 2)

{

return 1;

}

return recursive(n-1)+recursive(n-2);

}

public int nonRecursive(int n)

{

//Your code goes here.

}

// Please use the test code as follows.

public static void main(String[] args) {

NonRecursiveFb nrf = new NonRecursiveFb();

System.out.println(nrf.recursive(40));

System.out.println(nrf.nonRecursive(40));

}

}

b) Implement a method int nonRecursive(int n), which computes the value of Fa(m,n) defined as follows.

n+1                       if m=0;

Fa(m,n) =  Fa(m-1,1)                if m > 0 and n=0;  

Fa(m-1,Fa(m,n-1))        otherwise

The template is:

(There is a recursive implementation recursive(int m,int n) given in the template to help you test your results.)

package dataStructures;

public class NonRecursiveFa {

ArrayStack stack_;

public int recursive(int m,int n)

{

if(m==0)

{

return n + 1;

}

if(n==0 )

{

return recursive(m-1,1);

}

return  recursive(m-1,recursive(m,n-1)) ;

}

public int nonRecursive(int m,int n)

{

        //Your code goes here.

}

// Please use the test code as follows.

public static void main(String[] args) {

NonRecursiveFa nrf = new NonRecursiveFa();

System.out.println(nrf.recursive(1,4));

System.out.println(nrf.nonRecursive (1,4));

System.out.println(nrf.recursive(2,5));

System.out.println(nrf.nonRecursive (2,5));

System.out.println(nrf.recursive(3,6));

System.out.println(nrf.nonRecursive (3,6));

}

}

Note: Fa(m,n) grows very fast with m. Don’t try to compute Fa(m,n) with m>3.