wk10/MY470_wk10_lecture.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### MY470 Computer Programming\n",
    "# Searching and Sorting Algorithms\n",
    "### Week 10 Lecture"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Problem Set 5 takes place in class tomorrow!\n",
    "\n",
    "* Come to your class. Don't be late. \n",
    "* **7 questions, 25 min long**\n",
    "  * Give **Big-O for time complexity** and explain reasoning in 1-2 sentences.\n",
    "  * Last 2 questions also ask you to write a simple function (~3 lines of code each)\n",
    "* If you miss class and have not informed us **in advance** with a valid reason, we will mark your submission as **no attempt** and assign 0 to it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overview\n",
    "\n",
    "We will practice thinking about algorithm design and complexity analysis:\n",
    "\n",
    "* Search algorithms\n",
    "    * Linear search\n",
    "    * Binary search\n",
    "* Sorting algorithms\n",
    "    * Bubble sort\n",
    "    * Selection sort\n",
    "    * Insertion sort\n",
    "    * Merge sort\n",
    "* Hashing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Searching\n",
    "\n",
    "![Searching](figs/searching.jpg \"Searching\")\n",
    "\n",
    "* The goal is to find a specific item in a collection of items\n",
    "* The answer could be `True` or `False`, or alternatively, the precise location of the item\n",
    "* In Python, search with `in`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "4 in [1, 2, 3, 4, 5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Linear/Sequential Search\n",
    "\n",
    "* Visit each item in the collection in order until you discover the item or until you run out of items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def linear_search(ls, e):\n",
    "    \"\"\"Assume ls is a list.\n",
    "    Return True if e is in ls, False otherwise.\n",
    "    \"\"\"\n",
    "    for i in range(len(ls)):\n",
    "        if ls[i]==e:\n",
    "            return True\n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 1: What is the time and space complexity of linear search?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Binary Search\n",
    "\n",
    "*Example of divide and conquer strategy – break the problem into smaller pieces, solve the smaller pieces, and then reassemble to get the result*\n",
    "\n",
    "\n",
    "* Assume search space is sorted\n",
    "* Start from the middle\n",
    "    * If the item is the one we are searching for, we are done\n",
    "    * If the item is larger than the one we are searching for, eliminate the upper half and repeat the search in the lower half\n",
    "    * If the item is smaller than the one we are searching for, eliminate the lower half and repeat the search in the upper half\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Binary Search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# binary_search() is called a \"wrapper function\" –\n",
    "# it hides the implementation details\n",
    "def binary_search(ls, e):\n",
    "    \"\"\"Assume ls is a list with its elements in ascending order.\n",
    "    Return True if e is in ls, False otherwise.\n",
    "    \"\"\"\n",
    "    \n",
    "    def b_search(ls, e, low, high):\n",
    "        # Decrement high - low\n",
    "        if high==low: # only one item left\n",
    "            return ls[low]==e\n",
    "        mid = (low + high)//2\n",
    "        \n",
    "        # Check if the item is at the midpoint\n",
    "        if ls[mid]==e:\n",
    "            return True\n",
    "        # If the item is smaller than the midpoint, search in the lower half \n",
    "        elif ls[mid] > e:\n",
    "            if low==mid: # no items left\n",
    "                return False\n",
    "            else:\n",
    "                return b_search(ls, e, low, mid - 1)\n",
    "        # If the item is larger than the midpoint, search in the higher half \n",
    "        else:\n",
    "            return b_search(ls, e, mid + 1, high)\n",
    "        \n",
    "    if len(ls)==0:\n",
    "        return False\n",
    "    else:\n",
    "        return b_search(ls, e, 0, len(ls) - 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 2: What is the time and space complexity of binary search?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## When to Sort and Use Binary Search\n",
    "\n",
    "* Best if searching needs to be done many times\n",
    "* For small $n$, the additional cost of sorting is likely not worth it\n",
    "* For large $n$, sorting may be too expensive and ultimately, sequential search may be preferable\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Sorting\n",
    "\n",
    "![Sorting](figs/sorting.jpg \"Sorting\")\n",
    "\n",
    "* The goal is to place items from a collection in some kind of order\n",
    "* Sorting requires two operations:\n",
    "    * Compare values\n",
    "    * Exchange values if they are not in the correct order\n",
    "* The efficiency of a sorting algorithm depends on the total number of comparisons and exchanges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 5, 1, 2, 4] [1, 2, 3, 4, 5]\n",
      "[1, 2, 3, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "ls = [3, 5, 1, 2, 4]\n",
    "ls_new = sorted(ls)\n",
    "print(ls, ls_new)\n",
    "\n",
    "ls.sort()\n",
    "print(ls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Sorting Algorithms\n",
    "\n",
    "* Bubble sort\n",
    "* Selection sort\n",
    "* Insertion sort\n",
    "* Merge sort\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bubble Sort\n",
    "\n",
    "![Bubble sort](figs/bubble_sort.jpg \"Bubble sort\")\n",
    "\n",
    "1. Iterate over a list and compare the item at the current position with every item in the remaining sublist; swap the items if necessary to get the correct ordering\n",
    "2. Repeat until no swaps are done\n",
    "\n",
    "[Visualization](https://visualgo.net/bn/sorting)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Bubble Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def bubble_sort(ls):\n",
    "    \"\"\"Assume ls is a list of elements that can be compared using >.\n",
    "    Sort ls in ascending order.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Start from the whole list, reducing towards the front\n",
    "    for passnum in range(len(ls) - 1, 0, -1):\n",
    "        # Consider each of the sublists\n",
    "        for i in range(passnum):\n",
    "            if ls[i] > ls[i + 1]:\n",
    "                # Swap, pushing the larger number to the back\n",
    "                ls[i], ls[i + 1] = ls[i + 1], ls[i]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 3: What is the time and space complexity of bubble sort?\n",
    "\n",
    "[Hint](https://www.youtube.com/watch?v=koMpGeZpu4Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Selection Sort\n",
    "\n",
    "1. Iterate over a list and look for the largest/smallest item in the remaining sublist\n",
    "2. Swap the item in the current position with the identified item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def selection_sort(ls):\n",
    "    \"\"\"Assume ls is a list of elements that can be compared using >.\n",
    "    Sort ls in ascending order.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Consider each position, starting from the back\n",
    "    for pos in range(len(ls) - 1, 0, -1):\n",
    "        max_pos = 0\n",
    "        # Find the largest item in the sublist until this position\n",
    "        for i in range(1, pos + 1):\n",
    "            if ls[i] > ls[max_pos]:\n",
    "                max_pos = i\n",
    "        \n",
    "        # Swap the item at this position with the largest item\n",
    "        ls[pos], ls[max_pos] = ls[max_pos], ls[pos]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 4: What is the time complexity of selection sort?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Insertion Sort\n",
    "\n",
    "1. Iterate over a list starting from the beginning\n",
    "2. Insert each new item into the previous sublist in order, shifting the positions of larger items by 1\n",
    "\n",
    "In essence, the algorithm maintains a sorted sublist in the lower positions of the list as it progresses one item ahead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def insertion_sort(ls):\n",
    "    \"\"\"Assume ls is a list of elements that can be compared using >.\n",
    "    Sort ls in ascending order.\n",
    "    \"\"\"\n",
    "    \n",
    "    for i in range(1, len(ls)):\n",
    "        currentvalue = ls[i]\n",
    "        pos = i\n",
    "\n",
    "        while pos > 0 and ls[pos - 1] > currentvalue:\n",
    "            ls[pos] = ls[pos - 1]\n",
    "            pos -= 1\n",
    "\n",
    "        ls[pos] = currentvalue\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Exercise 5: What is the time complexity of insertion sort?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Merge Sort\n",
    "\n",
    "*Example of divide and conquer strategy – break the problem into smaller pieces, solve the smaller pieces, and then reassemble to get the result*\n",
    "\n",
    "1. If the list has 0 or 1 elements, it is sorted\n",
    "2. If the list has more than 1 element, split the list in two and use merge sort on each\n",
    "3. Merge the results*\n",
    "\n",
    "\\* Merge by inspecting the first elements of the two lists and moving the smaller one to the end of the result list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def merge_sort(ls):\n",
    "    \"\"\"Assume ls is a list. \n",
    "    Return a new sorted list with same elements as ls.\n",
    "    \"\"\"\n",
    "    \n",
    "    if len(ls) <= 1:\n",
    "        return ls[:]\n",
    "    else:\n",
    "        middle = len(ls)//2\n",
    "        left = merge_sort(ls[:middle])\n",
    "        right = merge_sort(ls[middle:])\n",
    "        return merge(left, right)\n",
    "    \n",
    "    \n",
    "def merge(left, right):\n",
    "    \"\"\"Assume left and right are sorted lists.\n",
    "    Return a new sorted list containing the same elements as (left + right).\n",
    "    \"\"\"\n",
    "    \n",
    "    result = []\n",
    "    i, j = 0, 0\n",
    "    # Inspect the first items of the two lists and append the smaller one to results\n",
    "    while i < len(left) and j < len(right):\n",
    "        if left[i] < right[j]:\n",
    "            result.append(left[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            result.append(right[j])\n",
    "            j += 1\n",
    "    # Append any remaining items\n",
    "    while i < len(left):\n",
    "        result.append(left[i])\n",
    "        i += 1\n",
    "    while j < len(right):\n",
    "        result.append(right[j])\n",
    "        j += 1\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### The time and space complexity of merge sort\n",
    "* The time complexity of merge sort is $O(n \\log n)$. It takes $O(\\log n)$ splits and each of them requires a merge which is $O(n)$. In a merge, each item in the list will eventually be processed and placed on the sorted list, so it will take $n$ operations to get a list of size $n$\n",
    "* The space complexity is $O(n)$, as the algorithm copies the list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hashing\n",
    "\n",
    "![Hashing](figs/hashing.jpg \"Hashing\")\n",
    "\n",
    "* A **hash table** is a collection of items that are stored in a way that makes them easy to find later\n",
    "* The goal is to design a hash table that allows us to search on the order of $O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hash Table \n",
    "\n",
    "![Empty hash table](figs/hash_table_empty.png \"Empty hash table\")\n",
    "\n",
    "* This hash table has length 10 and is currently empty\n",
    "* Slots are named with integers starting at 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* The **hash function** defines how you map an item to its rightful slot\n",
    "    * For example, consider **the remainder method**, `i % h`, where `h` is the size of the hash table\n",
    "        * We need to store `20`, `22`, `34`, `45`, `117`\n",
    "        * `20 % 10 = 0`\n",
    "        * `22 % 10 = 2`\n",
    "        * `34 % 10 = 4`\n",
    "        * `45 % 10 = 5`\n",
    "        * `117 % 10 = 7`\n",
    "    \n",
    "![Hash table with items](figs/hash_table_filled.png \"Hash table with items\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hash Table Collisions\n",
    "\n",
    "A **collision** occurs when more than one item maps to the same slot\n",
    "\n",
    "![Hash table with collision](figs/hash_table_collision.png \"Hash table with collision\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The goal is to create a hash function that **minimizes the number of collisions, is easy to compute, and evenly distributes the items in the hash table**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hash Functions\n",
    "\n",
    "* The **remainder method** \n",
    "    * Guarantees that the result is within the range of slot names\n",
    "    * Because of this, the modulo arithmetic is typically present in some form in all hash functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* The **folding method** \n",
    "    * Divide the item into equal-size pieces and add them to get the hash value; then use `%`\n",
    "    * E.g. 04/12/2017 = 04 + 12 + 20 +17 = 53 % 10 = 3 (if table length is 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* The **mid-square method** \n",
    "    * Square the item and then extract some portion of the resulting digits to get the hash value; then use `%`\n",
    "    * E.g. 77 = 77^2 = 5929 = 92 % 10 = 2 (if table length is 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hash Functions for Strings \n",
    "\n",
    "* Map each character to an ordinal value and sum them to get the hash value; then use `%`\n",
    "* E.g. 'cat' = ord('c') + ord('a') + ord('t') = 99 + 97 + 116 = 312 % 10 = 2 (if table length is 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on built-in function ord in module builtins:\n",
      "\n",
      "ord(c, /)\n",
      "    Return the Unicode code point for a one-character string.\n",
      "\n",
      "99 97 116\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "help(ord)\n",
    "print(ord('c'), ord('a'), ord('t'))\n",
    "\n",
    "def hash(string, table_size):\n",
    "    summ = sum([ord(i) for i in string])\n",
    "    return summ % table_size\n",
    "\n",
    "hash('cat', 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* The problem is that anagrams will always map to the same slot\n",
    "* One way to fix this is to use the position of the character as a weight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercise 6: Hash Functions for Strings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 5\n"
     ]
    }
   ],
   "source": [
    "# Rewrite the hash function below to mutliply the ordinal value \n",
    "# for each character by the position of the character\n",
    "\n",
    "def hash(string, table_size):\n",
    "    summ = sum([ord(i) for i in string])\n",
    "    return summ % table_size\n",
    "\n",
    "print(hash('cloud', 10), hash('could', 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Resolving Collisions\n",
    " \n",
    "* Rehashing\n",
    "* Chaining\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Rehashing\n",
    "\n",
    "* If a collision occurs, place item into the next available empty slot (starting from the beginnning, if necessary)\n",
    "* When searching, continue **probing** until item is found or until you encounter an empty slot\n",
    "* `rehash(pos) = (pos + skip) % table_size`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "**Linear probing** (`skip = 1`)\n",
    "\n",
    "![Linear probing for collisions](figs/collision_linear_probing.png \"Linear probing for collisions\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Other variants include **plus 3 probing** (`skip = 3`) and **quadratic probing** (`skip = 1, 4, 9, 16, ...`)\n",
    "        \n",
    "![Plus 3 probing for collisions](figs/collision_plus3_probing.png \"Plus 3 probing for collisions\")    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Chaining\n",
    "\n",
    "* If a collision occurs, still place item into the proper slot\n",
    "* When searching, use the hash function to generate the slot and then use a searching technique to find the item in the collection at that slot\n",
    "\n",
    "![Hash table with collision](figs/hash_table_collision.png \"Hash table with collision\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* In theory, hashing provides $O(1)$ searching\n",
    "* In practice, due to collisions, the runtime depends on the **load factor**, or $\\lambda = \\frac{n}{h}$, where $n$ is the number of items and $h$ is the size of the hash table\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Searching and Sorting Algorithms\n",
    "\n",
    "* The best sorting algorithm is $O(n \\log n)$\n",
    "* To search an ordered list, use binary search, which is $O(\\log n)$ \n",
    "* To search an unordered list, the best we can do is $O(n)$\n",
    "* In practice, sorting and binary search is not always faster than linear search\n",
    "* Use hash tables for O(1) searches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-------\n",
    "\n",
    "* **Lab**: **Problem Set 5**, functional programming in Python\n",
    "* **Next week**: Basic tree and graph algorithms, course summary, guidance for final project"
   ]
  }
 ],
 "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
}