- consider the page caching strategy based on the least frequently used (lfurulewhere the page in the cache that has been accessed the least often is the one that is evicted when new page is requested if there are tieslfu evicts the least frequently used page that has been in the cache the longest show that there is sequence of requests that causes lfu to miss (ntimes for cache of pageswhereas the optimal algorithm will miss only (mtimes - suppose that instead of having the node-search function ( in an order- -tree we have (dlog what does the asymptotic running time of performing search in now becomeprojects - write python class that simulates the best-fitworst-fitfirst-fitand nextfit algorithms for memory management determine experimentally which method is the best under various sequences of memory requests - write python class that implements all the methods of the ordered map adt by means of an (abtreewhere and are integer constants passed as parameters to constructor - implement the -tree data structureassuming block size of and integer keys test the number of "disk transfersneeded to process sequence of map operations notes the reader interested in the study of the architecture of hierarchical memory systems is referred to the book by burger et al [ or the book by hennessy and patterson [ the mark-sweep garbage collection method we describe is one of many different algorithms for performing garbage collection we encourage the reader interested in further study of garbage collection to examine the book by jones and lins [ knuth [ has very nice discussions about external-memory sorting and searchingand ullman [ discusses external memory structures for database systems the handbook by gonnet and baeza-yates [ compares the performance of number of different sorting algorithmsmany of which are external-memory algorithms -trees were invented by bayer and mccreight [ and comer [ provides very nice overview of this data structure the books by mehlhorn [ and samet [ also have nice discussions about -trees and their variants aggarwal and vitter [ study the / complexity of sorting and related problemsestablishing upper and lower bounds goodrich et al [ study the / complexity of several computational geometry problems the reader interested in further study of /oefficient algorithms is encouraged to examine the survey paper of vitter [