Homework 4: B Trees and Hash Tables
 Due before class on Monday, October 24
Remember to turn in a neat final draft of this homework on a separate sheet of paper.
1 B Tree Insertions
For each of the following, insert the given keys in order into a Btree of the given degree. Remember that a degree\(d\) Btree means that each node has at most \(d\) children, and therefore each node has at most \(d1\) keys in it.
I need to be able to clearly and easily follow your work. You do not need to redraw the tree on every insertion, but you should redraw it after every split and promotion that occurs so I can see your work.
 Insert the following into a Btree of max degree 3:
1, 69, 59, 91, 6, 28, 10, 50, 55, 22, 74

Insert the following into a Btree of max degree 5:
65, 73, 82, 2, 87, 7, 13, 49, 24, 81, 45, 8, 55, 14, 99, 22, 27, 85, 40
2 Hash tables
Use the following hash function for these problems:
\(h(x) = (11x) \bmod 13\)
So for example \(h(2018) = 7\).

Write down the hash values of the following numbers:
20, 30, 31, 42, 46, 56, 62, 85

Insert the following into a size13 hash table using separate chaining. Perform the insertions in the given order, one at a time. You just need to draw the final state of the hashtable after all insertions.
20, 56, 62, 31, 46, 30, 85, 42
Insert the following into a size13 hash table using open addressing and linear probing. Perform the insertions in the given order, one at a time. You just need to draw the final state of the hashtable after all insertions.
20, 56, 62, 31, 46, 30, 85, 42