#
#
# Alexey Bochkarev, 2022, a [at] bochkarev (dot) io
# **Content of the first topic (today):**
# - What is an algorithm (vs. a computer program).
# - Key properties: correctness, time, and space requirements (without details)
# - Several examples of sorting algorithms
# - Correctness and testing
# - A word on algorithmic *frameworks* / "types" of algorithms: greedy, D&C, randomized, brute-force, DP, ...
# ## What is an algorithm?
# Well, a recipe. Not good as a strict definition, but as put by [The Economist](https://www.economist.com/the-economist-explains/2017/08/29/what-are-algorithms),
#
# *An algorithm is, essentially, a brainless way of doing clever things.*
#
# A clear, step-by-step instructions manual, how to acheive something specific. Like,
# - get to the bus stop from some specific point,
# - sort an array of $N$ numbers, or
# - assemble the original genome sequence from a smaller, potentially overlapping pieces.
# - ...and so on.
#
# (Without too vague instructions.)
#
# Not a big deal, so far...
# **Note:** algorithm $\neq$ computer program. The former are abstract solution procedures, recipes, while the latter are their implementations in some specific programming language.
#
# We will talk about **algorithms** today -- but we'll consider some specific examples of **programs** too. I suppose, it will be a little easier this way.
# In order to discuss and illustrate some of these, let us pick a specific problem as an example.
# ### A specific example: sorting