wk3/MY470_wk3_lecture.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### MY470 Computer Programming\n",
    "# Control Flow in Python\n",
    "### Week 3 Lecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overview\n",
    "\n",
    "* What is control flow?\n",
    "  * Conditional statements\n",
    "  * Iteration\n",
    "  * List comprehensions\n",
    "* Examples\n",
    "  * Exhaustive enumeration \n",
    "  * Bisection search\n",
    "  * Newton-Raphson algorithm\n",
    "* Iteration and efficiency\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## From Last Week: Straight-Line Programs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 12 words in the sentence.\n"
     ]
    }
   ],
   "source": [
    "s = 'All animals are equal, but some animals are more equal than others.'\n",
    "s = s.rstrip('.').lower()\n",
    "s_tokens = s.split()\n",
    "print('There are', len(s_tokens), 'words in the sentence.')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Control Flow\n",
    "\n",
    "* Control flow is the order in which statements are executed or evaluated\n",
    "* In Python, there are three main categories of control flow:\n",
    "  * **Branches** (conditional statements) – execute only if some condition is met\n",
    "  * **Loops** (iteration) – execute repeatedly \n",
    "  * Function calls – execute a set of distant statements and return back to the control flow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conditional Statements\n",
    "\n",
    "![Conditional statements](figs/conditional_statements.png \"Conditional statements\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conditional Statements: `if`\n",
    "\n",
    "```\n",
    "if *Boolean expression*:\n",
    "    *block of code*\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How old are you? 26\n",
      "Ah, I see, you are a mature student.\n"
     ]
    }
   ],
   "source": [
    "x = input('How old are you? ')\n",
    "if int(x) >= 25:\n",
    "    print(\"Ah, I see, you are a mature student.\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Indentation in Python Code\n",
    "\n",
    "* Indentation is semantically meaningful in Python\n",
    "* You can use [tabs or spaces](https://www.youtube.com/watch?v=SsoOG6ZeyUI)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![Salary for using tabs vs. spaces](figs/tabs_spaces_salary.png \"Salary for using tabs vs. spaces\")\n",
    "\n",
    "* Obviously(!), tabs are preferable\n",
    "* However, it does not really matter in Jupyter as Jupyter converts tabs to spaces by default"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conditional Statements: `if`–`else`\n",
    "\n",
    "```\n",
    "if *Boolean expression*:\n",
    "    *block of code*\n",
    "else:\n",
    "    *block of code*\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Odd\n",
      "Problem solved!\n"
     ]
    }
   ],
   "source": [
    "x = 5\n",
    "if x % 2 == 0:\n",
    "    print(\"Even\")\n",
    "else:\n",
    "    print(\"Odd\")    \n",
    "print('Problem solved!')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conditional Statements: `if`–`elif`–`else`\n",
    "\n",
    "```\n",
    "if *Boolean expression*:\n",
    "    *block of code*\n",
    "elif *Boolean expression*:\n",
    "    *block of code*\n",
    "else:\n",
    "    *block of code*\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Negative\n"
     ]
    }
   ],
   "source": [
    "x = -2\n",
    "if x > 0:\n",
    "    print('Positive')\n",
    "elif x < 0:\n",
    "    print('Negative')\n",
    "else:\n",
    "    print('Zero')\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conditional Statements Are Evaluated Sequentially\n",
    "\n",
    "⚡️ Hence, it makes sense to start with the most likely one. This could make your code faster! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Guess which number from 1 to 100 I'm thinking of? 30\n",
      "You are very close. Try again.\n"
     ]
    }
   ],
   "source": [
    "correct = 25\n",
    "\n",
    "guess = int(input(\"Guess which number from 1 to 100 I'm thinking of? \"))\n",
    "\n",
    "if guess > correct + 10 or guess < correct - 10:\n",
    "    print(\"You are quite far. Try again.\")\n",
    "elif guess != correct:\n",
    "    print(\"You are very close. Try again.\")\n",
    "else:\n",
    "    print(\"That's right!\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Nested Conditional Statements\n",
    "\n",
    "📖 Nesting conditional statements is often a question of style. As always, clarity and speed should be your major considerations!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is a negative number\n"
     ]
    }
   ],
   "source": [
    "x = -100\n",
    "\n",
    "if type(x) == int or type(x) == float:\n",
    "    if x >= 0:\n",
    "        print('This is a nonnegative number.')\n",
    "    else:\n",
    "        print('This is a negative number.')\n",
    "elif type(x) == str:\n",
    "    print('This is a string.')\n",
    "else:\n",
    "    print(\"I don't know what this is.\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Conditional Statements: Exercise\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# Write a program that takes input X from the user about their \n",
    "# favorite dessert and responds \"I love X too!\", \"Oh no, I can't stand X!\", \n",
    "# or \"Oh really, I've never had X!\" depending on whether \n",
    "# the input is in my_faves and my_hates\n",
    "\n",
    "my_faves = ['ice cream', 'cake']\n",
    "my_hates = ['rice pudding', 'spotted dick', 'mince pie', 'lardy cake', 'syllabub']\n",
    "\n",
    "your_fave = input('What is your favorite dessert? ')\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration\n",
    "\n",
    "![Iteration](figs/iteration.png \"Iteration\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration: `while` vs. `for`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n",
    "while *Boolean expression*:\n",
    "    *block of code*\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n",
    "for *element* in *sequence*:\n",
    "    *block of code*\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration: `while` with decrementing function\n",
    "\n",
    "The decrementing function is a function that maps variables to an integer that is initially non-negative but that decreases with every pass through the loop; the loop ends when the integer is 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "# decrementing function: 5 - x\n",
    "x = 0\n",
    "while x < 5: \n",
    "    x += 1\n",
    "    print(x)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration: `while` with conditional statements\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Guess which number from 1 to 100 I'm thinking of? 70\n",
      "You are quite far. Try again.\n",
      "Guess which number from 1 to 100 I'm thinking of? 24\n",
      "You are very close. Try again.\n",
      "Guess which number from 1 to 100 I'm thinking of? 25\n",
      "That's right!\n"
     ]
    }
   ],
   "source": [
    "correct = 25\n",
    "repeat = True\n",
    "\n",
    "while repeat:\n",
    "    guess = int(input(\"Guess which number from 1 to 100 I'm thinking of? \"))\n",
    "    \n",
    "    if guess > correct + 10 or guess < correct - 10:\n",
    "        print(\"You are quite far. Try again.\")\n",
    "    elif guess != correct:\n",
    "        print(\"You are very close. Try again.\")\n",
    "    else:\n",
    "        print(\"That's right!\")\n",
    "        repeat = False\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration: `for`\n",
    "\n",
    "```\n",
    "for *element* in *sequence*:\n",
    "    *block of code*\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 "
     ]
    }
   ],
   "source": [
    "for i in [1, 2, 3, 4, 5]:\n",
    "    print(i, end=' ') \n",
    "    # Note that the \"end\" parameter replaces the default new line with a space\n",
    "    # This allows us to print on the same line\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## `range()`\n",
    "\n",
    "* In-built function that produces an immutable ordered non-scalar object of type `range`\n",
    "* Initiate as `range([start], stop, [step])`. If ommitted, `start = 0` and `step = 1`. \n",
    "* Function produces progression of integers `[start, start + step, start + 2*step, ..., start + i*step]` \n",
    "  * If step > 0, `start + i*step < stop` \n",
    "  * If step < 0, `start + i*step > stop` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "range(0, 6)\n",
      "[0, 1, 2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "print(range(6))\n",
    "print(list(range(6)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## `range()` is essential for `for`-loops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 \n",
      "1 2 3 4 5 \n",
      "1 3 5 "
     ]
    }
   ],
   "source": [
    "for i in range(6):\n",
    "    print(i, end=' ')\n",
    "print() \n",
    "\n",
    "for i in range(1, 6):\n",
    "    print(i, end=' ')\n",
    "print()\n",
    "    \n",
    "for i in range(1, 6, 2):\n",
    "    print(i, end=' ')\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Indexing Lists with `range(len(L))`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "index 0 - a\n",
      "index 1 - b\n",
      "index 2 - c\n",
      "index 3 - d\n"
     ]
    }
   ],
   "source": [
    "mylist = ['a', 'b', 'c', 'd']\n",
    "for i in range(len(mylist)):\n",
    "     print('index', i, '-', mylist[i])\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* This is especially useful when you need to go simultaneously over two different lists of the same length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a1, b2, c3, d4, "
     ]
    }
   ],
   "source": [
    "mylist1 = ['a', 'b', 'c', 'd']\n",
    "mylist2 = [1, 2, 3, 4]\n",
    "for i in range(len(mylist1)):\n",
    "     print(mylist1[i] + str(mylist2[i]), end=', ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration: `break` and `continue`\n",
    "\n",
    "* Use `break` to exit a loop \n",
    "* Use `continue` to go directly to next iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    if i == 2:\n",
    "        continue  # Now try with break\n",
    "    print(i)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Iteration: Exercise\n",
    "\n",
    "Using loops, write a program to print the following pattern:\n",
    "\n",
    "![Iteration exercise](figs/iteration_exercise.png \"Iteration exercise\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ⚡️ List Comprehensions\n",
    "\n",
    "```\n",
    "L = [*object, expression, or function* for *element* in *sequence*]\n",
    "L = [*object, expression, or function* for *element* in *sequence* if *Boolean expression*]\n",
    "L = [*object, expression, or function* for *element* in *sequence* for *element2* in *sequence2*]\n",
    "```\n",
    "\n",
    "* Provide a concise way to create lists\n",
    "* Faster because implemented in C\n",
    "* Nested list comprehensions can be somewhat confusing\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ⚡️ List Comprehensions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]\n",
      "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]\n"
     ]
    }
   ],
   "source": [
    "print([x**2 for x in range(1, 11)])\n",
    "\n",
    "ans = []\n",
    "for x in range(1, 11):\n",
    "    ans.append(x**2)\n",
    "print(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 16, 36, 64, 100]\n",
      "['a1', 'a2', 'a3', 'b1', 'b2', 'b3', 'c1', 'c2', 'c3']\n"
     ]
    }
   ],
   "source": [
    "print([x**2 for x in range(1, 11) if x%2 == 0])\n",
    "print([x + y for x in ['a', 'b', 'c'] for y in ['1','2', '3']])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ⚡️ Dictionary and Set Comprehensions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100}\n",
      "{'a': 1, 'b': 2, 'c': 2}\n",
      "{'o', 's', 't', 'm', 'n', 'g', 'e', 'a', 'r', 'i', 'd'}\n"
     ]
    }
   ],
   "source": [
    "print({x: x**2 for x in range(1, 11)})\n",
    "print({x.lower(): y for x, y in [('A', 1), ('b', 2), ('C', 2)]})\n",
    "\n",
    "print({x.lower() for x in 'SomeRandomSTRING'})\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## List Comprehensions: Exercise\n",
    "\n",
    "Rewrite the following code using a list comprehension:\n",
    "\n",
    "```\n",
    "sentence = \"the quick brown fox jumps over the lazy dog\"\n",
    "words = sentence.split()\n",
    "word_lengths = []\n",
    "for word in words:\n",
    "      if word != \"the\":\n",
    "          word_lengths.append(len(word))\n",
    "print(word_lengths)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Exhaustive Enumeration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The square root of 2500 is 50\n"
     ]
    }
   ],
   "source": [
    "# Find an approximation to the square root of a non-negative number\n",
    "\n",
    "x = 2500\n",
    "\n",
    "ans = 0\n",
    "\n",
    "# Increment ans until all options exhausted\n",
    "while ans**2 < x:\n",
    "    ans += 1\n",
    "    \n",
    "if ans**2 != x:\n",
    "    print(x, 'is not a perfect square')\n",
    "else:\n",
    "    print('The square root of', x, 'is', ans)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exhaustive Enumeration\n",
    "\n",
    "![Learning addition with an abacus as exhaustive enumeration](figs/exhaustive_enumeration.jpg \"Learning addition with an abacus as exhaustive enumeration\")\n",
    "\n",
    "\n",
    "* Systematically enumerate all possible solutions until you get the right answer or run out of possibilities\n",
    "* Example of **brute-force search** (a type of **guess and check** strategy) — a general problem-solving technique in computer science\n",
    "* Suprisingly useful as computers are quite fast these days!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Approximation with Exhaustive Enumeration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found 4.999000000001688 to be close approximation to the square root of 25\n",
      "num_guess = 49990\n"
     ]
    }
   ],
   "source": [
    "# Find an approximation to the square root of a non-negative number \n",
    "# using exhaustive enumeration\n",
    "\n",
    "x = 25\n",
    "\n",
    "epsilon = 0.01  # Precision of approximation  \n",
    "step = epsilon**2\n",
    "\n",
    "num_guess = 0 # Keep track of iteration steps\n",
    "ans = 0\n",
    "\n",
    "# Increment ans with step until close enough or until all options exhausted\n",
    "while abs(ans**2 - x) >= epsilon and ans <= x:\n",
    "    ans += step\n",
    "    num_guess += 1\n",
    "    \n",
    "if abs(ans**2 - x) >= epsilon:\n",
    "    print('Failed to find close approximation to the square root of', x)\n",
    "else:\n",
    "    print('Found', ans, 'to be close approximation to the square root of', x)\n",
    "    \n",
    "print('num_guess =', num_guess)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bisection Search\n",
    "\n",
    "![Searching for a word in a dictionary as bisection search](figs/bisection_search.jpg \"Searching for a word in a dictionary as bisection search\")\n",
    "\n",
    "* Start in the middle of the array, eliminate the half in which the answer cannot lie, and continue the search in the other half until you get the right answer or run out of possibilities\n",
    "* Example of **divide and conquer** strategy — an algorithm-design paradigm in computer science\n",
    "  \n",
    "* Naturally implemented as a recursive procedure (covered next week)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "notes"
    }
   },
   "source": [
    "*In divide and conquer algorithms you divide the problem into smaller pieces until you can solve them, then reassemble the pieces to find the final solution.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Approximation with Bisection Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found 5.00030517578125 to be close approximation to the square root of 25\n",
      "num_guess = 13\n"
     ]
    }
   ],
   "source": [
    "# Find an approximation to the square root of a non-negative number \n",
    "# using bisection search\n",
    "\n",
    "x = 25\n",
    "\n",
    "epsilon = 0.01  # Precision of approximation  \n",
    "num_guess = 0 # Keep track of iteration steps\n",
    "\n",
    "# Define interval for search\n",
    "low = 0\n",
    "high = max(1, x)\n",
    "\n",
    "# Start in the middle\n",
    "ans = (high + low) / 2 \n",
    "\n",
    "# Narrow down search interval until ans close enough\n",
    "while abs(ans**2 - x) >= epsilon:\n",
    "    if ans**2 < x:\n",
    "        low = ans\n",
    "    else:\n",
    "        high = ans\n",
    "    ans = (high + low) / 2\n",
    "    num_guess += 1\n",
    "    \n",
    "print('Found', ans, 'to be close approximation to the square root of', x)\n",
    "    \n",
    "print('num_guess =', num_guess)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Newton-Raphson Method for Finding Polynomial Roots\n",
    "\n",
    "![Root-finding with the Newton-Raphson method](figs/newton-raphson.jpg \"Root-finding with the Newton-Raphson method\")\n",
    "\n",
    "* $x^2 - 25$ is a polynomial $p$\n",
    "* Newton proved a theorem that implies that if $a$ is an approximation to the root of $p=0$, then $a - \\frac{p(a)}{p'(a)}$ is a better approximation\n",
    "* $p'$ is the first derivative of $p$. For $p = x^2 - 25$, $p' = 2x$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Example: Approximation with Newton-Raphson Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13.0\n",
      "7.461538461538462\n",
      "5.406026962727994\n",
      "5.015247601944898\n",
      "5.000023178253949\n",
      "Found 5.000023178253949 to be close approximation to the square root of 25\n",
      "num_guess = 5\n"
     ]
    }
   ],
   "source": [
    "# Find an approximation to the square root of a number using Newton-Raphson method\n",
    "# Find x such that x**2 - 25 is within epsilon of 0.01\n",
    "\n",
    "k = 25\n",
    "\n",
    "epsilon = 0.01  # Precision of approximation  \n",
    "num_guess = 0 # Keep track of iteration steps\n",
    "\n",
    "# Initialize first guess\n",
    "ans = k\n",
    "\n",
    "# Use Newton's theorem until ans close enough\n",
    "while abs(ans**2 - k) >= epsilon:\n",
    "    ans = ans - ( (ans**2 - k) / (2*ans) )\n",
    "    print(ans)\n",
    "    num_guess += 1\n",
    "    \n",
    "print('Found', ans, 'to be close approximation to the square root of', k)\n",
    "    \n",
    "print('num_guess =', num_guess)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## ⚡️ Iteration and Efficiency\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* **Half a loop is better than one**: Use `continue` and `break` to shorten iteration\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* **One loop is better than two**: Consolidate loops whenever possible\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* **Two loops are better than nested loops**: Attempt to rewrite any nested loops\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Efficient Iteration: Exercise\n",
    "\n",
    "Rewrite the following code to make it more efficient:\n",
    "\n",
    "```\n",
    "tokens = []\n",
    "for line in textfile:\n",
    "    words = line.strip().split()\n",
    "    words = [word.lower() for word in words]\n",
    "    words = [word.replace('-', '') for word in words]\n",
    "    for word in words:\n",
    "        tokens.append(word)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Control Flow\n",
    "\n",
    "![Three categories of control flow](figs/control_flow.png \"Three categories of control flow\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-------\n",
    "\n",
    "* **Lab**: `for` loops and list comprehensions, including nested list comprehensions\n",
    "* **Problem Set 1 (SUMMATIVE)**: Practice conditional statements and iteration on data\n",
    "* **Next week**: Functions in Python"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}