Read the following three papers from the class web site;* 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.
Paper#71969 | Written in 18-Jul-2015Price : $27