# 6.15. 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?