Self-Organizing Files (UMAP)

Author: Kin Lam, Ming-Ying Leung, and Man-Keung Siu

This module applies linear algebra to computer science. Students will become familiar with probabilistic modelling of an actual problem encountered in a field of application, become acquainted with an important problem in file organization, and reinforce their learning of the topic of Markov chains.

Table of Contents:

1. SELF-ORGANIZING FILES
1.1 The Problem
1.2 The Move-to-Front Scheme
1.3 The Transposition Scheme

2. APPLICATION OF MARKOV CHAINS TO SELF-ORGANIZING FILES
2.1 Stationary Distribution for a Scheme
2.2 Transposition is Better Than Move-to-Front
2.3 Historical Notes

3. REFERENCES

4. ANSWERS TO EXERCISES

5. SKETCH OF SOLUTIONS TO EXERCISES