CSC3171 Quiz 8

Fall 2011
Herbert J. Bernstein ( )

CSC3171 Quiz 8
Fall 2011


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

This is the eighth weekly quiz to be taken on or before Thursday, 27 October 2011. You should do it after you read the Knuth's Sorting and Searching through section 6.3 (Digital Searching) 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 use of the balanced two-way merge in an expernal sort using magnetic tape and give an example.

  2. Explain 4-way replacment selection and give an example.

  3. Explain polyphase merge soting with horizontal distribution.

  4. Summarize the impact of the ability to read tape backwards on polyphase sorting.

  5. Explain Sheldon Sobel's oscillating sort.

  6. Explain external radix sorting.

  7. Explain the difference in timing considerations between disk based sorting and tape-based sorting.

  8. Explain the timing of sequential searching, timing of a uniform binary search and the timing of a Fibonaccian search.

  9. Explain how to use a balanced tree to represent a linear list in such a way that we can insert items rapidly, yet can also perform random accesses to list items.

  10. Explain how to convert between a binary tree and an octonary tree and vice versa.

  11. Define a trie search and give an example.

  12. Define a digital tree search and give an example.

  13. Define a Patricia tree search and give an example.

  14. Summarize the comparative performance of the trie search the digital tree search, and the Patricia tree search.

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

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

Revised 19 September 2011