$30
CSCE 221
Homework Assignment #3
First Name Last Name UIN
User Name E-mail address
Please list all sources in the table below including web pages which you used to solve or implement the
current homework. If you fail to cite sources you can get a lower number of points or even zero, read more
on Aggie Honor System Office website: http://aggiehonor.tamu.edu/
Type of sources
People
Web pages (provide URL)
Printed material
Other Sources
I certify that I have listed all the sources that I used to develop the solutions/codes to the submitted work.
On my honor as an Aggie, I have neither given nor received any unauthorized help on this academic work.
Your Name Date
1
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