CSC3171 Quiz 7

Fall 2011
Herbert J. Bernstein ( )

CSC3171 Quiz 7
Fall 2011


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

This is the seventh weekly quiz to be taken on or before Thursday, 20 October 2011. You should do it after you read the Knuth's Sorting and Searching through section 5.3.4 (Networks for Sorting) 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. State the law of trichotomy and the law of transitivity.

  2. Explain the meaning of stable sorting and illustrate with an example.

  3. Give a good estimate of the time required to sort N records if the records are in random order and sorting is done by pairwise comparisons.

  4. What is a Young tableau of shape (n1, n2, ..., nm)?

  5. Explain sorting by comparison counting.

  6. Explain Shell sort.

  7. Explain quicksort.

  8. Explain the heapsort.

  9. Explain the straight 2-way merge sort.

  10. Explain the radix list sort.

  11. State the information theoretical lower bound for the minimum number of comparisons that will suffice to sort n elements.

  12. How many comparison are required to merge an ordered set of m elements with an ordered set of n elements.

  13. Explain Lewis Carroll's design for a lawn tennis tournament and explain why it is better than a typical knockout tournament.

  14. State the zero-one principle.

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

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

Revised 19 September 2011