Homework Assignment #3

Homework 3 (100 points)

due April 24 at 11:59 pm to eCampus.

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