COSC 3333 1 HW2

COSC 3333 1      HW2

Part I: written exercises.

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, 8818, 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.

Part II: programming exercise

Text programming project 11.2 on page 577 (You can modify Listing 11.1 using

hashFunc3 on slide 81).