P4M_Notebook_5

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "P4M Notebook 5.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Vh71OubDeRq"
      },
      "source": [
        "# Part 5:  Putting it together...\n",
        "\n",
        "To wrap things up, we are going to bring together the techniques we have seen, and attempt a few challenges.\n",
        "\n",
        "Please submit this notebook by 5pm (California time) on Wednesday, March 17th.  Your submission should include answers to all three questions from the first (Repetition and benchmarking) section, and **two** of the challenging problems."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tmXRsSLiDw2i"
      },
      "source": [
        "## Repetition and benchmarking\n",
        "\n",
        "Computers are very good at repetition.  As your programming skills improve, you can more easily coax your computer into performing more repetitions.  We have seen at least three ways of performing repetition:  with loops (e.g, for and while loops), with lists (especially slicing and comprehension), and with numpy arrays (especially vectorized functions).  \n",
        "\n",
        "It is good to see this, in a simple example, to reflect on what you've learned this quarter.  Our simple example will be producing a list of squares $n^2$ for $n$ in a range of numbers.\n",
        "\n",
        "The first things we learned were how to use Python as a calculator, printing \"answers\" to the screen, and using a \"for loop\" to repeat things.  Here is a bit of code in that spirit."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1_Gk52ZaDd1M"
      },
      "source": [
        "for n in range(10):\n",
        "  print(n*n)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CI7QBmfi8jn1"
      },
      "source": [
        "Then we learned about lists.  Here are two ways to make a list of the squares, from $0^2$ up to $9^2$.  We print the list at the end of each code block."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_pSgH2YtEoDT"
      },
      "source": [
        "L = []\n",
        "for n in range(10):\n",
        "  L.append(n*n)\n",
        "print(L)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7arqtxfWESCf"
      },
      "source": [
        "L = [0]*10\n",
        "for n in range(10):\n",
        "  L[n] = n*n\n",
        "print(L)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BG8Z6La18uv4"
      },
      "source": [
        "Hopefully you learned to give your lists better names, like `square_list`.  A very slick Pythonic way of producing a list is with \"list comprehension\".  Such an approach is in the code below."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uTel6wOOEZrm"
      },
      "source": [
        "square_list = [n*n for n in range(10)]\n",
        "print(square_list)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EDUFarMO836b"
      },
      "source": [
        "Finally, we learned about the numpy package, which pumps arrays through the processor very quickly.  A numpy approach is below."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "KWyPzv53EfRW"
      },
      "source": [
        "import numpy as np # First we have to load the package."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sCWmWLfWEgqV"
      },
      "source": [
        "A = np.arange(10)\n",
        "print(A*A)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WEKhWP4oE1GJ"
      },
      "source": [
        "Let's consider the question:  what is the fastest way to produce a list (or array) of squares?  To answer it, we will wrap things in different functions, and carry out some time analysis.  \n",
        "\n",
        "Notice that the functions are as identical as possible.  The method of creating a list/array is the different in each function.  But all the functions take a single input `N` and return a list or array with the squares of 0,...,N-1.  Note that there are **no print statements**!  Printing takes time, and we don't care about how much time it takes to *print* a list on your screen.  Also, if we run %timeit, then a print statement will fill your screen with tens of thousands of printed messages!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8fDM7N4UEkj1"
      },
      "source": [
        "def make_sq_1(N):\n",
        "  L = []\n",
        "  for n in range(N):\n",
        "    L.append(n*n)\n",
        "  return L"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qEZsZmViFJAE"
      },
      "source": [
        "def make_sq_2(N):\n",
        "  L = [0] * N\n",
        "  for n in range(N):\n",
        "    L[n] = n*n\n",
        "  return L"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NhGyT-BYFOpM"
      },
      "source": [
        "def make_sq_3(N):\n",
        "  return [n*n for n in range(N)]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Api8iz1eFRlN"
      },
      "source": [
        "def make_sq_4(N):\n",
        "  A = np.arange(N)\n",
        "  return A*A"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lZGA3AmEFVs0"
      },
      "source": [
        "%timeit make_sq_1(1000)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FVUJxnmfFYSU"
      },
      "source": [
        "%timeit make_sq_2(1000)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Zt1l8hOsFZxs"
      },
      "source": [
        "%timeit make_sq_3(1000)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pSVmRwAdFb5s"
      },
      "source": [
        "%timeit make_sq_4(1000)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wtjJCpIvF965"
      },
      "source": [
        "These benchmarks are useful, but let's do a graphical analysis.  This is the last thing we studied."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CNgnxRhFGIz9"
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "import seaborn as sns # In case we want some modern stylings.\n",
        "import time as time"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_nCiB6uSJT2C"
      },
      "source": [
        "Now we are going to create a graph to benchmark the performance of these three functions.  This will use a few new programming techniques."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3Qbzo01tFdi8"
      },
      "source": [
        "fig,ax = plt.subplots(1,1,figsize=(8,5)) # Initialize a plot.\n",
        "N_array = np.array([2**n for n in range(1,21)]) # We'll try N in the array [2,4,8,..,~1 million]\n",
        "for method in [make_sq_1, make_sq_2, make_sq_3, make_sq_4]: # A list of functions, oh my!\n",
        "  time_array = np.zeros(len(N_array)) # Initialize an array of zeros\n",
        "  for j,N in enumerate(N_array):  # See notes afterwards about the enumerate command.\n",
        "    time_tot = 0\n",
        "    for reps in range(10): # Average of 10 repetitions.\n",
        "      start_time = time.time()\n",
        "      method(N)\n",
        "      end_time = time.time()\n",
        "      time_tot += end_time - start_time\n",
        "    time_ave = time_tot / 10\n",
        "    time_array[j] = time_ave\n",
        "  plt.plot(N_array, time_array, label='Time using function '+method.__name__)\n",
        "plt.legend()\n",
        "plt.xscale('log')\n",
        "plt.yscale('log')\n",
        "plt.suptitle('Time to create a list of squares from 1 to N')\n",
        "plt.xlabel('Length of list (N)')\n",
        "plt.ylabel('Time (seconds)')\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "D7YqhyfZHgW5"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eWyplW1_Jfak"
      },
      "source": [
        "Let's do a line-by-line analysis.\n",
        "\n",
        "1.  `fig,ax = plt.subplots(1,1,figsize=(8,5))`\n",
        "\n",
        "2.  `N_array = np.array([2**n for n in range(1,21)])`\n",
        "\n",
        "3.  `for method in [make_sq_1, make_sq_2, make_sq_3, make_sq_4]:`\n",
        "\n",
        "4.  `  time_array = np.zeros(len(N_array)) # Initialize an array of zeros`\n",
        "\n",
        "5.  `  for j,N in enumerate(N_array):`\n",
        "\n",
        "6.  `    time_tot = 0`\n",
        "    `for reps in range(10):`\n",
        "      `start_time = time.time()`\n",
        "      `method(N)`\n",
        "      `end_time = time.time()`\n",
        "      `time_tot += end_time - start_time`\n",
        "    `time_ave = time_tot / 10`\n",
        "\n",
        "    `time_array[j] = time_ave`\n",
        "7.    `plt.plot(N_array, time_array, label='Time using function '+method.__name__)`\n",
        "\n",
        "8.  `plt.legend()`\n",
        "\n",
        "9.  `plt.xscale('log')`\n",
        "10. `plt.yscale('log')`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0Ucwm_uHKL1w"
      },
      "source": [
        "Line 1 initializes a plot, with figure size 8 inches by 5 inches.  The \"1,1\" means that the plot has no subplots, or more precisely, it is a 1 by 1 grid of plots.  (Only one plot).\n",
        "\n",
        "In line 2, we use a list comprehension to make a list [2,4,8,16,..., 2^20].  Note that 2^20 is about one million.  These are the N's that we're going to work with.\n",
        "\n",
        "Line 3 might be surprising and interesting.  The variable `method` is iterated through an array of four *functions*!  Yes, we can have a list of functions!  And then we can use those functions!  Functions are Python objects like any other, and they can be treated as such.\n",
        "\n",
        "Lines 4-6 create an array of times.  Instead of using the %timeit magic, we store our times in an array, and we carry out a timing experiment from scratch.  Line 4 just initializes a numpy array of zeros to fill later.\n",
        "\n",
        "Line 5 has a new command `enumerate` in the loop.  This makes `N` iterate through our `N_array`, and meanwhile `j` will simply \"count up\".  It's equivalent to setting `j=0` before the loop, and putting a `j = j + 1` within the loop to count.\n",
        "\n",
        "Line 6 carries out the timing experiment.  It runs a function (`method`) to create a list of squares up to `N`.  It does this 10 times, checking the time before and after each time.  Then it computes the average amount of time elapsed (among the 10 repetitions) and records this in the `time_array`.\n",
        "\n",
        "Line 7 plots `N` on the x-axis and time (`time_array`) on the y-axis with a line plot.  It assigns this plot a label, which is the name of the method.  To find the name of the function `method`, you can use `method.__name__`.  That's a bit fancier Python.\n",
        "\n",
        "Finally, Line 8 produces the legend from the labels.  \n",
        "\n",
        "Lines 9 and 10 make the x-axis and y-axis log-scaled, which is helpful since the variable `N` is increasing exponentially, and some times are as short as microseconds while others are closer to milliseconds or seconds.\n",
        "\n",
        "The rest is styling."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6anmwPIoLwdu"
      },
      "source": [
        "## Exercises\n",
        "\n",
        "1.  Interpret the plot above.  Which method is fastest for long lists?  Which method is fastest for short lists?  At what size `N` should you switch from one method to the other?\n",
        "\n",
        "2.  Add another method to the plot, by defining your own function `make_sq_5` that mirros the basic structure of the other `make_sq` functions.  Note that your function must create the list in a different way, but it should still take the same parameter `N` and return a list or numpy array.  Create the plot with your function added to the other four, and compare the performance of your method to the others.\n",
        "\n",
        "3.  Create a function with `def inflate(S):` which takes as input a string `S` and returns a string in which the 1st letter of `S` appears once, and the second letter appears twice, the third letter appears three times, etc.  For example, `inflate('Hello')` should return the string `'Heelllllllooooo'`.  You must use a loop of the form `for j,letter in enumerate(S):`, and *no other loops*!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5cc5rYeH9rcr"
      },
      "source": [
        "Put your solutions here."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3CDgf54dWoL"
      },
      "source": [
        "# Final challenges!\n",
        "\n",
        "Please turn in your notebooks with your attempts on **two** of the challenges below.  **Only two** will be graded."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HJJWMj_8VdXg"
      },
      "source": [
        "## Challenge 1\n",
        "\n",
        "If $N$ is a positive integer, then $r_3(N)$ is the number of ways that $N$ can be expressed as the sum of three squares.  Order and sign matter, so for example\n",
        "$$6 = 1^2 + 1^2 + 2^2 = (-1)^2 + 1^2 + 2^2 = 2^2 + (-1)^2 + (-1)^2 = \\cdots$$\n",
        "These are all different ways of expressing 6 as the sum of three squares.  In fact, $r_3(6) = 8 \\cdot 3 = 24$.  The 8 comes from the fact that there are eight sign-choices, and the 3 comes from the three orderings (1,1,2) and (1,2,1) and (2,1,1).\n",
        "\n",
        "In other words, $r_3(N)$ is the number of elements in the following set:\n",
        "$$\\{ (a,b,c) \\in {\\mathbb Z}^3 : a^2 + b^2 + c^2 = N \\}.$$\n",
        "\n",
        "Write a function that computes $r_3(N)$ as efficiently as you can, for somewhat large values of $N$ (e.g., $N \\approx 1000$).\n",
        "\n",
        "You can check whether your function is behaving correctly, by comparing to the values found at the [Online Encyclopedia of Integer Sequences](https://oeis.org/A005875).\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MqXUlGr6UbAI"
      },
      "source": [
        "def rep_three(N):\n",
        "  return R # The result of your function should be R."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CCzEYimdUa9Z"
      },
      "source": [
        "rep_three(6) # This should output 24."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Yoqn17uMUax1"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qRLhmGVkXd8K"
      },
      "source": [
        "# Challenge 2\n",
        "\n",
        "If $r$ is a positive real number, then the area of the circle of radius $r$ is $\\pi r^2$.  If you place this circle around the origin, on a sheet of graph paper, then you will find *about* $\\pi r^2$ \"grid points\" inside this circle.  The grid points inside the circle form the set\n",
        "$$S = \\{ (x,y) \\in {\\mathbb Z}^2 : x^2 + y^2 < r^2 \\}.$$\n",
        "\n",
        "Define $E(r) = \\pi r^2 - \\# S$ to be the \"error\" -- the difference between the area of the circle and the number of grid points within the circle.  \n",
        "\n",
        "Create a plot with $r$ on the horizontal axis and $E(r)$ on the y-axis.  Try to accomplish this as efficiently as possible, where $r$ ranges from $0$ to $1000$.\n",
        "\n",
        "Can you come up with a good bound $\\vert E(r) \\vert \\leq f(r)$ for some nice function $f(r)$, just by looking at your plot?  I.e., your plot of $E(r)$ should be bounded above by the graph of $y = f(r)$ and below by the graph of $y = -f(r)$.  If you can come up with such a bound, plot it too."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_gyzNqCaUavY"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kYWSMHMsY853"
      },
      "source": [
        "# Challenge 3\n",
        "\n",
        "The following result was found by Euler, but I've changed his numbers to $A$ and $B$ to make your life hard.\n",
        "\n",
        "Theorem:  A prime number $p$ can be expressed in the form $x^2 + 3 y^2$ if and only if $p$ is congruent to $A$ modulo $B$ (i.e., `p % B == A`).  \n",
        "\n",
        "Use experimental techniques to determine $A$ and $B$.  Now try the same for $3$ replaced by $4,5,6,7,8,9$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Zg0Nc1e6aDi7"
      },
      "source": [
        "# Challenge 4\n",
        "\n",
        "Pascal's triangle has $1$ in the first row, then $1, 1$ in the second rod, then $1,2,1$ in the third row, etc.  One can place these numbers in a triangle, with \"rows\" as diagonals, as drawn below.\n",
        "\n",
        "1 1 1 1 1 1\n",
        "\n",
        "1 2 3 4 5\n",
        "\n",
        "1 3 6 10\n",
        "\n",
        "1 4 10\n",
        "\n",
        "1 5\n",
        "\n",
        "1\n",
        "\n",
        "Et cetera.\n",
        "\n",
        "Turn these numbers into black and white dots, depending on whether they are even (black) or odd (white).  This produces an image like the following:\n",
        "\n",
        "X X X X X X\n",
        "\n",
        "X O X O X\n",
        "\n",
        "X X O O\n",
        "\n",
        "X O O\n",
        "\n",
        "X X\n",
        "\n",
        "X\n",
        "\n",
        "Now perform this in PIL, to create an image that fills the top-left triangle in an image of at least 200 x 200 pixels.  You should *not* be computing giant numbers like 200 factorial!  Each row of Pascal's triangle can be computed from the previous by addition... and you can perform this \"mod 2\" all the way through.\n",
        "\n",
        "Extra fun:  instead of black/white dots for even/odd, try colors based on remainders after dividing by three, by four, etc.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qjBNKFCd95sS"
      },
      "source": [
        "# Challenge 5\n",
        "\n",
        "Often when visualizing time-series data, it makes sense to look not at day-by-day changes, but rather at a 7-day rolling average.  For example, when looking at Covid-19 cases, there are reporting fluctuations from day to day, so instead it is usually better to look at the average number of cases over the previous 7 days.\n",
        "\n",
        "Write a function `def rolling(A, window=7):` which takes as input a one-dimensional numpy array `A`, and a parameter `window` whose default value is `7`.  The function must return an array `R` whose length is shorter than the length of `A`.  The entry `R[j]` should be the **average** of `A[j]`, `A[j+1]`, etc., up to `A[j+window-1]`.  \n",
        "\n",
        "Then use this function and matplotlib to produce a plot:  a line plot of the array `A` produced below, and a line plot of the 7-day rolling average `R` produced by your function.  These plots should be on the same figure, and clearly labeled.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lu-pNl8SbeEG"
      },
      "source": [
        "# Here is the code to produce your test array A.\n",
        "# Please use this array in your plot!\n",
        "\n",
        "x_array = np.arange(300)\n",
        "A = 5*(x_array/200)**2\n",
        "A = A + np.random.random(len(A))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oq5NDBV4_tCs"
      },
      "source": [
        "# Please use this code to import matplotlib.\n",
        "import matplotlib.pyplot as plt"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9BM_gTge_6rb"
      },
      "source": [
        "# Here is a plot of the array, to get you started.\n",
        "plt.plot(x_array, A)\n",
        "\n",
        "# Now it's time to write your function to produce the 7-day rolling average, add it to the plot, and make everything clear and labeled."
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3OlNFd1xJ1CV"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    }
  ]
}