Data structures and algorithms for hierarchical memory machines

Candidate: Mirza,Mirza G. R.


This thesis analyzes the influence of hierarchical memory in models of practical computation. While hierarchical memory is the standard in real computing systems, the most common models of computation, Random Access Memory Machines and Turing Machines, do not reflect this form of memory. Our main contributions are: (1) Models of computation that have memory hierarchy, and which provide a rich structure for the complexity analysis of real computational problems. (2) Optimal bounds for problems such as sorting, with respect to both space and time, for a variety of memory access costs. (3) Related bounds for other problems, including constrained multitape merging and the implementation of Priority Queues and B-Trees. (4) The introduction of multiprogramming and multiprocessing concepts for these models, and an analysis of their relative computational power.