You are here

Cache-Oblivious Computations: Algorithms and Experimental Evaluation

Author: 
Ramachandran, Vijaya
Issue Date: 
Monday, September 8, 2008
Description: 
Discussion based on techniques and analysis for handling massive data sets. Analysis of algorithms is discussed from the perspective of I/O complexity and the cache-oblivious model. Related topics include the Longest Common Subsequence problem, recursion, bioinformatics, priority queue, heaps and Gaussian Elemination. This is a very mathematical treatment.
Keywords: 
massive data sets, memory hierarchy, analysis of algorithms, I/O complexity, cache-oblivious model, longest common sequence, recursion, bioinformatics, priority queue, heap, Gaussian Elimination
Education Levels: 
Middle School
High School
Intended Audience: 
Educator
Type: 
Instructional Material : Lecture/Presentation
Publisher: 
U Texas-Austin
URL: 
http://www.cs.utexas.edu/~firstbytes/teachers/index.html
CSTA Classification: 

CT.L2-14

Examine connections between elements of mathematics and computer science, including binary numbers, logic, sets and functions.

CPP.L3A-12

Describe how mathematical and statistical functions, sets, and logic are used in computation.

CT.L3B-01

Classify problems as tractable, intractable, or computationally unsolvable.

CT.L3A-03

Explain how sequence, selection, iteration, and recursion are building blocks of algorithms.

CPP.L3B-06

Anticipate future careers and the technologies that will exist.

CT.L3B-03

Critically examine classical algorithms and implement an original algorithm.

CC.L3C-01e

Standard Algorithms (AP Comp Sci A Topic V)

CI.L3B-02

Analyze the beneficial and harmful effects of computing innovations.

Download this resource: