CSC3171 Quiz 9

Fall 2011
Herbert J. Bernstein ( )

CSC3171 Quiz 9
Fall 2011


This web page is
Copyright © 2007, 2011 Herbert J. Bernstein and other parties. All rights reserved.

This is the nineth weekly quiz to be taken on or before the start of class Thursday, 3 November 2011. You should do it after you read the Knuth's Sorting and Searching through the end. You should expect to spend 30 minutes to 2 hours on this quiz. You may use your text and any other resources to do this quiz, but if you do not know the answers well or are unable to discuss them in class, you will lose credit for the quiz.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Please fill in the following information:



Please answer the following questions on this form (or on a paper copy of this form).

  1. Explain the birthday paradox and discuss how it is related to hash functions.

  2. Explain the middle square method of hashing.

  3. Explain hashing by division and a good choice of divisor.

  4. Explain hashing by division and give a simple example suitable for use on a binary computer.

  5. Explain how to avoid having the hash of (X,Y) and of (Y,X) come out the same.

  6. Explain collision resolution by chaining.

  7. Explain collision resolution by open addressing. Be sure to explain how you would do a deletion.

  8. What is an inverted file?

  9. What is the post office tree?

  10. What is a quadtree? What is an octree?

  11. Give the Google sites URLs of your first and second presentations.

  12. Give your structural homology URL.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Revised 6 October 2011