Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
Before you keep reading...
Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.
5.16. Programming Exercises¶
Set up a random experiment to test the difference between a sequential search and a binary search on a list of integers.
Use the binary search functions given in the text (recursive and iterative). Generate a random, ordered list of integers and do a benchmark analysis for each one. What are your results? Can you explain them?
Implement the binary search using recursion without the slice operator. Recall that you will need to pass the list along with the starting and ending index values for the sublist. Generate a random, ordered list of integers and do a benchmark analysis.
__len__) for the hash table Map ADT implementation.
__contains__) for the hash table Map ADT implementation.
How can you delete items from a hash table that uses chaining for collision resolution? How about if open addressing is used? What are the special circumstances that must be handled? Implement the
delmethod for the
In the hash table map implementation, the hash table size was chosen to be 101. If the table gets full, this needs to be increased. Re-implement the
putmethod so that the table will automatically resize itself when the loading factor reaches a predetermined value (you can decide the value based on your assessment of load versus performance).
Implement quadratic probing as a rehash technique.
Using a random number generator, create a list of 500 integers. Perform a benchmark analysis using some of the sorting algorithms from this chapter. What is the difference in execution speed?
A bubble sort can be modified to “bubble” in both directions. The first pass moves “up” the list, and the second pass moves “down.” This alternating pattern continues until no more passes are necessary. Implement this variation and describe under what circumstances it might be appropriate.
Perform a benchmark analysis for a shell sort, using different increment sets on the same list.
merge_sortfunction without using the slice operator.
One way to improve the quick sort is to use an insertion sort on lists that have a short length (call it the “partition limit”). Why does this make sense? Reimplement the quick sort and use it to sort a random list of integers. Perform an analysis using different list sizes for the partition limit.
Implement the median-of-three method for selecting a pivot value as a modification to
quick_sort. Run an experiment to compare the two techniques.