Due: Thursday February 7th by 11:55 pm (REVISED)

Revisions History:
- Created Jan. 19th,2013

Assignment Goals:

1. Review/learn more Java features including interfaces.
2. Give you experience designing and implementing data structures in Java.
3. More practice with code craft requirements. See the code craft requirements document BEFORE you start this assignment.
4. Give you experience experimentally evaluating data structure performance.

In class we are spending a lot of time considering data structures that take a single key and support insert and search operations. What happens if you have more than one key?

Consider the problem of storing n 2 dimensional points where for each point p, p.x is an integer in the range 1...2^k, and p.y is an integer in the range 1...2^k. We want to support the following operations:

• insert(p) - insert point p into the data structure.
• query(s,b) - Add to Arraylist S references to all points in the data structure that are inside the rectangular query bounds b
• count(b) - Return the number of points in the data structure that are inside the rectangular query bounds b

We could simply create a list all n points and search the whole list for each query or count operations. This would give us an O(1) insert and O(n) query and count operations. But we can do better!

A quadtree is a recursive data structure for storing 2D points that is based on recursively subdividing a region into 4 equal sized quadrants. Each sub-quadrant is further divided until each point sits in its own quadrant.

A quadtree contains tree types of nodes: an internal node with four children, a node representing a quadrant containing a single point, and a node representing an empty quadrant.

One might represent a quadtree in Java as follows:

The query operation can be implemented as follows (Note: you can use an Arraylist instead of a Vector):

The insert operation can be implemented as follows:

For this assignment you are to do the following:

a) Create a Java interface called TwoDimDictionary that specifies insert, query, count and display operations.

b) Implement a simple TwoDimDictionary based on a Java Arraylist. You should create helper classes for representing points and query rectangles.

c) Implement a TwoDimDictionary based quadtrees as described above. Use the  helper classes for points and query rectangles created for part b).

d) Create a testing and evaluation class which generates random points and query rectangles and evaluates your two implementations of TwoDimDictionary.

e) Perform a careful experimental evaluation of your TwoDimDictionary implementations graphing the results. You will need to use a timing method like for example:

long startTime = System.nanoTime();  
methodToTime();  
long endTime = System.nanoTime();    
long duration = endTime - startTime;

Analysis the performance of the methods and make recommendations as to when one is preferable over the other.

Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing! You are to use only code that you have developed yourself for this assignment.

• Add a delete operation. How should it be defined?
• Perform an asymptotic analysis of the tree based TwoDimDictionary? What can you say about the worst case and average case? What kinds of input does the tree do well on? What kinds of input does it do poorly on? Does your asymptotic analysis agree with you experimental evaluation?