Computer Science Help requiredVishal 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.
- 8 years ago
- 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"
- NOT RATEDKindly confirm if you are 100% sureDeadline: 26th Sept, 2 PM ESTRead the following three papers from the class web site:
* M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, …8 years ago