tags: algorithms computer-science
Algorithm
An algorithm is a set of elementary instructions.
- algorithms are explicit, precise, unambiguous
- usually, mechanically-executable
- usually intended to accomplish a specific purpose
Algorithms have been with us since the dawn of civilization, but have become a topic of formal academic study only within the past few decades
- descriptions of step-by-step arithmetic as early examples of written human language
Describing Algorithms
A complete description of any algorithm has four components:
- What: a precise specification of the problem that the algorithm solves
- How: a precise description of the algorithm itself
- Why: a proof that the algorithm solves the problem it is supposed to solve
- How fast: an analysis of the [runtime] of the algorithm
It is not necessary to develop these four components in this particular order.
- specifications, descriptions, correctness, and analyses evolve simultaneously or are iterated on separately
- presenting these components separately is usually clearest for the reader
Aim your descriptions at the right audience: ex. a competent but skeptical programmer who is not as clever as you are
- over time, you naturally build up lots of intuition about the problem
- anyone reading the algorithm later, or the derived code, will not share that intuition or experience
TODO: take more notes