|Data Structures and Algorithms|
|Tutorial Problems: Part 3|
The records for this database will be stored on discs which have an average access time of 2.5ms to read a block of 4Kbytes. Each disc uses a 32-bit integer to address blocks within the disc. The database spreads over multiple discs, so a 16-bit disc identifier has to be added to each block address. It takes 150ns to read a word from the computer's main memory.
The population is 17x106 taxpayers and 0.78 x 103 politicians (1.8x103 millionaires have never needed to submit a tax return.). There are also records for 1.2 x 106 foreign residents who pay some tax and 2.8x106 companies, trusts and other tax avoidance structures.
free places freed blocks into free lists. In order to re-use memory as much as possible, malloc will generally search the free lists for a block before requesting another one from the operating system (a very expensive exercise!). A best-fit algorithm searches for the smallest free block into which the requested block will fit.
Suggest a number of ways in which free could organise the free lists and give the time complexities for
|Continue on to Tutorials: Part 4||Back to the Table of Contents|