israeldi.hw1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stats507 Homework 1, January 23rd, 2019\n",
    "### Israel Diego [(Go to Home Page)](https://israeldi.github.io/coursework/) \n",
    "\n",
    "#### Discussed with: Yutian Wang, Jack Stubblefield, and Xiaochuan Guo\n",
    "#### israeldi@umich.edu\n",
    "\n",
    "This notebook shows solutions to homework 1 for Stats507\n",
    "\n",
    "## Table of Contents\n",
    "\n",
    "1. [Problem 1: Warm up: Defining Simple Functions](#Problem-1:-Warm-up:-Defining-Simple-Functions)\n",
    "2. [Problem 2: Euclid's algorithm](#Problem-2:-Euclid's-algorithm)\n",
    "3. [Problem 3: Approximating Euler's number 𝑒](#Problem-3:-Approximating-Euler's-number-$e$)\n",
    "4. [Problem 4: Testing Properties of an Integer](#Problem-4:-Testing-Properties-of-an-Integer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 1: Warm up: Defining Simple Functions\n",
    "#### ([Back to Top](#Table-of-Contents))\n",
    "#### Time Spent: 5 minutes\n",
    "1. Define a function called `say_hi`, which takes no arguments and prints the string\n",
    "`Hello, world!` when called."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def say_hi():\n",
    "    print('Hello, world!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Define a function called `goat_pad`, which takes a string as its only argument, and prints that string, prepended and appended with the string `goat`. So, `goat_pad('bird')` should produce the output\n",
    "<center> `goatbirdgoat` </center>\n",
    "`goat_pad('_')` should produce the output\n",
    "<center> `goat_goat` </center>\n",
    "and so on. You may assume that the input is a string, so there is no need to perform any error checking in your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def goat_pad(s):\n",
    "    print('goat' + s + 'goat')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Define a function called `print_n`, which takes two arguments, a string `s` and an integer `n` (in that order), and prints the string `n` times, each on a separate line. You may assume that `s` is a string and that the integer `n` is non-negative."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_n(s, n):\n",
    "    for _ in range(n):\n",
    "        print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 2: Euclid's algorithm\n",
    "#### ([Back to Top](#Table-of-Contents))\n",
    "#### Time Spent: 30 minutes\n",
    "Euclid's algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm) is a method for finding the greatest common divisor (GCD) of two numbers. Recall that the GCD of two numbers m and n is the largest number that divides both m and n.\n",
    "1. The Wikipedia page above includes several pseudocode implementations of Euclid's algorithm. Choose one of these, and use it to implement a function `gcd`, which takes two integers as its arguments and returns their GCD. You may assume that both inputs are integers, so there is no need to include any error checking in your function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a, b):\n",
    "    while b != 0:\n",
    "        t = b\n",
    "        b = a % b\n",
    "        a = t \n",
    "    return(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Use your function to evaluate the GCDs of the following pairs of numbers:\n",
    "    1. 2018, 2019\n",
    "    2. 1200, 300\n",
    "    3. 5040, 60"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 300, 60)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = gcd(2018, 2019)\n",
    "B = gcd(1200, 300)\n",
    "C = gcd(5040, 60)\n",
    "\n",
    "A, B, C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. What does your function do if one or both of its arguments are negative? Does this behavior make sense?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-4, 4, -4)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Testing gcd(a, b) with numbers different signs\n",
    "gcd(8, -12), gcd(-8, 12), gcd(-8, -12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The output above is incorrect for the first and third function calls, because the GCD should always be positive no matter what the sign of the inputs. A way to correct this would be to `return(abs(a))` to avoid the output from being negative."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem-3:-Approximating-Euler's-number $e$\n",
    "#### ([Back to Top](#Table-of-Contents))\n",
    "#### Time Spent: 1.5 hours\n",
    "The base of the natural logarithm, $e$, is typically defined as the infinite sum\n",
    "<center>$$e=\\sum_{k=0}^{\\infty}\\dfrac{1}{k!}=1+1+\\frac{1}{2}+\\frac{1}{6}+\\frac{1}{24}+\\ldots,$$</center>\n",
    "where $k!$ denotes the factorial of $k$,\n",
    "<center>$$k!=k\\cdot(k-1)\\cdot(k-2)\\cdots3\\cdot2\\cdot1,$$</center>\n",
    "1. An early characterization of Euler's number, due to Jacob Bernoulli, was as the limit\n",
    "<center>$\\underset{x\\rightarrow\\infty}{\\lim}(1+\\frac{1}{x})^{x}$</center>\n",
    "Define a function called `euler_limit` that takes as an argument an integer $n$, and returns a float that approximates $e$ by taking $x=n$ in Equation (2). You may assume that the input to your function will be a positive integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euler_limit(n):\n",
    "    approx_E = (1 + 1/n) ** n\n",
    "    return(approx_E)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Define a function called `euler_infinite_sum` that takes a single non-negative integer argument $n$, and returns an approximation to $e$ based on the first $n$ terms of the sum in Equation (1). Your function should return a float. You may assume that the input will be a non-negative integer, so you do not need to include error checking in your function. As an example, `euler_infinite_sum(4)` should return the sum of the first four terms in Equation 1, so that ~euler_infinite_sum(4)~ returns $1+1+\\frac{1}{2}+\\frac{1}{6}\\approx2.667$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def euler_infinite_sum(n):\n",
    "    # Initials\n",
    "    approxSum = 0      # keeps track of the running sum \n",
    "    factorialTerm = 1  # keeps track of the product of integers for the factorial term\n",
    "    \n",
    "    # Looping through each term in the sum of e\n",
    "    for i in range(n):\n",
    "        if i == 0:\n",
    "            approxSum += 1\n",
    "        else:\n",
    "            factorialTerm *= i\n",
    "            approxSum += (1 / factorialTerm)\n",
    "    return(approxSum)\n",
    "\n",
    "euler_infinite_sum(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Define a function called `euler_approx` that takes a single argument, a float `epsilon`, and uses the sum in (1) to obtain an approximation of $e$ that is within `epsilon` of the true value of $e$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2.7182539682539684, 8)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def euler_approx(epsilon):\n",
    "    # Returns: a tuple with the approximate value of e within epsilon, and the number of terms\n",
    "    # needed to achieve this estimate i.e. (approx, n).\n",
    "    \n",
    "    # Initials\n",
    "    factorialTerm = 1   # keeps track of the product of integers for the factorial term\n",
    "    absError = 1        # keeps track of the error bound \n",
    "    \n",
    "    # The first if statement guards against values of epsilon larger than 1\n",
    "    if absError < epsilon:\n",
    "        return(absError, 0)\n",
    "    \n",
    "    # Here we use the fact that the error bound is given by the next term in the taylor polynomial, \n",
    "    # which we check inside of the while loop\n",
    "    else:\n",
    "        i = 1\n",
    "        while( absError >= epsilon ):\n",
    "            factorialTerm *= i\n",
    "            absError = 1 / factorialTerm\n",
    "            i += 1\n",
    "    return(euler_infinite_sum(i - 1), (i - 1)) \n",
    "\n",
    "euler_approx(0.0001)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2.7182818284590455, 19)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "# Alternate Solution\n",
    "def euler_approx(epsilon):\n",
    "    # Returns: a tuple with the approximate value of e within epsilon, and the number of terms\n",
    "    # needed to achieve this estimate i.e. (approx, n).\n",
    "    \n",
    "    # Initials\n",
    "    factorialTerm = 1   # keeps track of the product of integers for the factorial term\n",
    "    absError = math.e\n",
    "    \n",
    "    i = 0\n",
    "    while(absError > epsilon):\n",
    "        if i != 0:\n",
    "            factorialTerm *= i\n",
    "        absError -= 1 / factorialTerm\n",
    "        i += 1\n",
    "\n",
    "    return(euler_infinite_sum(i), i) \n",
    "\n",
    "euler_approx(0.0000000000000000000000000000000000000000000001)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Define a function called `print_euler_sum_table` that takes a single positive integer $n$ as an argument and prints the successive values obtained from `euler_infinite_sum(k)` as $k$ ranges from $1$ to $n$, one per line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_euler_sum_table(n):\n",
    "    # Initials\n",
    "    approxSum = 0      # keeps track of the running sum \n",
    "    factorialTerm = 1  # keeps track of the product of integers for the factorial term\n",
    "    \n",
    "    # Looping through each term in the sum of e\n",
    "    for i in range(n):\n",
    "        if i == 0:\n",
    "            approxSum += 1\n",
    "            print(approxSum)\n",
    "        else:\n",
    "            factorialTerm *= i\n",
    "            approxSum += (1 / factorialTerm)\n",
    "            print(approxSum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Which of these two approximations is better?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* By printing the first few values of both approximations, it is clear that `euler_infinite_sum` is the better approximation. For a more concrete proof, see below. \n",
    "\n",
    "Using the binomial formula,\n",
    "\\begin{align*}\n",
    "\\left(1+\\frac{1}{n}\\right)^{n}= & \\sum_{k=0}^{n}\\binom{n}{k}\\left(\\frac{1}{n}\\right)^{k}\\\\\n",
    "= & \\sum_{k=0}^{n}\\left(\\frac{n(n-1)\\cdots(n-k+1)}{k!}\\right)\\left(\\frac{1}{n}\\right)^{k}\\\\\n",
    "= & \\sum_{k=0}^{n}\\left(\\frac{1}{k!}\\right)\\left(1-\\frac{1}{n}\\right)\\left(1-\\frac{2}{n}\\right)\\cdots\\left(1-\\frac{k-1}{n}\\right)\\\\\n",
    "< & \\sum_{k=0}^{n}\\left(\\frac{1}{k!}\\right)\n",
    "\\end{align*}\n",
    "The last summation is the $n$-th Taylor expansion of $e$ and the strict inequality holds for any $n>1$. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem 4: Testing Properties of an Integer\n",
    "#### ([Back to Top](#Table-of-Contents))\n",
    "#### Time Spent: 1 hour\n",
    "In this problem, you'll get a bit more practice working with conditionals, and a first\n",
    "exposure to the kind of thinking that is required in a typical \"coding interview\" question.\n",
    "A positive integer $n$ is a power of $2$ if $n = 2^p$ for some integer $p \\geq 0$\n",
    "\n",
    "1. Write a function `is_power_of_2` that takes a positive integer as its only argument and returns a Boolean indicating whether or not the input is a power of $2$. You\n",
    "may assume that the input is a positive integer. You **may not** use the built-in math.sqrt function in your solution. You should need only the division and modulus (%) operations. Hint: the simplest solution to this problem makes use of recursion, though recursion is not necessary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_power_of_2(num):\n",
    "    if (num == 1):\n",
    "        return(True)\n",
    "    elif (num % 2) != 0:\n",
    "        return(False)\n",
    "    else:\n",
    "        return(is_power_of_2(num / 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Generalize your previous solution to a function `is_power` that takes two positive integers as its arguments, $b$ and $n$, in that order, and returns a Boolean. `is_power(b,n)` should return True if $n$ is a power of $b$ and `False` otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_power(b, n):\n",
    "    if (n == 1):\n",
    "        return(True)\n",
    "    elif (n % b) != 0:\n",
    "        return(False)\n",
    "    else:\n",
    "        return(is_power(b, n / b))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}