## Exercises 8. 4. 2021: Caches, caches everywhere!

### Ex. 1: Transposition

In the lecture we saw cache-aware matrix transposition using tiles and cache-oblivious
transposition using recursive divide-and-conquer.
- Recall the cache-aware algorithm and its analysis. Do you understand how it works
and
* why we do it this way *? Simulate the algorithm on a 8x8 matrix with \(B
= 3\).
- The cache-aware algorithm required
* tall-cache assumption *, more
precisely, \(M \ge 2B^2\). What if can guarantee only \( M \ge B^2 \)? Can we modify
the algorithm to keep \( \mathcal{O}(N^2/B) \) complexity?
- Recall the cache-oblivious algorithm and its analysis. Do you understand how it works
and
* why we do it this way *? Simulate the algorithm on a 8x8 matrix with \( B
= 3 \).
- In the cache-oblivious algorithm, we assumed that \(N\) is a power of two. What
happens if it is not? Show that in such case, all submatrices throughout the algorithm
are
* almost square *, i.e. number of rows and columns differ by at most one.
Then observe that this does not break the algorithm in any way.

### Ex. 2: Searches and trees

(You didn't think you can escape trees, did you? :-))

- Analyze cache-complexity of binary search in a sorted array. Do you think the
complexity is optimal (i.e. can there be algorithm that can do better)? [The last part
is really a question about what you think, I do not expect any proof or something :-)]
- Analyze cache performance of static balanced binary search tree.
- (spoiler!) Why did the binary trees failed? Can we fix the problem in the
cache-aware setting?
- (another spoiler!) Analyze the cache performance of (a,b)-trees. Choose \(a\) and
\(b\) to make the performance the best possible (asymptotically) in the cache-aware
setting.
- Cherry to top the cake: Modify the previous construction to the cache-oblivious
setting. Assume only a static tree. Hint: Basically you need to combine
divide-and-conquer with dynamic choice of \(a, b \). Each level of needs to use a
different size of vertices and verices need to be stored recursively.