CSE 373 Data Structures Sp08, Homework 4

Electronic Turn-in of code due: 11:59pm Thursday, 5/08/08.
Written Problems and printout of code due: At the beginning of class, Friday, 5/09/08

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 Tian by 11:59pm Monday May 5th .

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 (draw the up-tree) 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. Break ties by adding the set that contains the second parameter to the set containing the first parameter.

 

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.  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 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 a 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. (For example for integers this would mean returning values in increasing order.)

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. (Note: If the call to add(item) attempts to insert a duplicate value, the duplicate should not be added, but the original value should splay to the top. If a call to contains(item) returns false, it should splay the last (deepest) node in the access path 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. (Note that we are not asking you to implement remove()!)
  2. Similarly, you do not need to implement previous(), hasPrevious() or remove() for the BasicSetIterator.
  3. You can assume that the set will not be modified while you have an iterator running.

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.

Although the book contains an implementation of a top-down splay tree in chapter 12, this is not what we discussed in class and is not likely to be very useful. To be clear, you should NOT submit code for a top down splay tree for this assignment.

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) via catalyst. 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.)