Description

Consider a computer with a memory hierarchy as shown below (next page). The primary memory has 2t*2 memory cells–they can carry at most 4t keys. Additional space for storing addresses is allowed. For example, the following will be counted as one memory cell.

It is random access and implemented as an array–any element can be accessed directly. All computational operations can be performed only on keys that are there in the primary memory. Also, the time taken to access an element in this memory is fast–1 time unit.
The secondary memory is implemented as a two dimensional array of NX2t dimensions. Intuitively, each row stands for a block on the secondary memory. As such, the secondary memory can only be accessed at the granularity of a row. For example, the entire B1 can be loaded into the primary memory, but not individual elements B[1][j]. Therefore, you can readDisk(B[i]) and writeDisk(B([j]) commands only that can touch the secondary memory. Time taken for each of these operations is 10 units.
Let t be 10. N can be as much as you want (as big a secondary memory as you want).
Write programs to store data in your computer as:
● B-Tree: insert/search and delete operations (20 marks)
● Binary Search Tree: insert/search and delete operations. (20 marks)
You can assume there are 60 keys and order of the keys is as follows: 17 13 2 27 48 54 39 57
60 3 23 46 16 18 49 45 33 36 55 19 47 35 7 22 4 50 9 56 37 12 11 21 31 38 29 44 8 26 25 40 6
58 51 1 15 30 52 10 28 59 53 34 43 42 24 14 32 41 5 20
Search for: 49, 27, 22, 38, 11, 55, 7, 35 and 59 Delete: 13, 19, 24, 37, 43, 53, 18, 38 and 58.
Report the time taken for creation of the data structures, search time and delete time. The time taken has to be calculated as per the cost mentioned above. (5 + 5 marks)
(10 marks for good code design, commenting and readability)