Due 11:59pm Wednesday, 23 February 2011

For this assignment, you will explore multiple implementations of an ordered lis. You will primarily implement a `SkipList` which allows fast searching for data and fast updates. You should save your programs in your `cs35/labs/05` directory. You may work with one partner on this assignment. If you work with a partner, be sure to put both names on your assignment when submitting.
`cs35/homework/05` folder, you will find a description of an
`OrderedList` interface in `orderedList.h` for storing a collection of `integers` in
sorted order. A student directory is also an `OrderedList`, sorted
alphabetically by last name, but for simplicity in this assignment, we are just
storing integers. Review the interface description in `orderedList.h`
and be sure you understand what each method is trying to do before you
implement it. Note that the `insert` method must add a new element to the
list in sorted order (smaller integers first). The `find` method just
returns a Boolean value indicating if the particular item or *key* was
found in the list. Note it is possible to store more than one copy of the same
integer in the `OrderedList`. Your assignment is to implement and test the
`OrderedList` interface in three different ways: using a LinkedList,
using an ArrayList, and implementing a new structure called the SkipList. The LinkedList and ArrayList implementations have been completed for you. You will just need to test these. You will need to both implement and test the SkipList
`get` and `find` methods than the LinkedList, updates (`insert` and `remove`) are still slow in both implementations. You will implement a `SkipList` from scratch to allow faster updates. A description of `SkipLists` can be found in section 8.4 of your text on page 394. A simple implementation of a `SkipNode` is included in your homework folder. Feel free to modify this class if you do not like it. Your `SkipList` class must also implement the `OrderedList` interface.
`insert, remove, get,` and `find`, describe which implementations you think gives the best/worst performance. You do not have to give big-Oh run times.

Ordered List

In you SkipLists

While an ArrayList implementation offers faster The `SkipList` might seem overly complicated at first, but draw a few examples on the board or trace through some examples in the text. It will be helpful to implement `SkipSearch, SkipInsert,` and `insertAfterAbove` according the book's description. Once these are implemented, you should find that many of the methods in the `OrderedList` interface can be implemented on top of these methods.

Psuedocode for `SkipSearch` and `SkipInsert` are included below. Some details on degenerate cases have been omitted. You will need to add in these cases.

SkipSearch(k): //return a pointer to the SkipNode on the bottom level which //has the largest value <= k p = upperleftmost skip Node while the node below p is not null: p = below(p) while value(after(p)) <= k: p = after(p) return p SkipInsert(k): //Inserts a new tower of nodes containing the value k into the skip list //in sorted order p = SkipSearch(k) q = InsertAfterAbove(p, NULL, k) while a coinflip is heads: while above(p) is null: p = before(p) p=above(p) q=InsertAfterAbove(p,q,k) //TODO: if p is upperleftmost skip Node then add a new level

The book refers to special nodes that store the values positive and negative infinity. In C++, you can use the special values `INT_MAX` and `INT_MIN` from `<climits>` to represent these limits. You can use these numbers just like any other integer.

Think about how to implement `get` and `remove`. You implementation of `get` does not need to be fast. An `O(n)` algorithm is fine.

Tips

Draw pictures to help you visualize.
If you do not implement the TODO item `if p is upperleftmost skip Node then add a new level` mentioned in SkipInsert, it will be hard to insert more than a few elements.

Be careful to note which `SkipNode` links could be NULL and handle them correctly.

The book has psuedocode showing `rand() < 1/2`. In C++, rand() returns an integer. So do not use the condition described in the book to implement a coinflip.

Submitting

Along with your C++ source code, you should hand in a file named README. Your README should include a brief summary of your results, including a discussion of the advantages/disadvantages of the three implementations of OrderedList. Describe how you tested your implementations. Do you have any problems/bugs in your code? For each of the following operations: