Data Structures and Algorithms
The idea is to further teach fundamental concepts in algorithm design by exploring classic models of parallel computation, including the PRAM, generic PRAM simulation, HC/CCC/Butterfly, the mesh, and parallel hardware area-time tradeoffs (with many examples).
Abstract
Describe Larsen's method of dynamic hashing that enables a record to be located on a disk given its key using just one disk transfer and only a modest amount of information held in main memory. [10 marks] In Larsen's method each key has associated pseudo-random sequences of probe and signature values. Discuss what properties these sequences should have. Outline an algorithm that could be used to compute the n th probe–signature pair for a given key. You may assume that the key is a character string. [6 marks] Briefly discuss why Larsen's method is not used in most current filing systems. [4 marks]