\n",
"
\n",
"\n",
" Alexey Bochkarev, 2022, a [at] bochkarev (dot) io
"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"**Content of the first topic (today):**\n",
"- What is an algorithm (vs. a computer program).\n",
"- Key properties: correctness, time, and space requirements (without details)\n",
"- Several examples of sorting algorithms\n",
"- Correctness and testing\n",
"- A word on algorithmic *frameworks* / \"types\" of algorithms: greedy, D&C, randomized, brute-force, DP, ..."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## What is an algorithm?\n",
"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),\n",
"\n",
"*An algorithm is, essentially, a brainless way of doing clever things.*\n",
"\n",
"A clear, step-by-step instructions manual, how to acheive something specific. Like, \n",
"- get to the bus stop from some specific point, \n",
"- sort an array of $N$ numbers, or\n",
"- assemble the original genome sequence from a smaller, potentially overlapping pieces. \n",
"- ...and so on.\n",
"\n",
"(Without too vague instructions.)\n",
"\n",
"Not a big deal, so far..."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Note:** algorithm $\\neq$ computer program. The former are abstract solution procedures, recipes, while the latter are their implementations in some specific programming language.\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"In order to discuss and illustrate some of these, let us pick a specific problem as an example."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### A specific example: sorting