An IPython notebook for explaining basic concepts on algorithms analysis

gistfile1.json

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Ordenamiento por inserci\u00f3n\n",
      "==========================\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def insertion_sort(A):\n",
      "    j = 1\n",
      "    while j < len(A):\n",
      "        key = A[j]\n",
      "        i = j - 1\n",
      "        while (i >= 0) and (A[i] > key):\n",
      "            A[i + 1] = A[i]\n",
      "            i = i -1\n",
      "        A[i + 1] = key\n",
      "        j = j + 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "B = [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
      "print B\n",
      "insertion_sort(B)\n",
      "print B"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
        "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Correcci\u00f3n\n",
      "-----------\n",
      "\n",
      "**Invariante de ciclo** \n",
      "\n",
      "_Al comienzo de cada iteraci\u00f3n del ciclo externo el subarreglo $A[0..j-1]$ consiste de los elementos originalmente en $A[0..j-1]$  pero ordenados._\n",
      "\n",
      "La siguiente funci\u00f3n implementa la comprobaci\u00f3n correspondiente al invariante de ciclo.\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def invariant(A, original_A):\n",
      "    l1 = list(A)\n",
      "    l2 = list(original_A)\n",
      "    l2.sort()\n",
      "    return l1 == l2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "invariant([1, 2, 3, 4], [4, 3, 2, 1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "invariant([1, 2, 3, 4, 4], [4, 3, 2, 1, 5])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "La siguiente funci\u00f3n incluye aserciones para verificar que el invariante de ciclo se cumpla. Si la funci\u00f3n es correcto, estas aserciones no deber\u00edan fallar."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def right_insertion_sort(A):\n",
      "    original_A = list(A)\n",
      "    j = 1\n",
      "    assert invariant(A[0:j], original_A[0:j])\n",
      "    while j < len(A):\n",
      "        assert invariant(A[0:j], original_A[0:j])\n",
      "        key = A[j]\n",
      "        i = j - 1\n",
      "        while (i >= 0) and (A[i] > key):\n",
      "            A[i + 1] = A[i]\n",
      "            i = i -1        \n",
      "        A[i + 1] = key\n",
      "        j = j + 1\n",
      "    assert invariant(A[0:j], original_A[0:j])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "B = [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
      "right_insertion_sort(B)\n",
      "print B"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "La siguiente funci\u00f3n incluye un error, por lo tanto la aserci\u00f3n para comprobar el invariante de ciclo falla.\n",
      "Esto genera una excepci\u00f3n que es capturada para imprimir un mensaje y el estado de las variables."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def wrong_insertion_sort(A):\n",
      "    original_A = list(A)\n",
      "    j = 1\n",
      "    try:\n",
      "        assert invariant(A[0:j], original_A[0:j])\n",
      "        while j < len(A):\n",
      "            assert invariant(A[0:j], original_A[0:j])\n",
      "            key = A[j]\n",
      "            i = j - 1\n",
      "            while (i >= 0) and (A[i] < key):\n",
      "                A[i + 1] = A[i]\n",
      "                i = i - 1        \n",
      "            A[i + 1] = key\n",
      "            j = j + 1\n",
      "        assert invariant(A[0:j], original_A[0:j])\n",
      "    except  AssertionError:\n",
      "        print \"Error en el invariante de ciclo!\"\n",
      "        print \"j=\", j\n",
      "        print \"i=\", i\n",
      "        print \"A=\", A\n",
      "        print \"Original A=\", original_A"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "B = [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
      "wrong_insertion_sort(B)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Error en el invariante de ciclo!\n",
        "j= 2\n",
        "i= 0\n",
        "A= [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
        "Original A= [5, 4, 6, 3, 7, 2, 8, 1, 9]\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "An\u00e1lisis del tiempo de ejecuci\u00f3n\n",
      "--------------------------------"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Counter:\n",
      "    '''\n",
      "    Class Counter\n",
      "    Implements a step counter, which is used to compute the number of basic operations performed in\n",
      "    a particular call to a function.\n",
      "    '''\n",
      "    def __init__(self):\n",
      "        self.steps = 0\n",
      "\n",
      "    def reset(self):\n",
      "        self.steps = 0\n",
      "\n",
      "    def count(self):\n",
      "        self.steps += 1\n",
      "\n",
      "    def print_steps(self):\n",
      "        print \"Number of steps =\", self.steps\n",
      "        \n",
      "def acct_insertion_sort(A, acct):\n",
      "    j = 1; acct.count()\n",
      "    acct.count()\n",
      "    while j < len(A):\n",
      "        acct.count()\n",
      "        key = A[j]; acct.count()\n",
      "        i = j - 1; acct.count()\n",
      "        acct.count()\n",
      "        while (i >= 0) and (A[i] > key):\n",
      "            acct.count()\n",
      "            A[i + 1] = A[i]; acct.count()\n",
      "            i = i -1; acct.count()\n",
      "        A[i + 1] = key; acct.count()\n",
      "        j = j + 1; acct.count()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "B = [5, 4, 6, 3, 7, 2, 8, 1, 9,10]\n",
      "acct = Counter()\n",
      "acct_insertion_sort(B, acct)\n",
      "acct.print_steps()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Number of steps = 104\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Ahora vamos a analizar el comportamiento del algoritmo cuando el tama\u00f1o de la entrada var\u00eda. La siguiente funci\u00f3n genera arreglos al azar de tama\u00f1o 1 a n, llama la funci\u00f3n `acct_insertion_sort(l, acct)` y contabiliza el n\u00famero de pasos."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import random as rnd\n",
      "\n",
      "def exper_analysis(n):\n",
      "    results = []\n",
      "    acct = Counter()\n",
      "    for i in range(n):\n",
      "        l = range(i)\n",
      "        rnd.shuffle(l)\n",
      "        acct.reset()\n",
      "        acct_insertion_sort(l, acct)\n",
      "        results.append(acct.steps)\n",
      "    return results\n",
      "        \n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print exper_analysis(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[2, 2, 11, 20, 23, 41, 59, 80, 80, 116]\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "import pylab as pl\n",
      "pl.clf()\n",
      "x = np.arange(100)\n",
      "y = np.array(exper_analysis(100))\n",
      "pl.plot(x, y, 'k.')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "[<matplotlib.lines.Line2D at 0x1089abf90>]"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEACAYAAAC+gnFaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X90U/X9P/BnsJkOZ+kUmmCunGKbNoTWgpa4o+eM+Kkp\n0EFFpT2WHRpE6Q49c8XjQZz7Y+UPSTj7Y6KunoOrswcPtpztHNp5aFaZxPmrUYpOR9watbAmTeOg\nVIpWKu37+wdfLklo07RJmrT3+TjHc5qb3Jt778b7dfN6v9+vt0oIIUBERIo1J9knQEREycVAQESk\ncAwEREQKx0BARKRwDARERArHQEBEpHATBoK9e/eioKAA+fn52Lt3LwCgv78fFosFubm5KCkpwcDA\ngPx5m80GvV4Pg8GA9vZ2eXtnZycKCgqg1+tRW1ubgEshIqKpiBgI/vWvf+GPf/wjPvzwQ/zzn//E\n66+/ji+++AJ2ux0WiwVdXV0oLi6G3W4HALjdbjQ3N8PtdsPhcKCmpgaXpyls27YNDQ0N8Hg88Hg8\ncDgcib86IiKaUMRA8O9//xt33nknrrvuOlxzzTVYuXIl/vKXv6C1tRVWqxUAYLVacejQIQBAS0sL\nKisroVarkZWVhZycHLhcLvj9fgwODsJkMgEAqqqq5H2IiCi5IgaC/Px8vP322+jv78e3336Lw4cP\nw+v1IhAIQKPRAAA0Gg0CgQAAoLe3F5IkyftLkgSfz3fVdp1OB5/Pl4jrISKiSUqL9KbBYMDOnTtR\nUlKC66+/HsuWLcM111wT8hmVSgWVSpXQkyQiosSJGAgAYMuWLdiyZQsA4De/+Q0kSYJGo0FfXx+0\nWi38fj8yMzMBXHrS7+npkff1er2QJAk6nQ5erzdku06nG/P7cnJy8MUXX8R0UURESpKdnY3PP/98\n6gcQEwgEAkIIIU6dOiUMBoMYGBgQO3bsEHa7XQghhM1mEzt37hRCCHHixAlRWFgoLly4IL788ktx\n6623itHRUSGEECaTSXR0dIjR0VGxZs0a0dbWNub3RXFKivDb3/422aeQMngvruC9uIL34opY280J\nfxFs2LABZ86cgVqtRn19PebNm4ennnoKFRUVaGhoQFZWFg4ePAgAMBqNqKiogNFoRFpaGurr6+W0\nUX19PTZv3oyhoSGUlpZi9erVU49eREQUNxMGgn/84x9Xbbvxxhtx5MiRMT//9NNP4+mnn75q+x13\n3IFPP/10CqdIRESJxJnFKcpsNif7FFIG78UVvBdX8F7Ej+r/55dShkqlQoqdEhFRSou13eQvAiIi\nhWMgICJSOAYCIiKFYyAgIlI4BgIiIoVjICAiUjgGAiIihWMgICJSOAYCIiKFYyAgIlI4BgIiIoVj\nICAiUjgGAiKiJKqurobZbEZpaSkGBgaScg4MBERESdTV1YW33noLbW1tqK6uTso5TBgIbDYbli5d\nioKCAmzcuBEXLlxAf38/LBYLcnNzUVJSEhLFbDYb9Ho9DAYD2tvb5e2dnZ0oKCiAXq9HbW1tYq6G\niGiGmTt3LgCgqKgI+/btS8o5RAwEJ0+exEsvvYTjx4/j008/xcjICJqammC322GxWNDV1YXi4mLY\n7XYAgNvtRnNzM9xuNxwOB2pqauQa2du2bUNDQwM8Hg88Hg8cDkfir46IKMUdOHAA5eXleOONN5CR\nkRHVPvFOJ0UMBOnp6VCr1fj2229x8eJFfPvtt7j55pvR2toKq9UKALBarTh06BAAoKWlBZWVlVCr\n1cjKykJOTg5cLhf8fj8GBwdhMpkAAFVVVfI+RERKlpGRgYMHD0YdBID4p5MiBoIbb7wRTzzxBBYt\nWoSbb74ZGRkZsFgsCAQC0Gg0AACNRoNAIAAA6O3thSRJ8v6SJMHn8121XafTwefzxXzyRERKFO90\nUsTF67/44gs8++yzOHnyJObNm4fy8nK8+uqrIZ9RqVRQqVQxn0iwuro6+W+z2cy1SYmIgtTU1ODU\nqVMoLi7Gs88+G/PxIgaCY8eO4a677sJNN90EAHjggQfw/vvvQ6vVoq+vD1qtFn6/H5mZmQAuPen3\n9PTI+3u9XkiSBJ1OB6/XG7Jdp9ON+73BgYCISCmqq6vR1dWFuXPn4sCBA+Omi9auXYu1a9fKr3ft\n2hXT90ZMDRkMBnR0dGBoaAhCCBw5cgRGoxHr1q1DY2MjAKCxsRHr168HAJSVlaGpqQnDw8Po7u6G\nx+OByWSCVqtFeno6XC4XhBDYv3+/vA8REV2SrKGkEX8RFBYWoqqqCkVFRZgzZw5uv/12VFdXY3Bw\nEBUVFWhoaEBWVhYOHjwIADAajaioqIDRaERaWhrq6+vltFF9fT02b96MoaEhlJaWYvXq1Ym/OiKi\nGSRZQ0lV4vL4zhShUqmQYqdERDQtBgYGUF1djX379k1qFFGs7SYDARHRDBdru8kSE0REKWg6axAx\nEBARpaDp7DhmICAiSkHT2XHMPgIiohQ0mY5jdhYTESkcO4uJiCgmDARERArHQEBEpHAMBEREM0Ai\n5xUwEBARzQCJnFfAQEBENAMkcl4Bh48SEc0AkeYVcB4BEZHCcR4BERHFhIGAiEjhJgwE//nPf7B8\n+XL5v3nz5uG5555Df38/LBYLcnNzUVJSEjKcyWazQa/Xw2AwoL29Xd7e2dmJgoIC6PV61NbWJuaK\niIhoUibVRzA6OgqdTocPPvgAzz//PObPn48nn3wSe/bswdmzZ2G32+F2u7Fx40Z8+OGH8Pl8uPfe\ne+HxeKBSqWAymfDCCy/AZDKhtLQUv/rVr65aspJ9BEREkzOtfQRHjhxBTk4ObrnlFrS2tsJqtQIA\nrFYrDh06BABoaWlBZWUl1Go1srKykJOTA5fLBb/fj8HBQZhMJgBAVVWVvA8RESXPpAJBU1MTKisr\nAQCBQAAajQYAoNFoEAgEAAC9vb2QJEneR5Ik+Hy+q7brdDr4fL6YL4CIaCaZzpXHopUW7QeHh4fx\n17/+FXv27LnqPZVKBZVKFbeTqqurk/82m80wm81xOzYRUTJdniEMXAoKBw8enPQxnE4nnE5n3M4p\n6kDQ1taGO+64AwsWLABw6VdAX18ftFot/H4/MjMzAVx60u/p6ZH383q9kCQJOp0OXq83ZLtOpxvz\nu4IDARHRbBKPGcLhD8i7du2K6ZyiTg299tprcloIAMrKytDY2AgAaGxsxPr16+XtTU1NGB4eRnd3\nNzweD0wmE7RaLdLT0+FyuSCEwP79++V9iIhmm/FSQAcOHEB5eTneeOONCVcemzYiCufPnxc33XST\nOHfunLztzJkzori4WOj1emGxWMTZs2fl95555hmRnZ0t8vLyhMPhkLcfO3ZM5Ofni+zsbPHYY4+N\n+V1RnhIRUUpbuXKlACAAiPLy8oR+V6ztJktMEBElQGlpKdra2lBUVJTwp3/WGiIiSkGTWXw+VgwE\nRERTUF1dja6uLsydOxcHDhxInXz9FLDoHBHRFCRyoZdwqTh3IBgDAREpUiIXegk3nUFnKhgIiEiR\nIg3jjPcT/HQGnalgHwERURiz2SzP/i0vL5/S7N9gie44jrXdjHpmMRGRUsT7CT4jIyPmYJJI/EVA\nRBRmvCf4VB1pxOGjRETTJN4po3jh8FEiomkSnjJK9WGh0eIvAiKiKIWnjIJ/ISxevBiLFi1KStqI\nncVERNMkvNM3+BfCtddeG/M6A8nC1BAR0RQFz0VIT08HkLpzBSJhaoiIKA6ms8hcOI4aIiJSOI4a\nIiKimEQVCAYGBrBhwwYsWbIERqMRLpcL/f39sFgsyM3NRUlJScjQKZvNBr1eD4PBgPb2dnl7Z2cn\nCgoKoNfrUVtbG/+rISKiSYsqENTW1qK0tBSfffYZPvnkExgMBtjtdlgsFnR1daG4uBh2ux0A4Ha7\n0dzcDLfbDYfDgZqaGvkny7Zt29DQ0ACPxwOPxwOHw5G4KyMioqhMGAi+/vprvP3229iyZQsAIC0t\nDfPmzUNrayusVisAwGq14tChQwCAlpYWVFZWQq1WIysrCzk5OXC5XPD7/RgcHITJZAIAVFVVyfsQ\nEVHyTBgIuru7sWDBAjz88MO4/fbbsXXrVnzzzTcIBALQaDQAAI1Gg0AgAADo7e2FJEny/pIkwefz\nXbVdp9PB5/PF+3qIiGiSJpxQdvHiRRw/fhwvvPACVqxYge3bt8tpoMtUKhVUKlXcTqqurk7+22w2\nw2w2x+3YREQzndPphNPpjNvxJgwEkiRBkiSsWLECALBhwwbYbDZotVr09fVBq9XC7/cjMzMTwKUn\n/Z6eHnl/r9cLSZKg0+ng9XpDtut0ujG/MzgQEBFRqPAH5F27dsV0vAlTQ1qtFrfccgu6uroAAEeO\nHMHSpUuxbt06NDY2AgAaGxuxfv16AEBZWRmampowPDyM7u5ueDwemEwmaLVapKenw+VyQQiB/fv3\ny/sQEVHyRFVr6Pnnn8fPf/5zDA8PIzs7G3/6058wMjKCiooKNDQ0ICsrS66rYTQaUVFRAaPRiLS0\nNNTX18tpo/r6emzevBlDQ0MoLS3F6tWrE3dlREQUFc4sJiKa4TizmIiIYsJAQESkcAwEREQKx0BA\nRKRwDARERArHQEBEM85sWTQ+VTAQENGM09XVhbfeegttbW2orq6O+XhKDywMBEQ04wQvGh++PnCk\nRn289+IdWGYaBgIimnGCF40PXx84UqM+3nuRAosSMBAQ0YyTkZGBgwcPjrlIfKRGfbz3IgUWJWCJ\nCSKaVQYGBlBdXY19+/Zd1ahHem8mi7XdZCAgIoqguroaXV1dmDt3Lg4cOJCSAYS1hoiIEkgJHckM\nBEREESihI5mpISKateKR1pkJ/QrTkhrKysrCbbfdhuXLl8NkMgEA+vv7YbFYkJubi5KSkpAxuTab\nDXq9HgaDAe3t7fL2zs5OFBQUQK/Xo7a2dsonTUSzU7wndsUjrRNphNJsEVUgUKlUcDqd+Oijj/DB\nBx8AAOx2OywWC7q6ulBcXCwvaO92u9Hc3Ay32w2Hw4Gamho5Um3btg0NDQ3weDzweDxwOBwJuiwi\nmoninY9XQlonHqLuIwj/2dHa2gqr1QoAsFqtOHToEACgpaUFlZWVUKvVyMrKQk5ODlwuF/x+PwYH\nB+VfFFVVVfI+RERA/Btupc8PiFbUvwjuvfdeFBUV4aWXXgIABAIBaDQaAIBGo0EgEAAA9Pb2QpIk\neV9JkuDz+a7artPp4PP54nYhRDTzTbXhHi+lpIS0TjxEtXj9u+++i4ULF+J///sfLBYLDAZDyPsq\nlUpeoJ6IaKouN9yXRdvZezmldHmf4GPQxKIKBAsXLgQALFiwAPfffz8++OADaDQa9PX1QavVwu/3\nIzMzE8ClJ/2enh55X6/XC0mSoNPp4PV6Q7brdLoxv6+urk7+22w2w2w2T/a6iGgaJHqyVbQNvNL6\nApxOJ5xOZ/wOKCbwzTffiHPnzgkhhDh//ry46667xN/+9jexY8cOYbfbhRBC2Gw2sXPnTiGEECdO\nnBCFhYXiwoUL4ssvvxS33nqrGB0dFUIIYTKZREdHhxgdHRVr1qwRbW1tV31fFKdERCli5cqVAoAA\nIMrLy+N+/DVr1ggAoqioSJw9e3bcz509e1aUl5dH/MxsFmu7OeHeX375pSgsLBSFhYVi6dKlYvfu\n3UIIIc6cOSOKi4uFXq8XFosl5H+AZ555RmRnZ4u8vDzhcDjk7ceOHRP5+fkiOztbPPbYYwm5ICKa\nPtE21FOl9AY+WrG2m5xQRkRTNhMmWykBi84RkSLMhOJvycKic0SkCEoo/pYsDARENCMobWTQdGJq\niIhmBPZHjI99BERECsc+AiJKSZEqica7yijFhr8IiChugkf2nDt3Du+++y4AoLy8PGRWsNlslmcM\nL168GIsWLeJooBjE2m5GVWKCiCgawSUhtFotgLE7d4M7fq+99lrWCUoypoaIKG6CG/iOjg65kuiT\nTz4ZkgoKrjKanp4u78PRQMnB1BARxc14I3uCU0HhaSKOBoodRw0RUcorLS1FW1sbioqKuEhMAjAQ\nEFHK41N/YjEQEBEpHOcREBFRTBgIiGhCnAA2uzEQENGEWPlzdosqEIyMjGD58uVYt24dAKC/vx8W\niwW5ubkoKSkJeUKw2WzQ6/UwGAxob2+Xt3d2dqKgoAB6vR61tbVxvgwiSiRW/pzdogoEe/fuhdFo\nhEqlAgDY7XZYLBZ0dXWhuLgYdrsdAOB2u9Hc3Ay32w2Hw4Gamhq5A2Pbtm1oaGiAx+OBx+OBw+FI\n0CURUbwFTwALnxxGM9+EgcDr9eLw4cN49NFH5Ua9tbUVVqsVAGC1WnHo0CEAQEtLCyorK6FWq5GV\nlYWcnBy4XC74/X4MDg7CZDIBAKqqquR9iCj1ZWRk4ODBg8jIyGCaaBaaMBA8/vjj+N3vfoc5c658\nNBAIQKPRAAA0Gg0CgQAAoLe3F5IkyZ+TJAk+n++q7TqdDj6fL24XQUTTh2mi2SdiIHj99deRmZmJ\n5cuXjztGVaVSySkjIpr9gtNEnBw2O0SsPvree++htbUVhw8fxnfffYdz585h06ZN0Gg06Ovrg1ar\nhd/vR2ZmJoBLT/o9PT3y/l6vF5IkQafTwev1hmzX6XTjfm9dXZ38t9lshtlsnuLlEVG8XU4TUfI4\nnU44nc74HVBEyel0irVr1wohhNixY4ew2+1CCCFsNpvYuXOnEEKIEydOiMLCQnHhwgXx5Zdfiltv\nvVWMjo4KIYQwmUyio6NDjI6OijVr1oi2trYxv2cSp0REUdi6datYuXKlWLNmjTh79myyT4cSINZ2\nc1LrEVxOAT311FOoqKhAQ0MDsrKy5KcDo9GIiooKGI1GpKWlob6+Xt6nvr4emzdvxtDQEEpLS7F6\n9er4RTMiGlfwGgGR6v0HLyqzYMECnDp1iovFKARrDRHNctFW/gwuFT1//nycPn0awNVloyn1sNYQ\nEUU0XudueNmI4NFAy5Ytk//myKDZj78IiBQqfLGYffv2yaWiAbBs9AzCMtRENCVcLGb2YCAgoinh\nYjGzBwMBEZHCsbOYiIhiwkBANENxsRiKFwYCohmKVUApXhgIiGYoVgGleGFnMdEMNd6on+BSESwP\noQwcNUREIcInirE8xOwXa7s5qaJzRJSagn8FqNVqAGOnjPhrgcbCPgKiWSC44/j6668fd+EYdjDT\nWPiLgGgWCO44fuWVV8Z90mcHM42FfQREs0C05SJYVmJ2YmcxEZHCJbTExHfffYc777wTy5Ytg9Fo\nxK9//WsAQH9/PywWC3Jzc1FSUhIyq9Fms0Gv18NgMKC9vV3e3tnZiYKCAuj1etTW1k75hImIKL4i\nBoLrrrsOR48exccff4xPPvkER48exTvvvAO73Q6LxYKuri4UFxfDbrcDANxuN5qbm+F2u+FwOFBT\nUyNHqW3btqGhoQEejwcejwcOhyPxV0dERBOacNTQ5c6l4eFhjIyM4Mc//jFaW1thtVoBAFarFYcO\nHQIAtLS0oLKyEmq1GllZWcjJyYHL5YLf78fg4CBMJhMAoKqqSt6HiIiSa8JAMDo6imXLlkGj0eCe\ne+7B0qVLEQgEoNFoAAAajQaBQAAA0NvbC0mS5H0lSYLP57tqu06ng8/ni/e1EBHRFEw4fHTOnDn4\n+OOP8fXXX2PVqlU4evRoyPsqlQoqlSquJ1VXVyf/bTabYTab43p8IqKZzOl0wul0xu14Uc8jmDdv\nHn72s5+hs7MTGo0GfX190Gq18Pv9yMzMBHDpSb+np0fex+v1QpIk6HQ6eL3ekO06nW7c7woOBERE\nFCr8AXnXrl0xHS9iauj06dPyiKChoSG88cYbWL58OcrKytDY2AgAaGxsxPr16wEAZWVlaGpqwvDw\nMLq7u+HxeGAymaDVapGeng6XywUhBPbv3y/vQ0REyRXxF4Hf74fVasXo6ChGR0exadMmFBcXY/ny\n5aioqEBDQwOysrLkolZGoxEVFRUwGo1IS0tDfX29nDaqr6/H5s2bMTQ0hNLSUqxevTrxV0c0A7D+\nDyUbJ5QRJUFw43/u3Dm8++67ACJXC2XAoPGw+ijRDHS5+BsAaLVaABPX/wnep7q6muWlKW5YfZQo\nCYKLv3V0dIxbLXS8fVgwjuKJqSGiJJhK8TcWjKPxsOgcUZIlMnfPfgGKRkKLzhHRxBK52AsXkqHp\nwEBAFKPxcvfV1dUwm80oLS0NqdAbj2MTxRNTQ0QxGi93H49F5NkvQNFgHwHRNIs2b19aWoq2tjYU\nFRVNOCKIKBbsIyCaZtHm7Q8cOBAyLDQeqSKiROCEMqJJijZvn5GREZIO4oQwSlX8RUA0SeFP+tFi\nxy+lKvYREMVRpP6DaDt+OXeAJoudxUQpJB4jheJxDFIWdhYTpZB4pH+YQqLpxl8ERHEUj3H/nDtA\nk8XUEFGchOfmn3zySebqaUZIeGqop6cH99xzD5YuXYr8/Hw899xzAID+/n5YLBbk5uaipKQkZFy0\nzWaDXq+HwWBAe3u7vL2zsxMFBQXQ6/Wora2d8kkTJUL4/IDg17fffjvnANDsJSbg9/vFRx99JIQQ\nYnBwUOTm5gq32y127Ngh9uzZI4QQwm63i507dwohhDhx4oQoLCwUw8PDoru7W2RnZ4vR0VEhhBAr\nVqwQLpdLCCHEmjVrRFtb21XfF8UpESXEmjVrBABRVFQkzp49G/L67rvvFgAEAFFeXp7sUyUKEWu7\nOeEvAq1Wi2XLlgEAfvSjH2HJkiXw+XxobW2F1WoFAFitVhw6dAgA0NLSgsrKSqjVamRlZSEnJwcu\nlwt+vx+Dg4MwmUwAgKqqKnkfolQQPj8g+HV6ejoAduDS7DSpUUMnT57ERx99hDvvvBOBQAAajQYA\noNFoEAgEAAC9vb2QJEneR5Ik+Hy+q7brdDr4fL54XANRXFyeCXy5LyD49VQnkRHNBFGXmDh//jwe\nfPBB7N27FzfccEPIeyqVCiqVKm4nVVdXJ/9tNpthNpvjdmyiqQgvF0GUTE6nE06nM27HiyoQfP/9\n93jwwQexadMmrF+/HsClXwF9fX3QarXw+/3IzMwEcOlJv6enR97X6/VCkiTodDp4vd6Q7Tqdbszv\nCw4EREQUKvwBedeuXTEdb8LUkBACjzzyCIxGI7Zv3y5vLysrQ2NjIwCgsbFRDhBlZWVoamrC8PAw\nuru74fF4YDKZoNVqkZ6eDpfLBSEE9u/fL+9DRETJM+E8gnfeeQc//elPcdttt8npH5vNBpPJhIqK\nCvz3v/9FVlZWSG519+7dePnll5GWloa9e/di1apVAC4NH928eTOGhoZQWloqD0UNOSHOIyAimhRO\nKCOKAQu80WzAWkNEMeDi8EQMBKRwLPBGxBXKSAEi1RB68cUXsWPHDhZ4I0VjHwHNKMGN+oIFC3Dq\n1KkJ8/vh9f2/+uor1vunWSXWdpO/CGhGCV73d/78+Th9+jSAq9cADg4YarUawJX0z8aNG0NeEykd\n+wgoJVRXV0dV3TM4p3+5BtZYDXpwJ/D1118/bg0hpoOIkHqlPlPwlGgarFy5MqrqnmfPnhXl5eXi\n7NmzIX+HC68kSjSbxdpuso+AUkJpaSna2tpQVFQUlyd1rvJFSsIJZTQrsOEmmjoGAiIihePMYiJE\n39lMRFdjIKBZgaUiiKaOgYBmBZaKIJo69hHQrMDOZlIydhYTESkcO4sppY3XicvOXaLUMWEg2LJl\nCzQaDQoKCuRt/f39sFgsyM3NRUlJScg/ZJvNBr1eD4PBgPb2dnl7Z2cnCgoKoNfrUVtbG+fLoFQ1\nXidupM7d4CBhtVoZMIgSbMJA8PDDD8PhcIRss9vtsFgs6OrqQnFxMex2OwDA7XajubkZbrcbDocD\nNTU18s+Vbdu2oaGhAR6PBx6P56pj0swS7ZN+cCfuD3/4Q/m98EJwwYKDxOHDhzkaiCjRoqlD0d3d\nLfLz8+XXeXl5oq+vTwghhN/vF3l5eUIIIXbv3i3sdrv8uVWrVon3339f9Pb2CoPBIG9/7bXXxC9+\n8YsxvyvKU6IkG682UPj24HpAwe/dd999UdUJuvfee1kziGgCsbabUypDHQgEoNFoAAAajQaBQAAA\n0Nvbi5/85Cfy5yRJgs/ng1qthiRJ8nadTgefzzeVr6YUMd5wzfDtGRkZcnno4PdeeeWVcUf3HDhw\nQB4BBICjgYgSLOb1CFQqFVQqVTzORVZXVyf/bTabYTab43p8mrzwVb6CG+vgBnq87RO9Fyw4eADg\nwjFEYZxOJ5xOZ9yON6VAoNFo0NfXB61WC7/fj8zMTACXnvR7enrkz3m9XkiSBJ1OB6/XG7Jdp9ON\ne/zgQECpIXhBmMuLwIzVQIc34tG+R0TRC39A3rVrV0zHm9Lw0bKyMjQ2NgIAGhsbsX79enl7U1MT\nhoeH0d3dDY/HA5PJBK1Wi/T0dLhcLgghsH//fnkfmhkizdzlUFCiGW6iToSHHnpILFy4UKjVaiFJ\nknj55ZfFmTNnRHFxsdDr9cJisYR04j3zzDMiOztb5OXlCYfDIW8/duyYyM/PF9nZ2eKxxx5LWKcH\nxc/WrVvFypUrxZo1a8TJkyfH7dyNdlEZIkqMWNtNzixWuPDcf3DuPnzR9/HSOvFeVIaIJocziykm\nkSZ2RVvIjWsAE81sMY8aoplhvCf/8MY++HMvvvgiduzYMelRPkQ0szA1pBDjpXnCq3ZGmw4iotTB\n1BBFZbxSD8Clcfrj/UIgotmPgWAWiTSMMziPf+rUqXH7BZjvJ1IepoZmuOCc/rlz5/Duu+8C4Cgf\nIiXhwjQKF5zT12q16OvrQ1FREYxGI06dOjXmsFCu5kU0u7CPQGEilXnu6OiIKv1zeZQPgwARARw+\nmpIiTfIKr/kTXshtrEqf7PQlokiYGkqi8Rr88CGcGRkZ8ue+//57HDlyZML8PtM/RMrBPoIZLLjB\nX7x4MRYtWjRmY79+/Xr5c/fddx9+8IMfsIEnIlms7SZTQ9Mo/BdAcPrm2muvDWnsy8vL5cY+2gVd\niIimJKaSdQmQgqcUN5GWcQxenjG8wmfw54iIwsXabjI1NEXBT/cLFiwIGar55JNPjvlepPw+c/pE\nNFXsI0gTtRX1AAAGZklEQVSS4Pz+/Pnzcfr0aQCXOne/+uqrMd9jfp+IEmHG9RE4HA5s374dIyMj\nePTRR7Fz587pPoWIon3SV6vVAC7l7TMyMuQn/X379mHjxo1jvsf8PhGlpBhTU5Ny8eJFkZ2dLbq7\nu8Xw8LAoLCwUbrc75DPTfEpCiNCVuO6++245jz9//vyQnH5wjv++++6T8/bhOfzg11PN7x89ejQB\nVzoz8V5cwXtxBe/FFbG2m9P6i+CDDz5ATk4OsrKyAAAPPfQQWlpasGTJkoR833hP9+FP+sGTtLRa\nLYCJn/TDn+6D6/qE1+efSilnp9MZsji1kvFeXMF7cQXvRfxMayDw+Xy45ZZb5NeSJMHlck36OFNp\n4INz9cF/V1dXhwzP/POf/ywvxnL5/cs5/fBZvEREs8G0BgKVShXV50pLS+PewAc/3Yc/6V/+fHiZ\nBiDykz4R0WwwraOGOjo6UFdXB4fDAQCw2WyYM2dOSIdxtMGCiIguyc7Oxueffz7l/ac1EFy8eBF5\neXn4+9//jptvvhkmkwmvvfZawvoIiIhoYtOaGkpLS8MLL7yAVatWYWRkBI888giDABFRkqXchDIi\nIppeKbMwjcPhgMFggF6vx549e5J9OtOqp6cH99xzD5YuXYr8/Hw899xzAID+/n5YLBbk5uaipKTk\nqnWIZ7ORkREsX74c69atA6DcezEwMIANGzZgyZIlMBqNcLlcir0XNpsNS5cuRUFBATZu3IgLFy4o\n5l5s2bIFGo0GBQUF8rZI126z2aDX62EwGNDe3j7h8VMiEIyMjOCXv/wlHA4H3G43XnvtNXz22WfJ\nPq1po1ar8fvf/x4nTpxAR0cH/vCHP+Czzz6D3W6HxWJBV1cXiouLYbfbk32q02bv3r0wGo3y4AGl\n3ova2lqUlpbis88+wyeffAKDwaDIe3Hy5Em89NJLOH78OD799FOMjIygqalJMffi4YcflgfZXDbe\ntbvdbjQ3N8PtdsPhcKCmpgajo6ORvyDmKW1x8N5774lVq1bJr202m7DZbEk8o+S67777xBtvvCHy\n8vJEX1+fEEIIv98v8vLyknxm06Onp0cUFxeLN998U6xdu1YIIRR5LwYGBsTixYuv2q7Ee3HmzBmR\nm5sr+vv7xffffy/Wrl0r2tvbFXUvuru7RX5+vvx6vGvfvXu3sNvt8udWrVol3n///YjHTolfBGNN\nNPP5fEk8o+Q5efIkPvroI9x5550IBALQaDQAAI1Gg0AgkOSzmx6PP/44fve732HOnCv/91Tiveju\n7saCBQvw8MMP4/bbb8fWrVvxzTffKPJe3HjjjXjiiSewaNEi3HzzzcjIyIDFYlHkvbhsvGvv7e2F\nJEny56JpT1MiEHDuwCXnz5/Hgw8+iL179+KGG24IeU+lUiniPr3++uvIzMzE8uXLx62mqJR7cfHi\nRRw/fhw1NTU4fvw4rr/++qtSH0q5F1988QWeffZZnDx5Er29vTh//jxeffXVkM8o5V6MZaJrn+i+\npEQg0Ol06OnpkV/39PSERDQl+P777/Hggw9i06ZNWL9+PYBLUb6vrw8A4Pf7kZmZmcxTnBbvvfce\nWltbsXjxYlRWVuLNN9/Epk2bFHkvJEmCJElYsWIFAGDDhg04fvw4tFqt4u7FsWPHcNddd+Gmm25C\nWloaHnjgAbz//vuKvBeXjfdvIrw99Xq90Ol0EY+VEoGgqKgIHo8HJ0+exPDwMJqbm1FWVpbs05o2\nQgg88sgjMBqN2L59u7y9rKwMjY2NAIDGxkY5QMxmu3fvRk9PD7q7u9HU1IT/+7//w/79+xV5L7Ra\nLW655RZ0dXUBAI4cOYKlS5di3bp1irsXBoMBHR0dGBoaghACR44cgdFoVOS9uGy8fxNlZWVoamrC\n8PAwuru74fF4YDKZIh8s3h0aU3X48GGRm5srsrOzxe7du5N9OtPq7bffFiqVShQWFoply5aJZcuW\niba2NnHmzBlRXFws9Hq9sFgsiluq0ul0inXr1gkhhGLvxccffyyKiorEbbfdJu6//34xMDCg2Hux\nZ88eYTQaRX5+vqiqqhLDw8OKuRcPPfSQWLhwoVCr1UKSJPHyyy9HvPZnnnlGZGdni7y8POFwOCY8\nPieUEREpXEqkhoiIKHkYCIiIFI6BgIhI4RgIiIgUjoGAiEjhGAiIiBSOgYCISOEYCIiIFO7/AUK1\nYJtIgMo2AAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x10897cd90>"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    }
   ],
   "metadata": {}
  }
 ]
}