CSE 373 -- Data Structures and Algorithms

Winter 2002

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 5

Version 1.1.

The Dictionary ADT with Hashing and TreesS

Due date and time: Monday, Mar 4, 2002, in class). The optional applet should be turned in by class time on Wednesday, Mar 6, as a printout of the web page, with the URL of the applet clearly marked on the page.

Turn in the assignment as hardcopy.

Title: The Dictionary ADT with Hashing and Trees. .

Purposes: Gain familiarity with hashing and approximately balanced binary search trees and their roles in implementing dictionary abstract data types. .

Part A:

Hashing: Let h be a hash function defined by
h(s) = xor (i=0 to k-1) ascii(s_i) MOD n
This means that to compute the hash value for a string s, loop through all of the characters of s, and, starting with the value 0, keep performing a bitwise exclusive-or operation between the ith character (as an ascii integer) and the result so far. Finally, take that result modulo n. (Consult the ASCII code table linked here.) Hash functions that use the bitwise XOR operation on ASCII values are often used for strings, because the resulting value generally depends on every character in the string.
Let n = 7 be the size of the hash table. Insert the following associations into the hash table:

   ("Jo", 173.2)
   ("Sue", 133.5)
   ("Mike", 190.8)
   ("Mary-Lou", 115.1)
   ("Bo", 157.6)

Resolve any collisions using linear probing, going to the next position each time.

Expression Trees: Draw an expression tree for "x^3 + 2x^2 + 3x - 7" Assume that "+" is a binary operator. Assume that ^ is a binary operator. Parenthesize as needed and show multiplication explicitly.
Is your tree a complete binary tree? Why or why not?

Binary Search Trees: Show the results of listing the nodes of the following tree (for which A is thre root) in each of the orders: preorder, inorder, postorder, level order.

                   A
        B                     C
    D       E            F        G
   H I     J K          L M      N O

AVL Trees: Draw an AVL tree whose root has height 5 and which has as few nodes as possible, making each node either balanced or right-heavy.

AVL Search Trees: Starting with an empty AVL search tree, keep inserting the following elements into the tree, and show the (possibly "rebalanced") tree after each insertion.
I THINK THAT I2 SHALL NEVER SEE
A POEM AS LOVELY AS2 A2 TREE
Next, delete the element "I2" from the tree, and perform the rebalancing according to the AVL deletion method.

Part B: (OPTIONAL) Applet.
Implement an applet for your choice of the following. The applet must have a text area for entering commands and it should handle any number of commands in the text area at one time, one command per line.
(i). Hash table creation, insertion (i.e., PUT), and retrieval (i.e., GET), using the same method as in Part A, exercise 1. The CREATE command should take an integer argument that specifies the number of positions in the table. Example command sequence:

  CREATE 7
  INSERT Jo, 173.2
  INSERT Sue, 133.5
  INSERT Mike, 190.8
  INSERT Mary-Lou 115.1
  INSERT Bo, 157.6
  GET Sue

For each INSERT and GET operation, print the following in the Java Console using System.out.println: The operation being performed, hash value, number of collisions, final location in hash table, and current load factor.
(ii). AVL Tree with insertion method.

  CLEAR -- sets the current AVL tree to be empty.
  INSERT Bo, 157.6  -- inserts the given association.
  For each INSERT operation, print out in the Java Console the following
   information for each rotation operation:
     -- which node will be the root of the rotation
     -- whether it is an LL, LR, RL, or RR rotation.

You can display the tree using the following style:

    Bo, 157.6
 Jo, 173.2
       Mary-Lou 115.1
    Mike, 190.8
       Sue, 133.5

Individual Work: This assignment requires individual work.