{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>cs1001.py , Tel Aviv University, Fall 2017-2018</center></h1>\n",
    "<img src=\"http://www.pngall.com/wp-content/uploads/2016/05/Python-Logo-PNG-Image-180x180.png\" width=50/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recitation 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We talked about comlexity. First we had an intuitive intro through an exercise and then we formally defined the notion of $O$ and solved some theoretical exercises.\n",
    "\n",
    "#### Takeaways:\n",
    "\n",
    "<ol>\n",
    "  <li>The time complexity bound implies how that the running time changes as a function of the input size.</li>\n",
    "  <li>Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).</li>\n",
    "  <li>The Big O notation \"hides\" additive and multiplicative constants</li>\n",
    "  <li>Two solutions that have the same time complexity bound may differ in their running time (one can be more efficient than the other).</li>\n",
    "   <li>To analyze nested loops that are dependent, use a sum ($\\sum$), with the boundaries of the external loop as the limits and the number of iterations for the inner loop in the sum itself.</li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: Given an natural number $p$, how many right triangles exist with integer sized sides whose perimeter is $p$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model:\n",
    "\n",
    "How many triplets (a,b,c) are there such that:\n",
    "\n",
    "<ol>\n",
    "<li>$a^2 + b^2 = c^2$</li>\n",
    "  <li>$a + b + c = p$</li>\n",
    "  <li>$a,b,c > 0$ are all integers</li>\n",
    "</ol>\n",
    "\n",
    "### In order to avoid counting a triplet twice or more, we require:\n",
    "\n",
    "<ol>\n",
    "<li>$0 < a < b < c$</li>\n",
    "</ol>\n",
    "\n",
    "### Note:\n",
    "\n",
    "<ol>\n",
    "<li>$a \\neq b$ and $b \\neq c$</li>\n",
    "<li>The condition $b < c$ is redundant (since we require that $a,b,c > 0$ and $a^2 + b^2 = c^2$)</li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When computing code complexity, we\n",
    "<ol>\n",
    "    <li>define the entire content of the innermost loop as an “atomic operation” which takes constant time.</li>\n",
    "    <li>describe the complexity as a function of $p$ (i.e., use $p$ as the “problem size” or “input size”). \n",
    "        Note, however, that the formal definition of “problem size” for a numeric input is the size it takes to represent the input, i.e. $n = \\log(p)$. \n",
    "        Working with $p$ here is easier and more intuitive.</li>\n",
    "</ol>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trivial solution (v1):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def number_of_integer_right_triangles_v1(p):\n",
    "    cnt = 0\n",
    "    for a in range(1,p):\n",
    "        for b in range(1,p):\n",
    "            for c in range(1,p):\n",
    "                if a + b + c == p and a < b and a*a + b*b == c*c:\n",
    "                    cnt += 1\n",
    "    return cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis:\n",
    "\n",
    "$(p-1)^3$ iterations.\n",
    "\n",
    "The complexity is $O(p^3)$ (cubic complexity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Second version (v2):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we set $a,b$ and $p$, $c$ is already defined!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def number_of_integer_right_triangles_v2(p):\n",
    "    cnt = 0\n",
    "    for a in range(1,p):\n",
    "        for b in range(1,p):\n",
    "            c = p - a - b\n",
    "            if a < b and a*a + b*b == c*c:\n",
    "                cnt += 1\n",
    "    return cnt\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis:\n",
    "\n",
    "$(p-1)^2$ iterations.\n",
    "\n",
    "The complexity is $O(p^2)$ (squared complexity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Third version (v3):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We require $a<b$, so just start $b$'s loop from $a+1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def number_of_integer_right_triangles_v3(p):\n",
    "    cnt = 0\n",
    "    for a in range(1,p):\n",
    "        for b in range(a+1,p):\n",
    "            c = p - a - b\n",
    "            if a*a + b*b == c*c:\n",
    "                cnt += 1\n",
    "    return cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis:\n",
    "\n",
    "The loop are now dependent, so the number of iterations is: $\\sum_{a = 1}^{p-1} (p - (a+1)) = \\frac{(p-1)(p-2)}{2}$\n",
    "\n",
    "The complexity is again $O(p^2)$ (squared complexity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fourth version (v4):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$a = p-b-c < p-2a \\implies 3a < p$. Thus: $a < p/3$, that is, the maximal possible value of $a$ is $p//3$ (we add $1$ in order to include $p//3$ in the range).\n",
    "\n",
    "$b = p-a-c < p-a-b  \\implies 2b < (p-a)$. Thus: $b < (p-a)/2$, that is, the maximal possible value of $b$ is $(p-a)//2$ (we add 1 in order to include (p-a)//2 in the range)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def number_of_integer_right_triangles_v4(p):\n",
    "    cnt = 0\n",
    "    for a in range(1,p//3 + 1):\n",
    "        for b in range(a+1,(p-a)//2 + 1):\n",
    "            c = p - a - b\n",
    "            if a*a + b*b == c*c:\n",
    "                cnt += 1\n",
    "    return cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis:\n",
    "\n",
    "The number of iterations is: $\\sum_{a = 1}^{p/3} (\\lfloor\\frac{p-a}{2}\\rfloor + 1 - (a+1))$\n",
    "\n",
    "The complexity is again $O(p^2)$ (squared complexity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fifth version (v5):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$a+b+c=p \\implies c = p-a-b$. \n",
    "\n",
    "Substitute $c$ with $p-a-b$ in $a^2+b^2=c^2$ and isolate $b$ to get $b = \\frac{p^2-2ap}{2(p-a)}$.\n",
    "\n",
    "We don't even need to calculate c here!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def number_of_integer_right_triangles_v5(p):\n",
    "    cnt = 0\n",
    "    for a in range(1,p//3 + 1):\n",
    "        b = (p**2 - 2*a*p) / (2*(p-a))\n",
    "        if b == int(b) and a < b:\n",
    "            cnt += 1\n",
    "    return cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Analysis:\n",
    "\n",
    "$\\frac{p}{3}$ iterations.\n",
    "\n",
    "The complexity is $O(p)$ (linear complexity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experiment:\n",
    "\n",
    "For the input $p=240$: the runtimes rank: $v_1, v_2, v_3, v_4, v_5$.\n",
    "\n",
    "Once we double the input to $p=480$, the increase in runtime for $v_1$ is quadric (i.e. the runtimes is $2^3 = 8$ times slower), for $v_2,v_3,v_4$ its squared (i.e. the runtimes are $2^2=4$ times slower), and for $v_5$ its doubled."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "v1, p = 240 took 1.601157981541931 secs\n",
      "v2, p = 240 took 0.010859777806814463 secs\n",
      "v3, p = 240 took 0.006627583046110885 secs\n",
      "v4, p = 240 took 0.0012292747397566473 secs\n",
      "v5, p = 240 took 8.447809707945453e-05 secs\n",
      "\n",
      "v1, p = 480 took 11.816460675643185 secs\n",
      "v2, p = 480 took 0.04442245206757889 secs\n",
      "v3, p = 480 took 0.029284687634344664 secs\n",
      "v4, p = 480 took 0.005004340358311765 secs\n",
      "v5, p = 480 took 0.00014763929115702012 secs\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "def elapsed(expression,number=1):\n",
    "    ''' computes elapsed time for executing code\n",
    "    number of times (default is 1 time). expression should\n",
    "    be a string representing a Python expression. '''\n",
    "    t1=time.clock()\n",
    "    for i in range(number):\n",
    "        x = eval(expression)\n",
    "    t2=time.clock()\n",
    "    return t2-t1\n",
    "\n",
    "\n",
    "print(\"v1, p = 240 took\",elapsed(\"number_of_integer_right_triangles_v1(240)\"), \"secs\")\n",
    "print(\"v2, p = 240 took\",elapsed(\"number_of_integer_right_triangles_v2(240)\"), \"secs\")\n",
    "print(\"v3, p = 240 took\",elapsed(\"number_of_integer_right_triangles_v3(240)\"), \"secs\")\n",
    "print(\"v4, p = 240 took\",elapsed(\"number_of_integer_right_triangles_v4(240)\"), \"secs\")\n",
    "print(\"v5, p = 240 took\",elapsed(\"number_of_integer_right_triangles_v5(240)\"), \"secs\")\n",
    "print(\"\")\n",
    "print(\"v1, p = 480 took\",elapsed(\"number_of_integer_right_triangles_v1(480)\"), \"secs\")\n",
    "print(\"v2, p = 480 took\",elapsed(\"number_of_integer_right_triangles_v2(480)\"), \"secs\")\n",
    "print(\"v3, p = 480 took\",elapsed(\"number_of_integer_right_triangles_v3(480)\"), \"secs\")\n",
    "print(\"v4, p = 480 took\",elapsed(\"number_of_integer_right_triangles_v4(480)\"), \"secs\")\n",
    "print(\"v5, p = 480 took\",elapsed(\"number_of_integer_right_triangles_v5(480)\"), \"secs\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Big O notation\n",
    "\n",
    "Given two functions $f(n)$ and $g(n)$,\n",
    "\n",
    "$f(n) = O(g(n))$ \n",
    " If and only if there exist $c \\geq 0 $ and $n_{0}\\in \\mathbb{R}$ such that\n",
    " $\\forall n>n_0$    \n",
    "   $|f(n)| \\leq c\\cdot|g(n)|$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time complexity hierarchy\n",
    "  \n",
    "Let $n$ denote the size of the input.\n",
    "The most common time complexities we encounter are :\n",
    "\n",
    "* Constant - $O(1)$\n",
    "* Logarithmic - $O(\\log(n))$\n",
    "* Root/fractional - $O(n^{1/c})$ for $c>1$\n",
    "* Linear - $O(n)$\n",
    "* Loglinear - $O(n \\log(n))$\n",
    "* Polynomial - $O(n^{c})$ for $c>1$\n",
    "* Exponential - $O(c^{n})$ for $c>1$\n",
    "\n",
    "See also this list on [Wikipedia](http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prove or Disprove examples\n",
    "See some examples [here](http://tau-cs1001-py.wdfiles.com/local--files/recitation-logs-2017a/complexity_prove_or_disprove.pdf)"
   ]
  }
 ],
 "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.4.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}