TDDC32 Design and implementation of a software module in Java

Lab 1 - Data Structures and Algorithms

Your task - part 1

Suggested reading: Goodrich/Tamassia Ch. 10.1-10.2

Your task is to finish the implementation of the method void delete(AVLTreeNode node, double val) in the following AVL tree implementation. Note that you should check also the methods void rebalance(AVLTreeNode node) and void restructure(AVLTreeNode node) so they work correctly with deletion.

Your task - part 2

Suggested reading: Goodrich/Tamassia Ch. 9.2

In the second part of the lab you will implement and perform experiments on hash tables. The provided LinearProbingHashTableMap specializes (i.e. is a subclass of) the abstract HashTableMap (which in turn implements a Map). Your first objective is to understand how the linear probing hash table implementation works. Compile the code and write a short test program to explore its functionality.

NOTE: In order to be able to compile your LinearProbingHashTableMap.java and HashTableMap.java you need the other classes which the hash table uses. Hence, first download the java.datastructures.net package to some place convenient. To add a library of classes to your project, select the project containing lab 1, select Properties -> JavaBuildPath -> Libraries -> Add External JARs and then find and select the downloaded .jar.

You will now implement two new subclasses of HashTableMap:

1) QuadraticProbingHashTableMap, making use of Quadratic probing

2) DoubleHashingHashTableMap, making use of Double hashing

When you are convinced that your new hash table implementations are correct you are now to perform some experiments. This is done by disabling rehashing and testing the "speed" of insertions to the hash table by measuring the total number of probes in the hash table it takes to fill in every 5% of the table as the table grows in size. A probe is when a cell in the hash table is checked to see if it is empty so that the value can be stored there. Each insertion has a certain number of probes (only 1 if there is no collision). The total number of probes is the sum of all probes for all insertions until the measurement. Thus, you should count how many probes it took until the table is 5% filled and then at 10%, etc. until you reach 100% of the input data. The size of the input data should match the size of the hash table. The input data should be strings read from this Unique Words File. Note that the file contains a large number (10000+) of words and maybe you don't need to read them all. For example if you set the size of your hash table to 5153 then you should read 5153 words (as separated by whitespaces "\n", "\t" or " ") of the input file and try to insert them in the hash table. Observe that, with quadratic hashing, it is possible that even if the table is not full, the hash function cannot find new places to insert (due to clustering).

Finally you should plot a comparison of these hashing methods. On the x axis will be the loading factor (i.e. 5%, 10%, ..., 100%) and on the y-axis the total number of probes needed to insert the data until that moment. In order to test the hash table you should implement a method (i.e. a main() method) that does the previously described work, and of course the methods for quadratic hashing and double hashing. Since the hash table is implemented to accept a key-value pair, use the string key for both hashing and storing as the value.

Help with Eclipse

The easiest way to introduce a new class in Eclipse is to create a new class in the right package and to cut and paste the content of the class inside. Alternatively you could save the .java file in some directory and then right click on the right package, choose Import -> File system, find the file's parent directory, and select the file.

If you have trouble with the use of the term "pointers" in Java (e.g. if you mainly programmed in C++ before), please see some illustrative examples concerning this topic.

Page responsible: Tommy Färnqvist
Last updated: 2013-01-15