Week 13. Memory

Reading 13 Goodrich & Tamassia: Chapter 14

Problem 14.1 Describe an external-memory data structure to implement the double-ended queue ADT so that the total number of disk transfers needed to process a sequence of $k$ push and pop operations is $O(k∕B)$, where $B$ is the block size, i.e. number of elements fitting in a block.

Problem 14.2 The B-tree as described in the textbook uses the map ADT to hold the contents of each node. The time to retrieve an element from this data structure is described as $f\left(d\right)$, where $d$ is the maximum number of elements in the map. For a map, $f\left(d\right)=O\left(1\right)$.

Suppose we change this constituent data type to a sorted tree. What would be the resulting value of $f\left(d\right)$? And how does it affect the total run time of get() in the B-tree.

Problem 14.3 Describe an external-memory data structure to implement the stack ADT so that the total number of disk transfers needed to process a sequence of $k$ push and pop operations is $O(k∕B)$, where $B$ is the block size, i.e. number of elements fitting in a block.