HOMEWORK 8 - Jacobs University

H OMEWORK 8
320201: F UNDAMENTAL C OMPUTER S CIENCE I (A LGORITHMS & DATA S TRUCTURES )
080211 A LGORITHMS & DATA S TRUCTURES FOR I NFORMATION M ANAGEMENT
Fall 2014
Prof. Dr. Lars Linsen
Jacobs University
Due: Friday, November 21, 2014.
Problem 18: Red-black Trees.
(3+3=6 points)
(a) Suppose a node is inserted into a red-black tree and, then, immediately deleted again. Is the
resulting red-black tree the same as the initial one? Justify your answer.
(b) In Problem 17(b), you successively inserted the keys 41, 38, 31, 12, 19, and 8 into an empty
red-black tree. Now, successively delete the keys 8, 12, 19, 31, 38, and 41.
Problem 19: AVL Trees.
(6+5+3=14 points)
An AVL tree is a height-balanced binary tree, i.e., for each node x the heights of the left and right
subtrees of x differ by, at most, 1. Its implementation uses an additional attribute for the height x.h of
each node x.
(a) If we apply the BST operation of an I NSERT, the tree may not be balanced anymore. Describe an
efficient procedure B ALANCE to restore the AVL tree after insertion.
(b) Using Part (a), describe a procedure AVL-I NSERT that inserts a node into an AVL tree (maintaining the AVL property).
(c) Show that AVL-I NSERT in Part (b) runs in O(lg n) for an AVL tree with n nodes.
Problem 20: Hash Tables.
(3+7+5∗ +5+ =10+5∗ +5+ points)
(a) Demonstrate what happens if we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, and 10 into a hash
table of size m = 9 with hash function h(k) = k mod 9 and collisions resolved by chaining.
(b) Implement insertion into a hash table of size m = 11 using linear probing and double hashing
with the hash functions presented in class. Insert the keys 10, 22, 31, 4, 15, 28, 17, 88, and 59 and
output the hash tables after each step.
∗
(c)
Generalize the implementation in Part (a) to any size m and enrich it with a search function.
For a sufficiently large m, fill the hash table with n randomly generated numbers. Plot how the
running times for insertion change when the load factor increases. Output the hash tables to
observe the effect of primary clustering. For an appropriate load factor, perform searches with
randomly generated numbers to see how the primary clustering affects the average search time.
(d)
+
Suppose we use double hashing to resolve collisions in an open addressing implementation of
a hash table. Let d be the greatest common divisor of m and h2 (k) for some key k. Show that an
unsuccessful search examines ( d1 )th of the hash table before returning to slot h1 (k). Thus, when
m and h2 (k) are relatively prime, the search may examine the entire hash table.
Remarks:
• Solutions have to be handed in via jGrader (https://cantaloupe.eecs.jacobs-university.de/login.php)
by the due date. For late submissions you need to get in contact with the TAs directly. You need to
upload one zip-file that contains a PDF-file for the theoretical parts and source files (no executables or object files) for the programming assignments. The source files need to include a makefile.
Programming assignments need to be handed in as C code, C++ code, or Python code.
• Problems marked with a ∗ are bonus problems for students enrolled in the 080211 course.
• Problems marked with a + are bonus problems for all students.

Download Report