1. See the steps of inserting 50, 87, 50, 26, 52, 55, 13, 16, 28, 11, 20, 30 into a red-black tree. Draw the trees after you inserting each value, use the color change or rotations to fix the error if there is any. (for each new inserted value, draw the corresponding tree, you can use the applet to take the screenshots, however, the applet may not be correct even it shows Red-Black correct).

2. Given input {3823, 8806, 8783, 2850, 3593, 8479, 1941, 4290, 88 18, 7413, 1729} and a hash function h(x) = x %10 (table size is 10), showing the resulting.

Rehashing is NOT considered here

a. Separate chaining hash table

b. Open addressing hash table using linear probing.

c. Open addressing hash table using quadratic probing.

d. Open addressing hash table with second hash function h2(x) = 7-(x %7)

3. Using the diagrams (like in handouts 50-54) to trace the action of heapsort on the list of 6, 10, 1, 4, 7, 9, 3, 2, 8, 11, give every state of your tree such as finishing a

heapify or removing the root.