1 Coursework Specification
Your assignment is to study the performance of operations on an Abstract Data Type, based on numerical data generated from your UoB number. Use an existing random number generator1 that will create collections of 100 integer keys, with values in the range [0, N], where N is your UoB number. You will run your algorithm in the following cases:
1. K = 10 times;
2. K = 100 times;
3. K = 1, 000 times;
and will report for each case the average execution time2 calculated as the number of operations S divided by K.
Submission Guidelines
Your submission must be a zip archive containing plain text (.txt, .java) and pdf files uploaded to the module's Blackboard assessment section. The name of your zip archive must be your UoB number. The content of your submitted files must be as follows.
1. The results file which is a plain text file titled results.txt that has
- Your UoB number in the first line.
- One section from:
- Hash Table Insertion with Linear Probing
- Hash Table Insertion with Secondary Hash
- Binary Search Tree Insertion as detailed below.
2. Your full running code (Java files) that implements your results.
3. Your comments of up to 2 pages on how your results compare with the published time complexity of the chosen algorithm. This will include results from executing your program, knowledge of expected execution time, critical review and discussion of the results, making use of references, tables and/or graphical representations. This will be submitted as a pdf file titled comments.pdf.
4. Nothing else! For example, although you might well find it convenient to draw the various trees as you construct them, do not include such diagrams in your submission.
3 The ADTs
Hash Table Insertion with Linear Probing
The task here is to show, and count, the trace of operations needed to insert the randomly generated keys, one by one, into an initially empty 101-bucket hash table with:
- (primary) hash function h1(x) = x mod 101
- using linear probing for collision resolution.
Your Java code should keep count of the number S of hash table operations, and the average execution time for each case S/K should be printed out. The hash table operations are coded as follows:
- Pn to probe bucket n (to see if it already contains an entry);
- Ixx@n to insert key xx into bucket n;
Your results.txt file should have the coded operations in sequence, e.g. if the first 3 values to be inserted are
15012340, 250, 306 the results.txt file would start:
15012345
Hash Table Linear Probing 1) K=10
P3 I15012340@3 P48 I250@48 P3 P4 I306@4 ...
Number of steps required S=150
Average number of steps per key: 150/100=1.5
2) K=100
...
Note that you only need to print out the sequence of operations once!
Hash Table Insertion with Secondary Hash
The task here is the same as Hash Table Insertion with Linear Probing except that collision resolution is performed by using the secondary hash function h2(x) = (x mod 5) + 1 to calculate the increment from the collision index. Your results.txt file should include the section heading
Hash Table: Secondary Hash
Your Java code should keep count of the number S of hash table operations, and the average execution time for each case S/K should be printed out. The hash table operations are coded as follows:
- Pn to probe bucket n (to see if it already contains an entry);
- Ixx@n to insert key xx into bucket n;
Your results.txt file should have the coded operations in sequence, e.g. if the first 3 values to be inserted are
15012340, 250, 306 the results.txt file would start:
15012345
Hash Table Linear Probing 1) K=10
P3 I15012340@3 P48 I250@48 P3 P4 I306@4 ...
Number of steps required S=150
Average number of steps per key: 150/100=1.5
2) K=100
...
Note that you only need to print out the sequence of operations once!
Binary Search Tree Insertion
The task here is to show, and count, the trace of operations needed to insert the K randomly generated keys, one by one, into an initially empty binary search tree.
Your Java code should keep count of the number S of binary search tree operations, and the average execution time for each case S/K should be printed out. The binary search tree operations are coded as follows:
1. Txx insert key xx as the tree root;
2. Lxx@yy go left at the node with key yy (new key value xx is less than current node key yy);
3. Rxx&yy go right at the node with key yy (new key value xx is more than current node key xx);
4. Ixx@yy insert key xx as the child of the node with key yy.
Your results.txt file should have the coded operations in sequence, e.g. if the first 3 values to be inserted are
15012340, 250, 306 the results.txt file would start:
15012345
Binary Search Tree Insertion 1) K=10
T15012340 L250@15012340 I250@15012340 L306@15012340 R306@250 I306@250 ...
Number of steps required S=45
Average number of steps per key: 45/10=4.5