## 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.
1. 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$$.
2. 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?
3. 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$$.
4. 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? :-))
1. 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 :-)]
2. Analyze cache performance of static balanced binary search tree.
3. (spoiler!) Why did the binary trees failed? Can we fix the problem in the cache-aware setting?
4. (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.
5. 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.