Computer Science

* M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, Cache-Oblivious Algorithms, IEEE Symposium on Foundations of Computer Science, 1999.
* Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-Colton, J. Ian Munro, Theis Rauhe, Mikkel Thorup, Efficient Tree Layout in a Multilevel Memory Hierarchy, Extended version of ESA 2002 paper, November 2002.
* Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro, Cache-Oblivious Priority Queue and Graph Algorithm Applications, 34th ACM Symposium on Theory of Computing (STOC), 2002.

In the third paper, section 3.1 discusses a cache-oblivious list ranking algorithm based on list contraction, scanning, sorting, and 3-coloring to identify an independent set.

Your homework exercise is to take the high-level descriptions of cache-oblivious list ranking, and write detailed pseudocode that represents this algorithm.

State the asymptotic complexity in the RAM model for your pseudocode. 
What is the complexity in the I/O model?

BONUS: For extra credit, as a challenge, implement the cache-oblivious list ranking algorithm and compare its running time experimentally with a straightforward pointer-chasing approach.