# Explain (and implement) stuff to the instructor!

- Due Jul 20, 2017 by 11:59pm
- Points 100
- Available May 30, 2017 at 12am - Jul 20, 2017 at 11:59pm about 2 months

During their past experiences offering CMSC420 as a TA, the instructor has had monumental trouble understanding two opace algorithms operating on advanced data structure:

- Robson Traversal. Robson Traversal achieves the exact same result that threaded trees and link inversion achieve; stackless, amortized constant inorder successor search. However, when compared to threaded trees and link inversion, the space overhead is constant, consisting of about 5 pointers. The instructor also has access to pseudocode that implements the traversal, but the sheer fact that they do not understand the algorithm given the pseudocode should be some evidence of either their low IQ or the intellectual opaqueness of the algorithm, or both!
- The Gunnot-Monroe algorithm for ordered hashing with collision chain re-organization (e.g slide 15 here). Gunnot-Monroe builds upon the experience of Brent's Method, which we will discuss in class and with which we will likely conclude the discussion on single-dimensional hashing. The instructor has material outlining the algorithm, but still misses the point.

In both cases, thorough experimental comparisons with the data structures that solve the same problem, albeit less efficiently, will have to be made. For example, for GM, a thorough comparison with both ordered hashing and Brent's Method will have to be made. For RT, compare the approach with both threaded trees and link inversion. The spatial benefit is clear: if you can experimentally prove that your implementation compares well in terms of time with both threaded trees and link inversion (in fact, it will probably beat link inversion)

### Suggested workflow

- If you are familiar and comfortable with it, consider using C for either one of these projects. The object-oriented framework is generally excellent for Data Structures, but when dealing with such low-level data structures where efficiency is key, it is always helpful to go as close to assembly as possible (hint: run gcc -S on a C source file to see the assembly output for your processor's ISA).
- Implement Brent's method and compare it to regular ordered hashing. Make sure you can achieve improvements in time overall.
- Implement G-M and compare it to Brent's. Pin down increases in spatial cost.

### Grading

- The full, thoroughly tested, implementation of either data structure gets you 5% off of the total 10% extra credit. Possible to split this project across 2 people, where the different parties choose the algorithm to implement.