chap searching bentley et al " locally adaptive data compression scheme[bstw for more on ziv-lempel codingsee data compressionmethods and theory by james storer [sto knuth covers self-organizing lists and zipf distributions in volume of the art of computer programming[knu introduction to modern information retrieval by salton and mcgill [sm is an excellent source for more information about document retrieval techniques see the paper "practical minimal perfect hash functions for large databasesby fox et al [fhcd for an introduction and good algorithm for perfect hashing for further details on the analysis for various collision resolution policiessee knuthvolume [knu and concrete mathematicsa foundation for computer science by grahamknuthand patashnik [gkp the model of hashing presented in this has been of fixed-size hash table problem not addressed is what to do when the hash table gets half full and more records must be inserted this is the domain of dynamic hashing methods good introduction to this topic is "dynamic hashing schemesby enbody and du [ed exercises create graph showing expected cost versus the probability of an unsuccessful search when performing sequential search (see section what can you say qualitatively about the rate of increase in expected cost as the probability of unsuccessful search grows modify the binary search routine of section to implement interpolation search assume that keys are in the range to , and that all key values within the range are equally likely to occur write an algorithm to find the kth smallest value in an unsorted array of numbers ( <nyour algorithm should require th(ntime in the average case hintyour algorithm should look similar to quicksort example discusses distribution where the relative frequencies of the records match the harmonic series that isfor every occurrence of the first recordthe second record will appear half as oftenthe third will appear one third as oftenthe fourth one quarter as oftenand so on the actual probability for the ith record was defined to be /(ihn explain why this is correct graph the equations (nlog and (nnloge which gives the better performancebinary search on sorted listor sequential search on