Write clearly and give full explanations to solutions for all the problems. Show all steps of your work.
Reading assignment.
Hash Tables Chap. 9
Heap and Priority Queue, Chap. 8 Graphs, Chap. 13
Problems.
1. (10 points) R-9.7 p. 417
Draw the 11-entry hash table that results from using the has function, h(k) = (3k + 5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by chaining.
2. (10 points) R-9.8 p. 417
What is the result of the previous exercise, assuming collisions are handled by linear probing?
3. (10 points) R-9.10 p. 417
What is the result of Exercise R-9.7, when collisions are handled by double hashing using the secondary hash function hs(k) = 7 (k mod 7)?
2
4. (10 points) R-8.7 p. 361
An airport is developing a computer simulation of air-traffic control that handles events such as landings and takeoffs. Each event has a time-stamp that denotes the time when the event occurs. The simulation program needs to efficiently perform the following two fundamental operations:
Insert an event with a given time-stamp (that is, add a future event)
Extract the event with smallest time-stamp (that is, determine the next event to process)
Which data structure should be used for the above operations? Why? Provide big-oh asymptotic notation for each operation.
5. (10 points) R-13.5, p. 654
6. (10 points) R-13.7, p. 655
3
7. (10 points) R-13.16, p. 656
8. (10 points) R-13.31, p. 657
9. (10 points) C-13.10, p. 658
10. (10 points) C-13.15, p. 659
4
