CSE373 Data Structures Sp07, Homework 4

Electronic Turn-in of code due: 11am Wednesday, 5/09/07 using this link.
Written Problems and printout of code due: At the beginning of class, Wednesday, 5/09/07
No late assignments will be accepted.

For this assignment, (if you wish) you may work with one partner for the programming portion of the assignment.  Each partner needs to do and submit his or her own solution to the written problems.  The amount of code that needs to be written is not large, so it may not be easy to divide the work into independent pieces.  Any two people working as partners are likely to need to work together closely throughout the process, probably writing all of the code together.  Pair programming may be a good approach to try for this assignment.  Pair programming is a technique that is a part of Extreme Programming approaches used in some software companies.  Here are a few references on pair programming:  [as part of Extreme programming (XP)] [pair programming in Computer Science courses].  Note: You are not required to work in pairs – working individually is fine.

If you plan on working pairs: one partner MUST send email containing the names and email addresses of both partners to Anna by 11:59pm Friday May 4th  (o.k. really the hard deadline is Sunday May 6th but you will forget if you wait that long).

Written Problems (To be done individually)

Note that while you are not required to show your work for these problems, showing your work may allow partial credit to be awarded.

  1. Disjoint Sets: Show the result of the following sequence of operations: (note that in this exercise the parameters to union are arbitrary elements that may not be the name of a set, a find would need to be performed to find the set name)

 

union(1, 2), union(3,4), union(3,5), union(1,7), union(3,6), union(8,9), union(1,8), union(3,10), union(3,11), union(3,12), union(3,13), union(14,15), union(16,0), union(14,16), union(1,3), union(1,14)

 

a)      Using union where the set containing the second parameter should be added to the set containing the first parameter (retaining the name of the set containing the first parameter).

b)      Using union by size (number of nodes) as described in class.

 

2.   Disjoint Sets: For your final answers to both a and b above, perform a find with path compression on one of the deepest nodes.

Programming (May be done in pairs)

One application of BSTs is to implement ordered sets.  A set is a container that stores a collection of items with no duplicates; attempting to add a duplicate item to a set has no effect.  An ordered set is a set with the additional property that when we iterate through it, we retrieve the elements in order as defined by the comparison function for those elements.  Note that this is different from the disjoint sets we discussed in class and referred to above in the written problems that have the operations union and find.  Here we are representing a single set, and the values in the set have an ordering.

For this assignment, create Java interfaces for ordered sets and their iterators and implement those interfaces using splay tree as the underlying data structure. Specifically, define and implement the following two interfaces:

  1. Interface BasicSet. This is the interface describing the set operations.  Include the following:
  2. Interface BasicSetIterator. This interface specifies iterator operations for a BasicSet.

Because this is a sorted set, the items in the set must have type Comparable, meaning that whatever kind of objects they are, they implement the Comparable interface, which includes the compareTo() method. The ordering specified by compareTo() is the one that determines the order in which the items are returned from the set by successive calls to the iterator's next() method.

After defining the interfaces, create an implementation of BasicSet in a class named BasicOrderedSplayTreeSet. That class should contain a nested class BasicOrderedSplayTreeSetIterator that implements the BasicSetIterator interface.

Constraints

  1. Your implementation of BasicOrderedSplayTreeSet must use a Splay tree to store the set items.
  2. Tree nodes should be defined as a private class inside BasicOrderedSplayTreeSet.  A tree node should contain a reference to the item stored at that node and single links to the node's left and right children, plus a pointer to the parent node.  (you may add more information if desired).
  3. Use a single instance variable in BasicOrderedSplayTreeSet to refer to the root node of the tree. This should be null for an empty tree.
  4. Your tree methods should only traverse necessary parts of the tree. For instance, contains() should only search the left or right subtree of a node when looking for a particular item.
  5. Iterators will not affect the shape of the underlying splay tree.  In other words, do not “splay” every time an element is touched by an iterator.
  6. Calls to add(item) and contains(item) should splay those values to the top of the tree.

Simplifying Assumptions

  1. You only need to implement the listed operations for your set. You do not need to implement all of the set operations provided by the standard Java collection classes.
  2. Similarly, you do not need to implement previous(), hasPrevious() or remove() for the BasicSetIterator.
  3. Note that we are not asking you to implement remove()! J
  4. Your code does not need to use generics.  As long as it works with arbitrary Comparable objects that is sufficient.
  5. You are not required to provide a comprehensive set of tests for your code.  However, you do need to test your code.

Hints

Instead of trying to implement everything at once, it would probably be easier to implement the set as a regular binary tree first, then add the necessary code to do splay operations.

The splay tree representation is quite similar to that needed for the AVL tree, with two changes. First, there is no need to store an AVL balance factor or tree height in each node. Second you should add a "parent" pointer to each node that refers to that node's parent. To be efficient, splay operations require fast access to parent nodes.  You may find the AVL code from the book a useful starting point.

If you are rusty on iterators, you may find these slides and this linked list code useful.  (Although you do NOT need to know the material on JavaDoc or understand the code in BasicLinkedListTest.java that uses JUnit – but feel free to take a look!)

What to turn in

Please submit your Java source code for both the interfaces and implementations of the tree set electronically as individual files (not zipped into one file) using the turn-in link here.  Please also print out these files and bring them to class on the due date with your answers to the written problems.

If you work with a partner, 1) only one partner needs to submit the code electronically and make a printout.  2) Be sure that both partners’ names are listed in all files.  3) Include a text file (submit electronically and print out) that describes how you developed and tested your code.  If you divided it into pieces somehow, describe that.  If you worked on everything together, describe the actual process used – how long you talked about what, how long and in what order you wrote and tested the code.  Be sure to describe at least one good thing and one bad thing about the process of working together.  (Remember both partners need to submit individual answers to the written problems.)