2024-06-21 Friday Meeting Notes

An Algorithmic Sketch: What, Why, How

What:

An algorithmic sketch is an overview or roadmap for an approach to solving a problem which you expect to be primarily resource-bound by your algorithm or data structure choices, for your particular circumstances.

i.e. choosing merge sort vs. quicksort

Both are $$O(n log n)$$ compute time in the average case

What Distinguishes Merge Sort

• Stable sort (doesn't change order of equal items)
• $$O(n log n)$$ in worst case as well
• Can't be done in-place, requires a second array

What Distinguishes Quick Sort

• Unstable sort (equal items may be swapped)
• $$O(n^2)$$ in worst case
• Can be done in-place, no second array needed

Why

In the early stages of a project, or at forks in the road, when you or new members are trying to decide what to work on or how to contribute, having algorithmic sketches can help you decide which approach is more promising and why, backed up by a combination of analysis and intution.

They serve as an artifact later to record the decision and its justifications. ("Why did we go down this road again? If we needed to backtrack, what was the next best alternative?")

How

The first stage of an algorithmic sketch is (in no particular order):

• draw the major components of the system that need to interact
  • can use a diagramming tool like draw.io, LucidCharts, {white,chalk}board, paper and pen
• what are the desired inputs and outputs (can use English or mathematical notation)
• what are the steps to solving the problem, using pseudocode

The second stage is to count the amount of resources, asymptotically at first.

The third stage would be to write some prototypes.