6.15. Discussion QuestionsΒΆ
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.
Modify the hash function for strings to use positional weightings.
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?
Research perfect hash functions. Using a list of names (classmates, family members, etc.), generate the hash values using the perfect hash algorithm.
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)
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)
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)
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)
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?