This is in Java The intended usage of a data structure is crucial to choose the

Question

This is in Java

The intended usage of a data structure is crucial to choose the most ecient one. Common operations include insertions/deletions, queries1, and range queries2. Suppose that the application requirements are such that the crucial operations are insertions and queries. We know that hash tables have O(1) query time, provided that the hash function distributes the entries uniformly. But also a good choice of the initial table size is crucial to avoid costly re-hashings when new entries are added. AVL trees are Binary Search Trees that balance themselves through rotations. Because they are balanced, the query time is O(logn). But the order in which the entries are added is also important to avoid the worst-case O(logn) rotations per insertion. The purpose of this homework is to test experimentally the insertion and query performance of a separate-chaining hash table and an AVL tree, drawing conclusions from the results observed. Assuming that each entry is a pair <key,value>, where the key is used to index the entries, do the following.

1. (20 points) Make a conjecture for the asymptotic running time of (a) adding n entries with consecutive keys in a separate-chaining hash table and (b) searching for a key that is not in the table. Justify your conjecture using the running times detailed above and any other assumptions you make.

2. (20 points) Make a conjecture for the asymptotic running time of (a) adding n entries with consecutive keys in an AVL tree and (b) searching for a key that is not in the tree. Justify your conjecture using the running times detailed above and any other assumptions you make.

3. (40 points) Write a program that does the following. • Create an instance of the Hashtable class from the Java API. Make the initial table size of the hash table 1000 and the load factor3 0.75 (which has been shown experimentally to be optimal).

Create an instance of the AVLtree class attached with this homework.

• Measure the running time of adding various numbers of entries (as required by the table below) to the hash table and the AVL tree.

• For each of those cases, measure the running time of searching for a key that is not in the hash table, and do the same for the AVL tree.

Fill in the following charts adjusting the values of n as needed according to your platform. construction time n = 102 n = 103 n = 104 n = 105 n = 106 Hash table Tree search time n = 102 n = 103 n = 104 n = 105 n = 106 Hash table Tree

4. (20 points) How does these results compare with your conjecture in parts 1 and 2? If the results dier from your conjecture, investigate the reason by looking carefully at the code of Hashtable (grepcode.com) and AVLtree classes and explain what might have happened.

Explanation / Answer

advertisements

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.