Data Structures and Algorithms Help

Collaboration policy: The goal of homework is to give you practice in mastering the course material. Consequently, you are encouraged to collab- orate with others (groups of at most three). In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study group meeting. Specifically, you should spend at least 30–45 minutes trying to solve each problem beforehand. If your group is unable to solve a problem, it is your responsibility to get help from the instructor before the assignment is due. You must write up each problem solution and/or code any programming assignment by yourself without assistance, even if you collaborate with others to solve the problem. You are asked to identify your collaborators. If you did not work with anyone, you must write “Collaborators: none.” If you obtain a solution through research (e.g., on the web), acknowledge your source, but write up the solution in your own words. It is a violation of this pol- icy to submit a problem solution that you cannot orally explain to the instructor. No other student may use your solutions; this includes your writing, code, tests, documentation, etc. It is a violation of this policy to permit anyone other than the instructor and yourself read-access to the location where you keep your solutions.

1

Submission Guidelines: Your group has to submit your work on Black- board by the due date. Only one submission per group is necessary. Just make sure that you identify your group in the header by putting all names in the “author” field. For each of the program- ming assignments you must use the header template provided in Blackboard. The header must contain, your name, course number, semester, homework number, problem number, and list of collaborators (if any, otherwise put “none”). Your answers to questions that do not require coding must be in- cluded in this header as well. Your code must follow the Java formatting standards posted in Blackboard. Format will also be part of your grade. To complete your submission, you have to upload two files to Blackboard: your source file and your class file. The submission will be returned without grading if any of these guidelines is not followed.

Style and Correctness: Keep in mind that your goal is to communi- cate. Full credit will be given only to the correct solution which is described clearly. Convoluted and obtuse descriptions might receive low marks, even when they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups, and also help you conceptualize the key idea of the problem.

2

Assignment 6

Programming Assignment Grading Rubric: The following rubric applies only to the programming assignment.

Program characteristic

Program feature Credit possible

Part 3

Design 30%

Algorithm 30%

Functionality 30%

Program runs without errors

20%

Correct result given 10%

Input 15%

User friendly, typos, spacing

10%

Values read in correctly

5%

Output 15%

Output provided 10%

Proper spelling, spacing, user friendly

5%

Format 10%

Documentation: name, collaborators, header, etc.

5%

Clarity: comments, indentation, etc.

5%

TOTAL 100%

1(20) 2(20) 3(40) 4(20) TOTAL(100)

3

Assignment: The intended usage of a data structure is crucial to choose the most

efficient 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(log n). But the order in which the entries are added is also important to avoid the worst-case O(log n) 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).

1Access operations, such as read or contains. 2Returning multiple items. 3The load factor is the occupancy threshold for rehashing. That is, if the number of

items in the table is more than the table size times the load factor, the object rehashes the table increasing the capacity.

4

• Create an instance of the AVLtree class attached with this home- work.

• 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 accord- ing to your platform to obtain at least 4 measurements.

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 measurements compare with your con- jecture in parts 1 and 2? If the results differ from your conjecture, investigate the reason by looking carefully at the code of Hashtable (grepcode.com) and AVLtree provided and explain what might have happened.