Homework Assignment #3 (120 points) Solution




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.



Webpages(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.

Write clearlyandgivefullexplanationstosolutions foralltheproblems. Showallstepsofyourwork.

Reading assignment.

• Priority Queue and Heap, Chap. 8

• Hash Tables and Maps, Chap. 9

• Graphs, Chap. 13


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.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)?

3. (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.

4. (10 points) R-12.14 p. 588

Draw the frequency array. Use the minimum priority queue based on sorted array to build the Huffman tree for the string below. What is the code for each character and the compression ratio for this algorithm?

dogs do not spot hot pots or cats”.

6. (10 points) R-13.16, p. 656

7. (10 points) R-13.17, 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