Computer Science Help required
Vishal Vij* 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.
11 years ago
20
- Business Law
- problem set 4
- A spinner with three equal spaces of red, blue, and green is spun one time. A single six-sided die is rolled...
- Essay and Focus Questions Partisan Politics
- What does "fixed composition" mean?
- Financial Assignment
- True or false A general decline in prices also decreases the value of money.
- Does determining the mass and size of atoms require direct measure?
- outline format This a resend with document in pdf
- "A Good Man is Hard to Find " and "Bartlleby the Scrivener"
