About: A sidequest is an optional, not graded, not evaluated in anyway exploration into a topic. Sometimes it is just cool to know what is out there in the world. Sidequests come with a little descritions, presentations, related resources, and a sample code or exercise you can try. Side quests are likely a good area for further independent studies, research project, thesis, etc.

Performance Analysis Study

Problem Statement

When we learn algorithms, we analyze their tradeoffs in terms of the asymptotic growth of a function. As an example, merge sort (n log n) is much better than selection sort(n^2). But is it always better? (And what about something like Flashsort). Hardware complicates the question of "which algorithm is better" when we introduce different types of memory in our memory hierarchy.

Proposed Exercise

For this exercise, you will implement several popular sorting algorithms, sorting different data types. You will then use tools to measure how long the actual algorithm takes. Additionally, you will use tools to measure cache-hits, page-faults, etc. to really understand when an algorithm may perform best.

Proposed Evaluation

Implement and build a test framework for various benchmarks(e.g. sorting algorithms). Measure various metrics like cache-hits, page-faults, time, and allocations. Be very precise about the resolution of timers you are using, taking care that the cache is, or is not warmed up, etc.

Key Resources

(The first resource you should read)

Additional Resources