In this project you are to implement several different hashing algorithms perform an empirical comparative analysis of their running times. The hashing algorithms to be implemented are:
- Linear hashing
- Chained hashing
- Cuckoo hashing
- At least one additional algorithm.
For the empirical analysis, run the algorithms on a variety of test cases to determine the relative efficiencies of the algorithms as functions of various parameters, such as the number of elements and the load factor. How do your results compare with theoretical predictions of worst-case and amortized-time. You are encouraged to consider other factors as well. For example, if you generate your test cases randomly, you how do your choices of probability distribution and the distribution parameters affect your results?
In this project you are to implement several different algorithms for storing, querying, and modifying ordered data, and perform a empirical comparative analysis of their running times. The data structures to be implemented are:
- Binary Search Tree
- AVL Tree
- Splay Tree
- Red-Black Tree
For each data structure you implement, you must at minimum implement the following operations:
- Create (i.e., create a data structure with no elements).
- Search
- Insert
- Delete