Discussion Questions

  1. Using the hash table performance formulas given in the chapter, compute the average number of comparisons necessary when the table is

    • 10% full
    • 25% full
    • 50% full
    • 75% full
    • 90% full
    • 99% full

    At what point do you think the hash table is too small? Explain.

  2. Modify the hash function for strings to use positional weightings.

  3. We used a hash function for strings that weighted the characters by position. Devise an alternative weighting scheme. What are the biases that exist with these functions?

  4. Research perfect hash functions. Using a list of names (classmates, family members, etc.), generate the hash values using the perfect hash algorithm.

  5. Generate a random list of integers. Show how this list is sorted by the following algorithms:

    • bubble sort
    • selection sort
    • insertion sort
    • shell sort (you decide on the increments)
    • merge sort
    • quick sort (you decide on the pivot value)
  6. Consider the following list of integers: [1,2,3,4,5,6,7,8,9,10]. Show how this list is sorted by the following algorithms:

    • bubble sort
    • selection sort
    • insertion sort
    • shell sort (you decide on the increments)
    • merge sort
    • quick sort (you decide on the pivot value)
  7. Consider the following list of integers: [10,9,8,7,6,5,4,3,2,1]. Show how this list is sorted by the following algorithms:

    • bubble sort
    • selection sort
    • insertion sort
    • shell sort (you decide on the increments)
    • merge sort
    • quick sort (you decide on the pivot value)
  8. Consider the list of characters: ['P','Y','T','H','O','N']. Show how this list is sorted using the following algorithms:

    • bubble sort
    • selection sort
    • insertion sort
    • shell sort (you decide on the increments)
    • merge sort
    • quick sort (you decide on the pivot value)
  9. Devise alternative strategies for choosing the pivot value in quick sort. For example, pick the middle item. Re-implement the algorithm and then execute it on random data sets. Under what criteria does your new strategy perform better or worse than the strategy from this chapter?

Następna część - Programming Exercises