Due:
Wednesday, November 14
Readings:
Weiss Chapters 5, 6 (except 6.8)
Problems:
1. (3 points) Weiss 6.8 (all parts). Maximum item in a binary heap.
2. Finding all nodes in a binary heap less than a specified value X.
a. (6 points) Weiss 6.10(a). Also, show that your algorithm is O(K), where K is the number of nodes in your algorithm’s output.
b. (2 points) Weiss 6.10(b).
3. Min-max heap
a. (3 points) Weiss 6.18(a). Also, show why your answers are correct.
b. (5 points) Weiss 6.18(c). Write DeleteMin and DeleteMax for min-max heap.
4. (3 points) Weiss 6.19. Merging a leftist heap.
5. (3 points) Weiss 6.26. Merging a skew heap.
6. (4 points) Weiss 5.1 (all parts). Hashing examples.
7. (6 points) Weiss 5.11 (all parts). Hash table “Boolean spell-checker.” Assume the dictionary contains 30,000 words.
8. String pattern matching via hashing.
a. (3 points) Weiss 5.13(a). Assume your hash function is the one shown in Weiss Figure 5.4.
b. (2 points) Weiss 5.13(b).
9. (Extra Credit - 5 points) Min-max heap revisited.
a. (2 points) Weiss 6.18(b) Write the Insert algorithm for min-max heap.
b. (3 points) Write the string pattern matching algorithm and accompanying hash function for Weiss 5.13.