{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline\n",
    "import pandas as pd\n",
    "\n",
    "import numpy as np\n",
    "from __future__ import division\n",
    "import itertools\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "\n",
    "import logging\n",
    "logger = logging.getLogger()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4 Mining Data Streams\n",
    "============\n",
    "\n",
    "Data:    \n",
    "1. database   \n",
    "2. stream:     \n",
    "    + lost forever if the data arrived is not processed immediately or stored.    \n",
    "    + the data arrives so rapidly that it isn't feasible to store all.   \n",
    "    \n",
    "    solution: summarization     \n",
    "        + sample/filter, then estimate     \n",
    "        + fixed-length \"window\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 The Stream Data Model\n",
    "\n",
    "Examples of Steam Sources:   \n",
    "\n",
    "+ Sensor Data:      \n",
    "  Deploy a million sensors    \n",
    "  \n",
    "+ Image Data:     \n",
    "  satellites, surveilance camera\n",
    "\n",
    "+ Internet and Web Traffic\n",
    "\n",
    "![Fig 4.1: A data-stream_management system](files/res/figure_4_1.png)\n",
    "\n",
    "##### 4.1.3 Stream Queries\n",
    "two ways:\n",
    "\n",
    "1. standing queries     \n",
    "   preset, permanetly execting, and produce outputs at appropriate times.    \n",
    "\n",
    "2. ad-hoc queries    \n",
    "   a question asked once about the current state of a steam or streams.    \n",
    "   + a common sample approach is to store a **sliding windows** of each stream in the working store.\n",
    "  \n",
    "  \n",
    "**generalizations** about stream algorithms:\n",
    "\n",
    "1. Often, an **approximate answer** is much more **efficient** than an **exact solution**.\n",
    "\n",
    "2. **hash function** introduces useful **randomness** intho the algorithm's behavior $\\to$ approximate answer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Sampling Data in a Stream\n",
    "\n",
    "extract reliable samples from a stream:    \n",
    "select $S \\subset B$, $\\, s.t. \\, E[f(S)] = E[f(B)]$.\n",
    "\n",
    "Example   \n",
    "Prob: What fraction of the typical user's queries were repeated over the past month?     \n",
    "\n",
    "given: a user has issued $s$ search queries one time, $d$ queries two times, and no queires more than twice.\n",
    "\n",
    "solutions:\n",
    "\n",
    "- _REAL_: $$tf = \\frac{d}{s+d}$$\n",
    "\n",
    "- _BAD_: store 1/10 th of the stream **elements**.    \n",
    "  + for s: $1/10 s$ one time    \n",
    "  + for d:      \n",
    "    $(1/10)*(1/10)*d = 1/100 d$ two times,      \n",
    "    $1/10*9/10 + 9/10*1/10 d = 18/100d$ one time.\n",
    "  + calc: \n",
    "  $$\\hat{tf} = \\frac{1/100d}{1/10s + 1/100d + 18/100d} = \\frac{d}{10s + 19d}$$\n",
    "\n",
    "- _GOOD_: pick 1/10th of the **users** and take all their searches for the sample.    \n",
    "  $$\\hat{tf} = \\frac{d}{s+d}$$     \n",
    "  \n",
    "  sample: **hash**    \n",
    "  obtain a sample consisting of any rational fraction $a/b$ of the users by hashing user names to $b$ buckets. Add the search query to the sample if the hash value is less than $a$.\n",
    "  \n",
    "  **The General Sampling Problem**   \n",
    "  Our steam $x$ consists of tuples with $n$ components $\\{x_n\\}$(eg: user, query, time), and a subset of the components are the _key_ components $x_k$(eg: user).     \n",
    "  To take a sample of size $a/b$, we hash the _key_ value $h(x_k)$ for each tuple to $b$ buckets, and accept the tuple if $h(x_k) < a$.\n",
    "  \n",
    "  **varying the sample size**    \n",
    "  storage is limited, while users/queries grows as time goes on  ==> decrease the select fraction $a/b$.    \n",
    "  \n",
    "  solution:   \n",
    "  1. $h(x) = \\{0, 1, \\dots, B-1\\}$, $B$ is sufficient large.    \n",
    "  2. maintain a threshold $t$, we accept when $h(x) < t$.       \n",
    "  3. $t = t - 1$ if the allotted space is exceeded. remove all samples $h(x) = t$.    \n",
    "     [opt] efficient:   \n",
    "     + lower $t$ by more than 1.    \n",
    "     + maintaining an index on the hash value to find all those tuples quickly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 4.3 Filtering Streams\n",
    "\n",
    "#### 4.3.2 The Bloom Filter\n",
    "\n",
    "##### component\n",
    "0. key values: $ S = \\{s_1, s_2, \\dotsm, s_m\\}$. \n",
    "\n",
    "1. array $B$ of $n$ bits, initially all 0's.\n",
    "\n",
    "2. $h_i(s_j) \\in [1, n], \\quad i = 1, 2, \\dotsm, k$.\n",
    "\n",
    "##### intialization\n",
    "1. $B$ are all 0's.\n",
    "\n",
    "2. $B[h_i(s_j)] = 1$ for every hash function and every key value.\n",
    "\n",
    "##### test\n",
    "to test a key $K$:    \n",
    "if $ALL_{i=1}^{k} (h_i(K)) = 1$, then allow it, $K \\in S$;  else reject it.\n",
    "\n",
    "##### Analysis\n",
    "we have $n$ targets, $k \\times m$ darts.\n",
    "\n",
    "1. a given dart will NOT hit a given target: $$ P = (n - 1) / n $$\n",
    "\n",
    "2. all darts will NOT hit a given target: \n",
    "   \\begin{align}\n",
    "        P &= (\\frac{n-1}{n})^{k m} \\\\\n",
    "          &= (1 - \\frac{1}{n})^{n \\frac{1}{n} k m} \\\\\n",
    "          &\\approx e^{-\\frac{k m}{n}}\n",
    "   \\end{align}\n",
    "   namely, the possibility of a bit remained 0 is $e^{-\\frac{k m}{n}}$. \n",
    "\n",
    "3. the possibility of a bit remained 1 is $1 - e^{-\\frac{k m}{n}}$.\n",
    "\n",
    "4. for a key $K$, the possibility of all of bits of $h_i(K)$ remained 1 is: $$ (1 - e^{-\\frac{k m}{n}})^{k} $$\n",
    "\n",
    "conclusion:    \n",
    "P[false negtive] = 0, P[false positive] = $ (1 - e^{-\\frac{k m}{n}})^{k} $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Counting Distinct Elements in a Stream\n",
    "Solution:\n",
    "\n",
    "1. keep a list of all the elements seens so far in main memeory. $\\gets$ the number of distinct elements is not too great.\n",
    "\n",
    "2. use more machines.\n",
    "\n",
    "3. the Flajolet-Martin algorithm.\n",
    "\n",
    "\n",
    "#### 4.4.2 the Flajolet-Martin Algorithm\n",
    "**tail length** for $a$ and $h$:     \n",
    "the number of 0's at the end of the bit string $h(a)$,      \n",
    "where $a$ is a stream element, and $h$ is a hash function which maps the elements of an universal set to a bit-string that is sufficiently long. \n",
    "\n",
    "**estimate**:     \n",
    "We use estimate $2^R$ for the number of distinct elements seen in the stream,   \n",
    "where $R$ is the maximum tail length of any $a$ seen so far in the stream.\n",
    "\n",
    "**original idea**:    \n",
    "$\\text{different elements }\\uparrow \\implies \\text{ different bit-string } h(a) \\uparrow \\implies \\text{ \"unusual\" value occurs } \\implies $ use unusual properity to estimate.  \n",
    "\n",
    "##### Analysis\n",
    "1. for a given $a$, the probility of $h(a)$ ending in at least $r$ 0's is: $(\\frac{1}{2})^r$.\n",
    "\n",
    "2. for $m$ distinct elements, the probility of none of them ending in at least $r$ 0's is: \n",
    "   \\begin{align}\n",
    "       \\neg P &= (1 - (\\frac{1}{2})^r)^m \\\\\n",
    "         &= (1 - 2^{-r})^{2^r 2^{-r} m} \\\\\n",
    "         &\\approx e^{-\\frac{m}{2^r}}\n",
    "   \\end{align}\n",
    "\n",
    "3. the probility of at least one of them ending in at least $r$ 0's is: $P = 1 - e^{-\\frac{m}{2^r}}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x109993750>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfgAAAFsCAYAAAAg36sqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xl8FPXBP/DP3tkkm/sgHMEcHEoQCMihcsglCFIQxFRN\nUdGqFezLR3xetiLFig/pg9ZaSx+pN9SC8hMCUjmkoAiIXHJpIBDIHXKQZLOb3ew18/sjh0SE7Ohu\nJjv7eb9evtjZ2d18RjGfne/MfEcliqIIIiIiUhS13AGIiIjI91jwRERECsSCJyIiUiAWPBERkQKx\n4ImIiBSIBU9ERKRAshX88ePHkZ2dfcXzu3btwpw5c5CVlYX169fLkIyIiCjwaeX4oW+++SY2b96M\nsLCwds+7XC7k5OTg448/RkhICH75y19i/PjxiI2NlSMmERFRwJJlD753797429/+hh/OsVNQUIDk\n5GSYTCbodDoMHToUhw4dkiMiERFRQJOl4CdPngyNRnPF81arFSaTqW05LCwMFoulM6MREREpgixD\n9FdjMpnQ2NjYttzY2IjIyMhrvkcURahUKn9HI6Ig5RFEOF0eOF0eOFweuNxC27LTLcDlEuB0Nz/v\ncnvgdAktjwW4PM3Pu90CXB6h3WO3W4DbI8DtEdue83gue84jwOMR4RZaXytCEAS4BbHldZxl/OdQ\nqQBVywNVyzKgav98y+Mr1l3tfS0rVfj+hd+/5vvXtT7fuvBjn4t272v5zJY3qlUqvPHshA63sUsV\nfGpqKoqKimA2m2E0GnHo0CHMnz//mu9RqVSorlbuXn58vInbF8C4fZ1DEEU4nB40OT1ocrpb/vS0\nPOdGk8sDp9ODppaSdjhb/nQJl5V3c1G3FrfbLaDJ6YFH6Lwi1ahV0GhU0KrV0GhUzctqNfRaNYwG\nNTRqFdRqFbRqVdtjjUbd8rqW5R88VquaH/9wOTzcgCa7q3mdCs3rVSqoLn9PS5moW55TqVuWVSqo\nVM3rVZe9rrV81K3lqGr/vuaXNP/ZutxaaGr19+9RAe0+A8D361p/Vutzl5fmZe9PSDChpsba7nWt\nvRssO4WyFnzrv+QtW7bAZrNh7ty5ePbZZzF//nwIgoA5c+YgISFBzohE1AkEQYTN4Uaj3YXGJjds\nTS1/Opof2xxu2FuXHW7YHW7YHR7YHe7mAnd48HNrWKtRw6BTQ6/TIESvRWiEFmoAOm3zczqtuvmx\nVg2dtmVZo4Zep4ZW07xOq2l+rvWxVquCTtPyWKOGVqOCVquGVq1u/vMHZd6ZxdNVvpz5i06rgVYT\n3FeCq5RwNzkl/yVV+v+E3L7AdrXtczg9aLA50WBzwtLoQoPNCavdBavNBYvdCYvN1bxsd6HR7oKt\nyS2poDVqFYwGLUL0GhgNWhj1GoS0LIfotTAaNDC0FHWIXgODXoMQnQb6lj8NLY8NOk1zqWs1UKvb\nl2uw/rdTimDYvo50qSF6Iuq6RFFEY5Mb9RYH6q0O1FkdcIlAeaUFZqsTZpsTDVYnzI1OOFyeDj9P\no1Yh3KhDVLgBPeLCEGbUNf8TokVoSMufhubHoS2PjQYtQkO00GvVQTPMSvRTseCJCADgcHlQ29CE\nS+YmXGpowqUGBy6Zm1BnaUKdxYE6iwNOt3DV96tVKpjCdEiMMSIiVI+IMD0iQvUwhelgMuoREaZD\nuFEPU6gO4UYdQvQaljSRH7HgiYKEKIowNzpRVWdHZZ0N1fV2VNc3oabejmpzExoanVd9b0SoDkmx\nYYg2GRBlMiA6XI+ocAN694wC3B5EmQwIN+raTn4iIvmx4IkUxu5wo+KSDRdrG3Gx1o6LtTZU1tpQ\nWWeD03XlHrhGrUJMhAHX945GXGQIYiNDEBvR/E9MZAiiww3QaX/8ZCWlH+ckCmQseKIA5XB5UF7T\niNIqK8pqGlFe04jyS42obXBc8VqDToNu0aFIiDYiPtqIxOhQxEcZER8VgmiTARp1cJ9tTKRELHii\nAFBvdaC40oKiSiuKKy0orbKiqs5+xZnn0SYDBlwXjaTYMCTFhqJbTCgSY0IRbTLweDdRkGHBE3Ux\nFpsTFyosuFDRgAsVDSi6aIH5B8fHw0K06NsrCj3jw9EzIQw94sPRPTYMoSH8X5qImvG3AZGMPIKA\n0qpGnCszo6DcjHOlZtSYm9q9JibCgCF94pCcaEJyYjh6J5q4R05EHWLBE3Uil1vAhYoGnCmuw5mS\nehSUNbS7ZjwsRIuBqbFISTLhuqQIpCRFIDJML2NiIgpULHgiP/J4BBSUmfFdYS3yiupwrqwBbs/3\nZ7InxYaiT89IpPWIRHqPSHSLCeWeORH5BAueyMdq6u04ef4STl2oRX5JPRqb3ACab3LRKyEcfXtF\noV9yFPr0ikJEKPfOicg/WPBEP5PbI+BsST1OnL+Ek+drUV7z/S2Pk2LDcFP/BNxwXQz6945GuFEn\nY1IiCiYseKKfoMnpxqnztfjmbDWOn7sEm6N5L12vVWNQWiwGpsUiIzUWA/okcCIYIpIFC57IS3aH\nG8fP1eBgXhVOXahtO5YebTJg5IBEDE6PQ7/kKOi0GpmTEhGx4Imuyeny4Ni5GhzKq8KJ85fgarnZ\nSo+4MAzpG4/MvnHonWjiiXFE1OWw4Il+QBBFnCs1Y9/JChw+UwW7o/kytqTYUNzUPwHDr09E97gw\nmVMSEV0bC56oRW1DE748UYF9JyvaJpuJNhlw25CeGHlDInrEh3FPnYgCBguegppHEHCyoBZfHCvD\nifOXIIrNN2a5JaMbbs7ohn7J0VCrWepEFHhY8BSUGmxO7DlWjt3flKHO0nz3tZQkE8YO7oHh1ycg\nRM//NYgosPG3GAWV4koLdh4uxYHvKuH2CAjRa3BbZg+MHdQdyYkmueMREfkMC54UTxRFfFtYi0+/\nKsLp4noAQEK0EROG9sStA5NgNPB/AyJSHv5mI8USBBGHz1Th0wNFKK60AgAGXBeNSTf1QkZqLNQ8\nYY6IFIwFT4rjEQR8daoSW/YXoqreDpUKGH59AqaO6I3e3TgMT0TBgQVPiiEIIr7+rhKb9l1AVZ0d\nWo0K44b0wJThvZAQHSp3PCKiTsWCp4AniiIOna5C7pcXcLHWBo1ahduG9MC0Ub0RExEidzwiIlmw\n4Cmg5ZfU48Nd53ChogEatQpjBnXH9Jt7Iy7SKHc0IiJZseApIFVcasT63QU4dq4GAHBT/wTMHpvK\noXgiohYseAootiY3Nu29gP8cKYUgiujTMxJzx6cjrXuk3NGIiLoUFjwFBEEU8dWpi1i/+xwabC4k\nRBkxd3w6hvSJ4/zwREQ/ggVPXV5xpQX/3JGPc2Vm6LVqzBqTiinDe/G+60RE18CCpy7L6fJg875C\nbPu6GIIoYmi/eGSN74PYSJ4ZT0TUERY8dUn5JfV4d+tpVNbaEBcZgl/d3g8ZqbFyxyIiChgseOpS\nmpxurP+8ALuPlkEFYOKwnrhrTCrv7kZEJBF/a1KXca7MjLc++Q5V9XZ0jwvDA1P7I70Hz44nIvop\nWPAkO7dHwCf7CrHlq0JABKaOTMbMW1Oh06rljkZEFLBY8CSrsmor/vTPI7hQYUFshAEPT78B/ZKj\n5Y5FRBTwWPAkm6+/q8Tq7adhd3gwakA33DepL0JD+FeSiMgX+NuUOp3LLWDdf85i9zdlMBo0eHTG\nAIy4IVHuWEREisKCp05VVW/H/+WeQtFFC3rGh+G5h0bAwInoiIh8jgVPneZEwSX8Y/O3sDncuHVg\nEu6b3Bc9E0yorrbIHY2ISHFY8OR3oihi+8ESrP/8HDRqNR68oz9G39hd7lhERIrGgie/crk9WL3t\nDPaduojIcD2enH0jUpIi5I5FRKR4LHjyG7PVgb9tOImC8gakJJmw4K4bEW0yyB2LiCgosODJL8pr\nGvHqR8dwqcGBkTck4oGp/aHX8e5vRESdhQVPPne2tB5//X8n0NjkxqzRKZh+83W8ZzsRUSdjwZNP\nHc2vxqrN38LjEfHQHdfj1huT5I5ERBSUWPDkM7uPluKfn+VDr9Vgwd0DMZC3dyUikg0Lnnzik/2F\n2LjnPCJCdfjt3YN4pjwRkcxY8PSziKKIjV+ex5b9RYiLDMHTWYORGB0qdywioqDHgqefTBRFfLT7\nHLYfLEFCtBHPZA1BbGSI3LGIiAgsePqJBFHEvz7Lx66jZUiKDcWirCG8xp2IqAthwZNkgihizfYz\n+OJYOXrGh2FR1hBEhOnljkVERJdhwZMkoihi3c6z+OJYOZITw7EoawjCjTq5YxER0Q+o5Q5AgWXD\nnvPYeaQUPeLC8PQ9g1nuRERdVKcXvCAIWLJkCbKyspCdnY3i4uJ26z/77DPMnj0bc+bMwdq1azs7\nHl3Dlv2F+PdXRUiINuLprMEwhXJYnoioq+r0IfqdO3fC5XJh3bp1OH78OHJycvD3v/+9bf3y5cuR\nm5sLo9GIadOmYfr06TCZTJ0dk37gs8Ml2LDnPGIjDHgmawiiwnlCHRFRV9bpBX/06FGMHj0aADBo\n0CCcOnWq3XqdToeGhgao1WqIosg5zLuA/acqsHbnWUSG6bGIl8IREQWETi94q9WK8PDwtmWNRgNB\nEKBWNx8tePDBBzF79mwYjUZMnjy53WuvJj5e2Xv4cm7f8fxqvPvpaYQZdXjp8VvQ2w8z1PG/X2BT\n8vYpedsAbp/SdXrBh4eHo7GxsW358nIvLy/HBx98gF27dsFoNOKZZ57Btm3bMGXKlGt+ZnW1xa+Z\n5RQfb5Jt+0qrrFj+wRGoVMCCWRkI1ap8nkXO7esM3L7ApeRtA7h9gc6bLy+dfpJdZmYm9uzZAwA4\nduwY+vXr17bO4XBArVZDr9dDrVYjJiYGFoty/wN1ZbUNTXh1/XHYHR7Mn3YD+iVHyx2JiIgkkFTw\nx48fxzvvvAOn04mHHnoII0aMwLZt2yT9wEmTJkGv1yMrKws5OTn43e9+hy1btuCjjz5CSkoKZs2a\nhaysLNx7772wWq2YNWuWpM+nn8/W5MZf1h9HncWBu8elYcQNiXJHIiIiiSQN0S9btgzPPPMMtm/f\nDoPBgI0bN2LBggUdDqFfTqVS4YUXXmj3XEpKStvjBx54AA888ICUWORDHkHA/+WeRGl1I27L7IEp\nI5LljkRERD+BpD14QRAwfPhwfP7557j99tvRvXt3CILgr2wkg/W7C/BtYR1uTIvFvRP78CoGIqIA\nJangjUYj3n77bRw4cADjxo3D+++/j7CwMH9lo06272QFdhwqQVJsKB6dMQAaNSc6JCIKVJJ+g7/8\n8suw2+14/fXXERUVhZqaGrzyyiv+ykad6Hx5A97fdgahBi2enH0jjAbepoCIKJB5/Vu8oKAA27Zt\nQ1VVFTZt2oQDBw5g8uTJ6Natmz/zUSeotzrwtw0n4BEEPPqLgUiMCZU7EhER/Uxe7cF/8MEH+K//\n+i+oVCoMHDgQGRkZEEURzz//PN5++21/ZyQ/crkFrNx4EvVWJ+aMS8PA1Fi5IxERkQ94tQf//vvv\nY9OmTTAaje2ef+ihhzBz5kzMnz/fL+HI/z7cdRYFZQ0YcUMipgznGfNERErh1R68TqeDy+W64nm7\n3Q69nncUC1SHT1dh19Ey9IgLwwNT+/OMeSIiBfFqD/6xxx7DrFmzMGrUKMTFxQEAampq8NVXX+Gp\np57ya0Dyj6p6O97dmge9To3HZ2bAoNPIHYmIiHzIq4K/8847MXz4cOzfvx/V1dUQRRHDhg3DwoUL\nkZjIWc4Cjcst4P9yT7VMQ3s9usfxUkciIqXx+iz6xMREThurEOt3n0PRRQtuGdgNtwxMkjsOERH5\nAWcyCTJHzlRj55FSdI8Lw/2T+nX8BiIiCkgs+CBSZ3Hg3U/zoNeq8fgvBsCg53F3IiKlklzwL774\nIpxOpz+ykB+Jooh3Ps2DzeFG1oQ+6BEfLnckIiLyI8kFHxUVxUvjAtDub8rw7YVaDEyNxdjB3eWO\nQ0REfia54M+dO4f3338fJSUl/shDfnCx1oaPdp1DWIgWD97B692JiIKB5DuK9O/fH0ajEX/5y19Q\nUlKC66+//or7u1PX4REEvPnJd3C6BcyffgOiwg1yRyIiok4gueBvuukmREdHY+7cuQCAqqoqn4ci\n3/n0qyJcqGjAyBsScVP/BLnjEBFRJ5Fc8MOGDWu3nJDA0uiqii5asHlfIaJNBtw3ua/ccYiIqBPx\nMjmF8ggC3t2aB48g4sE7+iMsRCd3JCIi6kQseIX67FApiiutuGVgN2Sk8BawRETBRlLBL1y48Irn\n5s2b57Mw5BtV9XbkfnkeplAd7hnfR+44REQkA6+OwT/xxBPIy8tDVVUVxo8f3/a8x+NBUhLnMu9K\nRFHEmm2n4XQLeGBqf4QbOTRPRBSMvCr4nJwcmM1mLFu2DM8//zxEUWx+s1bbdvtY6hq++vYivi2s\nQ0ZqDEbcwDv9EREFK68K3mQywWQy4Y033vB3HvoZGmxOrPvPOeh1avxqcj9OaENEFMQkHYM/fvw4\n3nnnHTidTjz00EMYMWIEtm3b5q9sJNGH/zkHq92Fu0anIi7KKHccIiKSkaSCX7ZsGTIyMrB9+3YY\nDAZs3LgR//jHP/yVjSTIL6nHV99eRO9uJkwc1kvuOEREJDNJBS8IAoYPH47PP/8ct99+O7p37w5B\nEPyVjbwkCCL+9Vk+AOD+SX2hVnNonogo2EkqeKPRiLfffhsHDhzAuHHj8P777yMsLMxf2chLe46X\no7jKilsyuiGtR6TccYiIqAuQVPAvv/wy7HY7Xn/9dURFRaGmpgavvPKKv7KRF6x2FzbsOY8QvQaz\nx6XJHYeIiLoISQUfHR2Nvn37ori4GLm5uejduzc+/PBDf2UjL+R+eR5WuwszbknhneKIiKiNpJvN\nLFiwAE1NTSgqKsJNN92EQ4cOYcKECf7KRh0oqbJi9zdl6BYTionDesodh4iIuhBJe/AXLlzA6tWr\nMWnSJMyfPx/r169HRUWFv7LRNYhi84l1ogj8cmIfaDW8rQAREX1PUivExcVBpVIhNTUVZ86cQWJi\nIqqrq/2Vja7h8JlqnCmpx+D0OAxM5c1kiIioPUlD9Onp6XjxxReRlZWFZ555BlVVVXA6nf7KRlfh\n9gj4+PMCaNQq3DMhXe44RETUBUnag1+6dCmmTp2KPn36YOHChaiuruZZ9DL44lg5qurtGDe4BxKj\nQ+WOQ0REXZCkgtdqtSgvL8err76KkSNHYsCAAejbt6+/stGPsDvc+GTfBRj0Gtx5y3VyxyEioi5K\nUsGvWLECX3zxBXbs2AG3240NGzZg+fLl/spGP2L7wWI02FyYOjwZEWF6ueMQEVEXJang9+7dixUr\nVsBgMCAyMhLvvvsu9uzZ469s9APmRie2HyxBRJgek4dzvnkiIro6SQWv0WjaLTudziueI//ZvO8C\nHC4PfnFrCkL0ks6PJCKiICOpJaZMmYKnnnoKZrMZ7733HjZt2oRp06b5KxtdprLWhj3HypEYE4rR\nNybJHYeIiLo4SQX/61//Gnv27EH37t1RUVGBJ598Erfddpu/stFlPt5zHh5BxOwxqZzUhoiIOiR5\nnHfMmDEYM2aMP7LQVRRXWnD4dBVSkiIwtF+83HGIiCgAeFXw2dnZV12nUqmwevVqnwWiK32yrxAA\nMGt0ClQq3uudiIg65lXBL1iw4KrrWDj+daHcjCP51UjtHoEBKTFyxyEiogDhVcGPGDHC3znoKtZ9\ndgYA8ItbufdORETe49laXVhJlRX7T1QgtXsEMrj3TkREErDgu7DN+y4A4N47ERFJJ6ngFy5ceMVz\n8+bN81kY+l5JlRVHzlSjb3IU996JiEgyr47BP/HEE8jLy0NVVRXGjx/f9rzH40FSEidd8YfWvfdf\nTu7PvXciIpLMq4LPycmB2WzGsmXL8Pzzz0MURQCATqdDbGysXwMGo9a995SkCAztn4CaGqvckYiI\nKMB4VfAmkwkmkwmvvfYavvjiC9hsNgDNe/ClpaX47W9/69eQwWbrgSIAwIxbruPeOxER/SSSZrJb\nsGABmpqaUFRUhJtuugmHDh3ChAkT/JUtKNXU23Ewrwo948NwYxpHR4iI6KeRdJLdhQsXsHr1akya\nNAnz58/H+vXrUVFR4a9sQWnHoRIIoogpI5K5905ERD+ZpIKPi4uDSqVCamoqzpw5g8TERFRXV0v6\ngYIgYMmSJcjKykJ2djaKi4vbrT9x4gTuu+8+3HvvvXjqqafgdDolfX4gs9pd2HOiHDERBgy/PlHu\nOEREFMAkFXx6ejpefPFFjBgxAu+//z5WrVoluYB37twJl8uFdevWYdGiRcjJyWlbJ4oilixZgpyc\nHPzrX//CqFGjUFpaKunzA9muo6VwugRMHtaLd4wjIqKfRVKLLF26FFOnTkV6ejoWLlyI6upqvPLK\nK5J+4NGjRzF69GgAwKBBg3Dq1Km2dRcuXEBUVBTeffddZGdno6GhAampqZI+P1A5XR7850gpQg1a\njB7UXe44REQU4CSdZKfVajFs2DAAwIQJE37SCXZWqxXh4eFtyxqNBoIgQK1Wo66uDt988w2WLFmC\n5ORkPProo8jIyMDIkSMl/5xAs+/URVhsLkwb1RtGg+S7+BIREbXT6U0SHh6OxsbGtuXWcgeAqKgo\nJCcnt+21jx49GqdOneqw4OPjTf4L3Ak8goidh0uh1ahxz+T+iI4Iabc+0LevI9y+wKbk7VPytgHc\nPqXr9ILPzMzE7t27MXXqVBw7dgz9+vVrW9erVy/YbDYUFxcjOTkZR44cwZw5czr8zOpqiz8j+93h\n01WouNSIMYO6w+1wobra1bYuPt4U8Nt3Ldy+wKbk7VPytgHcvkDnzZcXSQXvcrmwd+9emM3mttns\nVCoVZs6c6fVnTJo0Cfv27UNWVhYAYPny5diyZQtsNhvmzp2Ll156CU8//TREUURmZibGjh0rJWLA\nEUURW78uggrA7cN7yR2HiIgUQlLBP/3006ioqEBaWlq7a7SlFLxKpcILL7zQ7rmUlJS2xyNHjsT6\n9eulxApoBeUNuFBhweD0OCTFhskdh4iIFEJSwefn52Pr1q2cgMWHdh1pvgxw4rCeMichIiIlkXSZ\nXFpaGqqqqvyVJeiYrQ4cOl2F7nFhuL53tNxxiIhIQSTtwdvtdkyZMgV9+/aFXq8H0Dzkvnr1ar+E\nU7rPj5XDI4iYkNmDoyJERORTkgr+scce81eOoOP2CPj8mzIYDRqMyugmdxwiIlIYrwp+8eLFWLZs\nGV5//fUr1nEP/qc5cqYa5kYnJg7riRA9J7YhIiLf8qpZWi9pW7BgwRXrOLT80/yn5eS6CZk8uY6I\niHzPq4LPyMgAAIwYMcKvYYJF0UULzpWZMTA1FokxoXLHISIiBeIty2TQtvc+lHvvRETkHyz4Tmax\nOXHgu0okRBuRkRojdxwiIlIoFnwn23uiAm6PgPGZPaHm+QtEROQnkk7f3rhxI1QqVbt56ENCQpCa\nmoq+ffv6JaCSiKKIPcfLodOqcctAXhpHRET+I6ngd+3ahe+++w4TJ06EKIr44osvkJCQAJvNhunT\np+PBBx/0V05FyC+pR2WdHaMGJCIsRCd3HCIiUjBJBV9dXY2NGzciIiICAPDkk0/i0Ucfxbp163DX\nXXex4Duw53g5AGDMoO4yJyEiIqWTdAy+rq4OoaHfX9ZlMBhgNpuh0+mgVvNw/rU0Nrlw+Ew1EqON\n6NsrSu44RESkcJL24CdPnox58+bhjjvugMfjwY4dOzBx4kTk5uYiPj7eXxkV4cC3lXC5BYwZ1J2T\nAxERkd9Jvh/8rl27sH//fmg0GjzyyCMYO3Ysjh07hldeecVfGQOeKIr44lg5NGoVbua880RE1Akk\nFbzL5YJKpUJGRgZEUURtbS1yc3Mxc+ZMf+VThMKLFpRWW5HZNx6R4Qa54xARURCQvAdfUVGBtLS0\ndsPMLPhr48l1RETU2SQVfH5+PrZu3cpjyBI0Od048F0lok0GZKRw5joiIuockk59T0tLQ1VVlb+y\nKNKh01VwOD0YfWMS1Gp+MSIios4haQ/ebrdjypQp6Nu3L/R6PQDeD74jXx6vgArArTcmyR2FiIiC\niKSCf+yxx/yVQ5Eu1tpwrsyMAddFIy7SKHccIiIKIl4V/OLFi7Fs2TK8/vrrV6zjHvzVHfj2IgDg\n5gzuvRMRUefyquCzsrIAAAsWLOAJdl4SRRFffXsRep0aQ/rGyR2HiIiCjFcFf/bsWZw9exYArrib\nHP24grIGVNc3YdSARIToJR0JISIi+tm8ap6TJ09CpVKhoKAAxcXFmDBhArRaLXbv3o3U1FReB/8j\n9rcMz4/izHVERCQDrwp+yZIlAID77rsPGzduRGRkJADgiSeewMMPP+y/dAHK7RFwKK8SkWF6XN87\nWu44REQUhCRdB19TU4Pw8PC2Zb1ej7q6Op+HCnQnCi6hscmNETckQsO77BERkQwkHRweP348Hnjg\nAdx+++0QBAGffvoppk2b5q9sAeur1uH5ARyeJyIieUgq+P/+7//Gjh07cPDgQahUKvz617/G+PHj\n/ZUtIDU2uXD8XA16xIUhOTG84zcQERH5gaTxY7fbDb1ej4EDB2LAgAEwm83Izc31V7aAdPh0Fdwe\nESMHJPIqAyIikg3vJudjX53i8DwREcmPd5PzoZp6O/JLzeifHIWYiBC54xARURDj3eR86Ou8SgDc\neyciIvnxbnI+dCivChq1CkP7xcsdhYiIgpykgn/00UeveI7D9c0qa20orrLixrRYhIbo5I5DRERB\nTlLBjxgxwl85At6h082HLm7qnyBzEiIiIonH4AFg8+bNePXVV9HY2MhL5C5z+HTz8PyQPrxzHBER\nyU9Swa9YsQJffPEFduzYAbfbjY8//hjLly/3V7aA0To8PyAlhsPzRETUJUgq+L1792LFihUwGAyI\njIzEu+++iz179vgrW8Dg8DwREXU1kgpeo9G0W3Y6nVc8F4w4PE9ERF2NpJPspkyZgqeeegpmsxnv\nvfceNm3aFPQ3m6ms49nzRETU9Ugq+F//+tfYs2cPunfvjoqKCjz55JO47bbb/JUtIBxuGZ4f1o/D\n80RE1HXxpvfRAAAY90lEQVRIKngAGDNmDMaMGeOPLAGpdXKbIX05PE9ERF2H5Mvk6Hutw/MDUmIQ\nxuF5IiLqQljwPwOH54mIqKv6SQXvcrlQXV0Nh8Ph6zwBhcPzRETUVXl9DP7MmTPYtGkTmpqaoNPp\nYDQaYbVaAQCRkZG45557kJAQPHuy1fV2FFdZkZHK4XkiIup6vCr43NxcGAwGLFq0CGr1lTv9DocD\nW7ZsQY8ePTBy5Eifh+yKjp2tAQBk9uGd44iIqOvpsOCbmppw8803X3Pv3GAwYPbs2SgpKfFpuK7s\n2Lnmgh+UzuF5IiLqejo8Bh8SEnLVcj9w4ABqa2vblnv16uW7ZF1YY5MLZ4rrkZIUgWiTQe44RERE\nV5B8HfzTTz+NsLAwDBs2DIMHD8bWrVtx3333+SNbl3Wi4BIEUcRgTk1LRERdlOSCv/nmmzFo0CAc\nOXIEL7/8Mrp16+aPXF3aNy3H3zn3PBERdVWSC95qtSI9PR3p6em45557sGPHDknvFwQBS5cuRX5+\nPnQ6HV566SUkJydf8brnn38eUVFRePrpp6VG9CuXW8Cp85cQHxWCHnFhcschIiL6UZKvg09NTcX8\n+fPxwQcf4ODBg8jPz5f0/p07d8LlcmHdunVYtGgRcnJyrnjNunXrcPbsWahUKqnx/O5McR2anB4M\nTo/vkvmIiIiAn1Dwo0ePxgsvvIDa2lrs2LED48ePl/T+o0ePYvTo0QCAQYMG4dSpU1esP3HiBO65\n5x6Ioig1nt9xeJ6IiAJBh0P0DocDeXl5GDx4cNtzPXv2xMKFC6947VdffYVRo0Zd8/OsVivCw8Pb\nljUaDQRBgFqtRlVVFVauXImVK1fi008/lbIdnUIURRw7V4OwEC369IqUOw4REdFVdVjwBoMBWq0W\nb7/9NsaOHYv09PR26wVBwPHjx3Hw4EHccccdHf7A8PBwNDY2tnt/6+Q527dvR11dHR555BHU1NSg\nqakJaWlpmDlz5jU/Mz7e1OHP9YVzJfWoszgwbmhPdEvsvILvrO2TC7cvsCl5+5S8bQC3T+m8Osku\nIyMD/fr1w9atW7F27Vo4HA54PB6oVCqEh4dj5MiRePTRR736gZmZmdi9ezemTp2KY8eOoV+/fm3r\nsrOzkZ2dDQDYuHEjzp8/32G5A0B1tcWrn/1z7TpYBAC4oVdUp/3M+HhTp/0sOXD7ApuSt0/J2wZw\n+wKdN19evD6LXqfTYcaMGZgxY0bbc5fvfXtr0qRJ2LdvH7KysgAAy5cvx5YtW2Cz2TB37tx2r+1q\nJ7F9c7YGWo0KA1Ji5I5CRER0TZIvkzObzbh48SLS0tJw5MgROBwOjBkzxuv3q1QqvPDCC+2eS0lJ\nueJ1s2bNkhrNr2rq7SittmJgaiyMBsn/2oiIiDqV5Kb685//DI1Gg/z8fPTq1Qsmk0lSwQeq1rnn\nOXsdEREFAq8KvqSkpG2e+QkTJrQVekFBQZe8lM0fTpy/BAAYlBYrcxIiIqKOeVXwDz/8MMLCwpCU\nlISQkBCIoojRo0cjLS3N3/m6BKfLgzPF9egRH4aYiBC54xAREXXIq4L/85//jAEDBqCkpARHjhzB\nzp078de//hUxMTEYN26c4m82c6akHi63gIGp3HsnIqLA4FXBDxgwAEDz7WB79erVdunapUuXkJeX\n5790XcTJgubh+YE8e56IiAKE5KlqLxcbG4tbb73VV1m6rJMXamHQadCnV5TcUYiIiLzyswo+GFTV\n21FZa8P1vaOh1fBfFxERBQavGqt1Xvja2lq/humKTrWcPT+QZ88TEVEA8argX3vtNbjdbsyfP9/f\nebocHn8nIqJA5NVJdpmZmRg4cCBEUUT//v3brVOpVIo90c7lFpBXXIek2FDERRnljkNEROQ1r/bg\nly9fjry8PIwbNw6nT59u949Syx0A8kvr4XTx8jgiIgo8ks4ae+ONN/yVo0tqPf6ekcrheSIiCiyS\n5qIXBAFr167FgQMH4Ha7MXLkSGRnZ0u+o1ygOHm+FnqtGv14eRwREQUYSQW/YsUKFBUVYfbs2RBF\nER9//DFKS0vx3HPP+SufbC6Zm1Be04gb02Kh02rkjkNERCSJpILfu3cvcnNzodE0F964ceMwffp0\nvwST28kLLWfP8/g7EREFIElj64IgwOPxtC17PB5otcq8N/qp883X/PP4OxERBSJJ7XznnXciOzsb\n06dPhyiK+Pe//41p06b5K5ts3B4B3xXWIiHaiMToULnjEBERSSap4B977DFcf/31OHDgAERRxOOP\nP45x48b5KZp8CissaHJ6MGoA996JiCgwSR5fHzt2LMaOHeuPLF3Gd0XNw/PX946WOQkREdFPo8zr\n236mvMI6qAD0Z8ETEVGAklTwJ06c8FeOLsPh8qCg3IzkRBPCjTq54xAREf0kkgp+xYoVmD59Ot56\n6y1UV1f7K5OszpbWw+0Rcf113HsnIqLAJekY/Jo1a1BWVobc3Fw89NBD6N69O2bNmoUJEyZAp1PG\n3m5eYR0A4AYOzxMRUQCTfAy+R48emDlzJqZPn478/HysWbMG06dPx44dO/yRr9N9V1QHjVqFPj05\nPS0REQUuSXvwH330ETZv3oyqqirMnDkTa9euRbdu3VBZWYmZM2di8uTJ/srZKax2F4ovWtCnVxQM\nek5PS0REgUtSwR8+fBgLFy7E8OHDoVKp2p5PTEzEH/7wB5+H62xniusggsPzREQU+CQN0dtsNowY\nMaJduc+bNw8AMGXKFN8mk8F3Rc3H33mCHRERBTqv9uCfeOIJ5OXloaqqCuPHj2973uPxICkpyW/h\nOlteYR0Meg1SkiLkjkJERPSzeFXwOTk5MJvNWLZsGZ5//nmIotj8Zq0WsbHKuNtancWBi7U23JgW\nC62G8/8QEVFg86rgTSYTTCYT3njjDX/nkc13hZyeloiIlMOrgl+8eDGWLVuG7OzsK9apVCqsXr3a\n58E6W17r8XcWPBERKYBXBZ+VlQUAWLhwoV/DyEUUReQV1SHcqEPPhHC54xAREf1sXhX8n/70p6uu\nU8Ie/MVaG+osDgzrnwD1ZVcIEBERBSqvCn7hwoUQRbHd5XFK0jo8z+vfiYhIKbwq+M2bNyv6GPyZ\n4noAvD0sEREph6Rj8AsWLLhiXaDv1YuiiPySekSG6ZEYbZQ7DhERkU94VfAZGRkAgBEjRvg1jByq\n6u0wNzpxU/+EgP+yQkRE1ErSXPQulwsfffQRDhw4AI1Gg1tuuQVz5swJ6GLMbxme79uLd48jIiLl\nkFTwL774IiwWC2bNmgVBEJCbm4v8/Hw899xz/srnd/klLHgiIlIeSQX/zTff4JNPPmlbHj9+PGbM\nmOHzUJ0pv7QeoQYtesSHyR2FiIjIZyRNuh4fH4+ysrK25erqasTExPg8VGepbWhCdX0T+vaK4vXv\nRESkKF7twT/22GMAgPr6esyYMQOjRo2CRqPBwYMHkZ6e7teA/pRfyuF5IiJSJq8K/sEHH2y33HpS\n3b333hvYJ9iVmAGw4ImISHm8KvjWy+MEQcDatWtx4MABuN1ujBw5Evfff79fA/rT2ZJ66HVqJCdy\n/nkiIlIWSSfZrVixAkVFRZg9ezZEUcTHH3+M0tLSgDyL3mJzoqymETdcF837vxMRkeJIKvi9e/ci\nNzcXGo0GADBu3DhMnz7dL8H87Wwph+eJiEi5JO26CoIAj8fTtuzxeKDVSvqO0GW0Xv/ejwVPREQK\nJKmd77zzTmRnZ2P69OkQRRH//ve/MW3aNH9l86v8knpo1CqkJEXIHYWIiMjnJBV8YWEhfvOb3+DA\ngQMQRRGPP/44xo0b56do/mN3uFFUaUFaj0jodRq54xAREfmcpILPz8/H4sWLMXbsWH/l6RQFZWaI\nIofniYhIuSQVvFqtxm233YaUlBQYDAYAgXk/eE5wQ0RESiep4J955pkrJrYRRdGngTpDfnE9VCog\nvUek3FGIiIj8QlLBDxkyBP/617/abhc7duxYzJkzx1/Z/MLlFnC+ogHJCSYYDYF5BQAREVFHJDXc\n4sWL4XA4MHfu3Ha3i128eLG/8vlcUaUFbo+I9J7ceyciIuWSVPAnTpzA1q1b24bpx48fL/kyOUEQ\nsHTpUuTn50On0+Gll15CcnJy2/otW7Zg9erV0Gg06Nu3L5YuXerT+e4LyponuEnrwcvjiIhIuSRN\ndNOtWzeUlJS0LV+6dAkJCQmSfuDOnTvhcrmwbt06LFq0CDk5OW3rmpqa8Nprr2HNmjVYu3YtrFYr\ndu/eLenzO9Ja8OnduQdPRETKJfkg9C9+8QuMGjUKWq0WX3/9NRISEvDwww9DpVLhzTff7PD9R48e\nxejRowEAgwYNwqlTp9rWGQwGfPjhh21n6LvdboSEhEiNeE0F5Q2IDNMjNtK3n0tERNSVSCr4xx9/\nvN3yfffd1/bY22F0q9WK8PDv796m0WggCALUajVUKhViYmIAAGvWrIHdbsfNN9/c4WfGx5u8+tnV\ndXbUWRwYNTAJCQmBM0Tv7fYFKm5fYFPy9il52wBun9JJKvjW28b+HOHh4WhsbGxbbi33y5db71r3\n+uuve/WZ1dUWr153MK8SANAzNtTr98gtPt4UMFl/Cm5fYFPy9il52wBuX6Dz5stLp98nNTMzE3v2\n7AEAHDt2DP369Wu3fsmSJXA6nVi5cmXbUL2vFJQ1AADSeP07EREpXKdfCD5p0iTs27cPWVlZAIDl\ny5djy5YtsNlsyMjIwMcff4xhw4bhV7/6FQBg3rx5mDhxok9+dkG5GRq1Ctd1C+5hGyIiUr5OL3iV\nSoUXXnih3XMpKSltj/Py8vzyc11uD4ouWtArIZw3mCEiIsXr9CF6uRRdtMIjiByeJyKioBA0BX+O\nE9wQEVEQCZqCLyjnBDdERBQ8gqLgRVFEQZmZE9wQEVHQCIqCr21woN7qRFqPSJ/Oa09ERNRVBUXB\ntw7P8/g7EREFi+Ao+NYJbnj8nYiIgkRwFDwnuCEioiCj+IJvneAmOZET3BARUfBQfMG3TXDD4Xki\nIgoiii/41gluUnmCHRERBRHFF/yFCp5gR0REwUfxBV94sQHhRh3iOMENEREFEUUXvNXuQnV9E67r\nZuIEN0REFFQUXfCFF5uH569L4vF3IiIKLoou+AsVFgBACq9/JyKiIKPogi+s4B48EREFJ2UX/EUL\nIsP1iDYZ5I5CRETUqRRb8PVWB+osDqR04947EREFH8UWfGHL8ffrknj8nYiIgo9iC751gpsUHn8n\nIqIgpNiCL7zYsgfPM+iJiCgIKbLgRVHEhYoGxEWGwBSqlzsOERFRp1NkwV9qaILV7uLlcUREFLQU\nWfCFnOCGiIiCnCIL/gKnqCUioiCnyIJv3YPvncg9eCIiCk6KK3hBFFF40YJuMaEIDdHKHYeIiEgW\niiv4qjo77A43J7ghIqKgpriCb73BDKeoJSKiYKa4gr/AKWqJiIiUV/CFFxugVqmQzBPsiIgoiCmq\n4AVBRFGlBd3jwmDQaeSOQ0REJBtFFXxFrQ1Ol4De3cLljkJERCQrRRV8SWXz8XcOzxMRUbBTVMEX\nV1kBcIIbIiIiZRV8yx58z3gO0RMRUXBTTMGLoojiSivio0I4gx0REQU9xRR8ncUBq93F4+9ERERQ\nUMG3Hn9PTuDwPBERkXIKnmfQExERtVFMwZdUtuzBs+CJiIiUU/BFlRaYQnWICtfLHYWIiEh2iih4\nW5MLNeYmJCeEQ6VSyR2HiIhIdooo+JIqDs8TERFdThEFX9xy/L1XIs+gJyIiAhRT8M1n0HOKWiIi\nombKKPgqK/RaNRKjQ+WOQkRE1CUEfMG73ALKaxrRMyEcajVPsCMiIgIUUPDFFxvgEUSeYEdERHSZ\ngC/4C+VmAJyiloiI6HIBX/AFZS0Fzz14IiKiNgFf8BfKG6BSAT3iw+SOQkRE1GV0esELgoAlS5Yg\nKysL2dnZKC4ubrd+165dmDNnDrKysrB+/foOP+98mRlJsWEw6DT+ikxERBRwOr3gd+7cCZfLhXXr\n1mHRokXIyclpW+dyuZCTk4N3330Xa9aswYcffohLly5d8/PsDjePvxMREf1Apxf80aNHMXr0aADA\noEGDcOrUqbZ1BQUFSE5Ohslkgk6nw9ChQ3Ho0KEOP5PH34mIiNrr9IK3Wq0ID/9+j1uj0UAQhLZ1\nJtP3ZR0WFgaLxdLhZ3KKWiIiova0nf0Dw8PD0djY2LYsCALU6ubvGSaTqd26xsZGREZGXvPzPnnl\nF/4J2oXExyt7hILbF9iUvH1K3jaA26d0nb4Hn5mZiT179gAAjh07hn79+rWtS01NRVFREcxmM5xO\nJw4dOoTBgwd3dkQiIqKApxJFUezMHyiKIpYuXYozZ84AAJYvX45vv/0WNpsNc+fOxe7du7Fy5UoI\ngoA5c+bg3nvv7cx4REREitDpBU9ERET+F/AT3RAREdGVWPBEREQKxIInIiJSIBY8ERGRAnX6dfC+\nIggCli5divz8fOh0Orz00ktITk6WO5bPHT9+HC+//DLWrFkjdxSfcrlc+P3vf4/y8nI4nU48/vjj\nGD9+vNyxfMLj8WDx4sUoLCyESqXCCy+8gD59+sgdy+cuXbqEu+66C++99x5SUlLkjuNTs2bNapuQ\nq1evXvif//kfmRP51qpVq7B79264XC7cf//9mDVrltyRfGbjxo3YsGEDAMDhcOD06dPYv39/uwnW\nApUgCHjuuedQWFgItVqNF198EampqVd9fcAW/OVz2h8/fhw5OTn4+9//Lncsn3rzzTexefNmhIUp\n7055n3zyCWJiYrBixQqYzWbMnDlTMQW/e/duqNVqrF27FgcPHsSrr76quL+bLpcLS5YsgdFolDuK\nzzkcDgBQ3JfqVl9//TW++eYbrFu3DjabDW+99ZbckXxq1qxZbV9Y/vjHP+Luu+9WRLkDwN69e2G3\n27F27Vrs378ff/nLX/DXv/71qq8P2CH6a81prxS9e/fG3/72NyjxSsYpU6bgySefBND8rVSjUc7d\nACdOnIg//vGPAICysrIOZ2MMRP/7v/+LX/7yl4iPj5c7is+dPn0adrsd8+fPx7x583D8+HG5I/nU\nvn370K9fP/zmN7/BY489ppgv1j908uRJnD17FnfffbfcUXwmJCQEFosFoijCYrFAp9Nd8/UBuwd/\ntTntW6e9VYLJkyejtLRU7hh+ERoaCqD5v+Nvf/tbPPXUUzIn8i2NRoNnn30Wn3322TW/YQeiDRs2\nICYmBrfeeitWrVqluC+gRqMR8+fPx913343CwkI88sgj2L59u2J+t9TW1qKiogKrVq1CSUkJHn/8\ncWzbtk3uWD63atUqLFy4UO4YPpWZmQmn04kpU6agvr4eb7zxxjVfH7B/Y681pz0FhoqKCsybNw8z\nZ87EtGnT5I7jczk5Odi+fTuef/55NDU1yR3HZzZs2ID9+/cjOzsbp0+fxrPPPouamhq5Y/nMdddd\nhxkzZrQ9joqKQnV1tcypfCc6Ohq33nortFotUlJSYDAYUFtbK3csn2poaEBhYSGGDx8udxSfeuut\nt5CZmYnt27dj06ZNePbZZ+F0Oq/6+oBtxGvNaU9dX01NDR566CE888wzuOuuu+SO41O5ublYtWoV\ngOYhNZVKpagvn//85z+xZs0arFmzBv3798ef/vQnxMXFyR3LZzZs2ICcnBwAQGVlJaxWq6IORQwd\nOhRffvklgObts9vtiI6OljmVbx06dAgjR46UO4bP2e32tnOyIiIi4HK52u7G+mMCdoh+0qRJ2Ldv\nH7KysgA0z2mvVCqVSu4IPvfGG2/AYrFg5cqVWLlyJYDmb6cGg0HmZD/flClT8Oyzz+L++++H2+3G\nc889B71eL3cs8tKcOXPwu9/9Dvfddx+A5t8tSvqCNm7cOBw6dAhz5syBIAj4wx/+oLjfMYWFhYq8\nqmr+/Pn43e9+h3vvvRdutxtPP/00QkJCrvp6zkVPRESkQMr5WkpERERtWPBEREQKxIInIiJSIBY8\nERGRArHgiYiIFIgFT0REpEAseCIiIgUK2IluiKjzHT58GF9++SVGjx6NL7/8EuPGjcPWrVvx+9//\nXu5oRPQD3IMnIq/16NEDLpcLw4YNQ2NjI4YMGQKbzSZ3LCL6ESx4IvJaTU0NMjIyYDabER8fD4fD\nAb1ej6qqKrmjEdEPsOCJyGtnz57F0KFDkZeXh2HDhsFqtSIyMhJut1vuaET0A5yLnoiISIF4kh0R\neaV///4dvkalUiEvL68T0hBRR7gHT0SSffLJJ2hoaMDw4cPRp08fueMQ0Y9gwRORVwoKCnD+/Hmc\nOnUKKSkpmDBhAkwmk9yxiOgqOERPRF7ZsWMHpk+fDo1GA5vNxnIn6uK4B09Eknz00UdIT09HZmam\n3FGI6Bp4mRwRea2pqQkWi4XlThQAWPBE5LUvv/wSDz74IEpKSuSOQkQdYMETkVc2bNiAd955B/Pn\nz0d5ebnccYioAzwGT0REpEDcgyciIlIgFjwREZECseCJiIgUiAVPRESkQCx4IiIiBWLBExERKRAL\nnoiISIFY8ERERArEgiciIlKg/w8gsp1vnvuVTAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10990f650>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x = np.linspace(0, 8, 100)\n",
    "\n",
    "p = 1 - np.exp(-x)\n",
    "\n",
    "plt.plot(x, p)\n",
    "plt.xlabel(r'$\\frac{m}{2^r}$')\n",
    "plt.ylabel(r'probility of $h(a)$ ending in at least $r$ 0s')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "namely,    \n",
    "\\begin{equation}\n",
    "    P \\to \\begin{cases}\n",
    "        1 \\quad \\text{if } m \\gg 2^r \\\\\n",
    "        0 \\quad \\text{if } m \\ll 2^r\n",
    "    \\end{cases}\n",
    "\\end{equation}\n",
    "hence, $2^R$ is unlikely to be either much too high or much too low.\n",
    "\n",
    "\n",
    "##### Combining Estimates\n",
    "Suppose we have $k$ hash functions, then $k$ estimates $E_i$ of $m$ are obtained, but how to combine those estimates?\n",
    "\n",
    "Solutions:\n",
    "\n",
    "1. Average(E_i)   \n",
    "   cons: overestimate $\\Leftarrow$ if $E_p \\gg m \\gg E_q$, $Ave(E_p, E_q) \\to E_p$.\n",
    "   \n",
    "2. Median(E_i)    \n",
    "   cons: estimate is always a power of 2.\n",
    "   \n",
    "3. hybrid      \n",
    "   1. group $h_i$ to $b$ buckets containing $x$ hash functions.    \n",
    "      $x \\geq C log_2 m$ in order to guarantee that any possible average can be obtained.\n",
    "   2. average $E(h_i)$ in every buckets, obtain $E_b$.   \n",
    "   3. $\\text{median}(E_b) \\approx m$ when $b$ is sufficiently large,     \n",
    "\n",
    "space requirements:     \n",
    "keep one integer $R$ per hash function.    \n",
    "\n",
    "in practice, the **time** it takes to compute hash values would be the more significant limitation on the **number** of hash functions we use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "count unique elements, real: 7\n",
      "h(x) = x % 32, counts: 4\n",
      "h(x) = (2x + 1) % 32, counts: 1\n",
      "h(x) = (3x + 7) % 32, counts: 16\n",
      "h(x) = 4x % 32, counts: 16\n"
     ]
    }
   ],
   "source": [
    "logger.setLevel('WARN')\n",
    "\n",
    "# exercise 4.4.1\n",
    "\n",
    "def Flajolet_Martin_algorithm(stream, hash_func, bits):\n",
    "    R = 0\n",
    "    \n",
    "    for e in stream:\n",
    "        h = hash_func(e)\n",
    "        logger.info('e: {}, h:{}'.format(e, h))\n",
    "        \n",
    "        mask = 1\n",
    "        \n",
    "        for r in range(bits):\n",
    "            logger.info('mask: {}'.format(mask))\n",
    "            if not (h & mask):\n",
    "                mask <<= 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        logger.info('r: {}, R: {}'.format(r, R))\n",
    "        \n",
    "        if(r > R):\n",
    "            R = r\n",
    "            \n",
    "    return 2**R\n",
    "\n",
    "\n",
    "stream = np.array([3, 1, 4, 1, 5, 9, 2, 6, 5], dtype=np.int)\n",
    "print('count unique elements, real: {}'.format(len(np.unique(stream))))\n",
    "\n",
    "print('h(x) = x % 32, counts: {}'.format(Flajolet_Martin_algorithm(stream, lambda x: (x) % 32, 5)))\n",
    "print('h(x) = (2x + 1) % 32, counts: {}'.format(Flajolet_Martin_algorithm(stream, lambda x: (2*x + 1) % 32, 5)))\n",
    "print('h(x) = (3x + 7) % 32, counts: {}'.format(Flajolet_Martin_algorithm(stream, lambda x: (3*x + 7) % 32, 5)))\n",
    "print('h(x) = 4x % 32, counts: {}'.format(Flajolet_Martin_algorithm(stream, lambda x: (4*x + 0) % 32, 5)))        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.axes._subplots.AxesSubplot at 0x109aa5490>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfAAAAFVCAYAAAAQfb27AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHLpJREFUeJzt3X90k/X99/FX+ou2SawU2+3cXyhSj78YZ2wyPR6OQNuD\nymxhTGtswdIjdTA2NnXU2wAd2N4ycuru6Tz8Uo5HduoRGIhM0HEGAuNMxqw667HIVI5UFMSWst5N\nijQ0+f7B19wUaEOzXkk/6fPxV5OrufLOp5c8TZpesQWDwaAAAIBREmI9AAAA6DsCDgCAgQg4AAAG\nIuAAABiIgAMAYCACDgCAgSwP+MmTJzVp0iR9+umn3a7fvXu3iouLVVJSok2bNlk9BgAAcSXJyp37\n/X4tWbJEaWlpF13v8Xj08ssvKzU1VaWlpSooKNCwYcOsHAcAgLhh6TPw2tpalZaWKisrq9v1hw8f\nVk5OjpxOp5KTkzVu3DjV19dbOQoAAHHFsoBv2bJFmZmZuu222yRJ55/wzev1yul0hi7b7Xa1t7db\nNQoAAHHHspfQt2zZIpvNpv379+vQoUNyu91avXq1hg0bJqfTKZ/PF/pen8+njIyMXvcXDAZls9n6\nPMfc//07fXb6f/X5dtF2+42d+tXPZsV6jF599NFHKlv4ktIzsmM9Sq862r5S3fIZuu6662I9Sq9Y\nz/5lwnqylv3r5OcfKs05bMDPadXP3bKAv/jii6Gvy8rKVFNTE/odd25urpqamtTW1qa0tDTV19er\noqKi1/3ZbDY1N/f9WXpXwKaklLTw3xhjp0/7Inp8WVnOiG4XidZWr9IzsuUY+l9Rub//VLTWJVIm\nrWdrq5f17CesZf/paDthxJxS5D/3rCxnj9ssfRPb+YLBoLZv366Ojg65XC653W5VVFQoEAiouLhY\n2dkD+/+gAAAYSKIS8Lq6Oknnnnl/Iz8/X/n5+dG4ewAA4g4ncgEAwEAEHAAAAxFwAAAMRMABADAQ\nAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAM\nRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAA\nAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMlGTVjru6ulRVVaUjR47IZrOpurpa1157bWj7unXr\ntHnzZg0dOlSSVFNTo1GjRlk1DgAAccWygO/Zs0cJCQlav3693nrrLT311FNatWpVaHtjY6Nqa2s1\nevRoq0YAACBuWRbwyZMnKz8/X5L0xRdfKCMjo9v2xsZGrVmzRi0tLcrLy9OcOXOsGgUAgLhjWcAl\nKTExUW63Wzt37tQzzzzTbVthYaFmzpwpu92u+fPna+/evcrLy+t1f1lZzj7PMCQlUTrT55tFnT09\nJaLHJ0W2LpE4dcoRlfvpL9Fal0iZtJ6ZmQ7Ws5+wloOTFT93SwMuSR6PR5WVlXK5XHr99deVmpoq\nSSovL5fDce4gmTRpkg4ePBg24M3N7X2+/zOdXX2+TSz4OjojenxZWc6IbheJ1lZvVO6nv0RrXSJl\n0nq2tnpZz37CWg5Okf7ce4u+Ze9C37p1q5599llJUmpqqmw2m2w2mySpvb1dU6dOVUdHh4LBoA4c\nOKAxY8ZYNQoAAHHHsmfgU6ZMkdvt1v3336+zZ89q8eLF2rlzpzo6OuRyubRgwQLNmjVLKSkpGj9+\nvCZOnGjVKAAAxB3LAp6amqqnn366x+1FRUUqKiqy6u4BAIhrnMgFAAADEXAAAAxEwAEAMBABBwDA\nQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEA\nMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAA\nAAxEwAEAMBABBwDAQAQcAAADEXAAAAxkacC7urq0cOFClZaWasaMGfr444+7bd+9e7eKi4tVUlKi\nTZs2WTkKAABxxdKA79mzRwkJCVq/fr0efvhhPfXUU6Ftfr9fHo9HL7zwgurq6rRx40adPHnSynEA\nAIgblgZ88uTJqqmpkSR98cUXysjICG07fPiwcnJy5HQ6lZycrHHjxqm+vt7KcQAAiBtJVt9BYmKi\n3G63du7cqWeeeSZ0vdfrldPpDF222+1qb2+3ehwAAOKC5QGXJI/Ho8rKSrlcLr3++utKTU2V0+mU\nz+cLfY/P5+v2DP1SsrKcvW6/lCEpidKZPt8s6uzpKRE9PimydYnEqVOOqNxPf4nWukTKpPXMzHSw\nnv2EtRycrPi5WxrwrVu36sSJE5o7d65SU1Nls9lks9kkSbm5uWpqalJbW5vS0tJUX1+vioqKXvfX\n3Nz3Z+hnOrsimj3afB2dET2+rCxnRLeLRGurNyr301+itS6RMmk9W1u9rGc/YS0Hp0h/7r1F39KA\nT5kyRW63W/fff7/Onj2rxYsXa+fOnero6JDL5ZLb7VZFRYUCgYCKi4uVnZ1t5TgAAMQNSwOempqq\np59+usft+fn5ys/Pt3IEAADiEidyAQDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxE\nwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAAD\nEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDA\nQAQcAAADJVm1Y7/fr0WLFunYsWPq7OzUvHnzVFBQENq+bt06bd68WUOHDpUk1dTUaNSoUVaNAwBA\nXLEs4Nu2bVNmZqaefPJJtbW1afr06d0C3tjYqNraWo0ePdqqEQAAiFuWBXzKlCm68847JUmBQECJ\niYndtjc2NmrNmjVqaWlRXl6e5syZY9UoAADEHcsCnp6eLknyer166KGH9Mgjj3TbXlhYqJkzZ8pu\nt2v+/Pnau3ev8vLyrBoHAIC4YlnAJen48eOaP3++Zs6cqcLCwm7bysvL5XA4JEmTJk3SwYMHwwY8\nK8vZ5xmGpCRKZ/p8s6izp6dE9PikyNYlEqdOOaJyP/0lWusSKZPWMzPTwXr2E9ZycLLi525ZwFta\nWjR79mwtXbpUt956a7dt7e3tmjZtml577TWlpaXpwIEDKi4uDrvP5ub2Ps9xprOrz7eJBV9HZ0SP\nLyvLGdHtItHa6o3K/fSXaK1LpExaz9ZWL+vZT1jLwSnSn3tv0bcs4GvWrFF7e7tWrlyplStXSpJc\nLpdOnz4tl8ulBQsWaNasWUpJSdH48eM1ceJEq0YBACDuWBbwqqoqVVVV9bi9qKhIRUVFVt09AABx\njRO5AABgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgA\nAAYKG/Cf/OQn+vOf/yy/3x+NeQAAwGW4rIDv27dPd955p6qrq/X+++9HYy4AANCLsJ9Gdsstt+iW\nW27R119/rR07dugXv/iFHA6H7r33Xs2YMUMpKSnRmBMAAJznsj5O9MCBA/rTn/6k/fv3a+LEibrr\nrrv05ptvat68eXr++eetnhEAAFwgbMDz8/M1fPhw3XPPPVq6dKlSU1MlnXtmfs8991g+IAAAuFjY\ngK9bt052u11XXXWVTp8+raamJo0cOVKJiYnaunVrNGYEAAAXCPsmtr/+9a968MEHJUknT57U3Llz\ntWHDBssHAwAAPQsb8I0bN+qll16SJA0fPlyvvPKKXnzxRcsHAwAAPQsb8LNnzyo5OTl0OTk5WTab\nzdKhAABA78L+Dnzy5MkqLy/XXXfdpWAwqL/85S8qKCiIxmwAAKAHYQNeWVmpHTt26O2331ZSUpLK\ny8s1efLkaMwGAAB6EDbgNptN11xzja666ioFg0FJUn19vW6++WbLhwMAAJcWNuDV1dXas2ePRowY\n0e36uro6y4YCAAC9CxvwN998Uzt27AidwAUAAMRe2HehjxgxQoFAIBqzAACAyxT2GfgVV1yhwsJC\nff/739eQIUNC1y9fvtzSwQAAQM/CBnzChAmaMGFC6G+/g8EgfwcOAECMhQ343XffraNHj+qTTz7R\nbbfdpi+//PKiN7QBAIDoCvs78Ndee00/+9nPtGzZMv373/9WaWkpH2ICAECMhQ342rVrtX79ejkc\nDmVlZWnLli167rnnojEbAADoQdiX0BMSEuRwOEKXs7OzlZiYGHbHfr9fixYt0rFjx9TZ2al58+Z1\nOwXr7t27tWrVKiUlJemee+7RvffeG+FDAABg8Akb8GuvvVZ1dXXy+/368MMP9dJLL+mGG24Iu+Nt\n27YpMzNTTz75pNra2jR9+vRQwP1+vzwej15++WWlpqaqtLRUBQUFGjZs2H/+iAAAGATCBnzJkiVa\nvXq1hgwZokWLFunWW2/VY489FnbHU6ZM0Z133ilJCgQC3Z61Hz58WDk5OXI6nZKkcePGqb6+XlOm\nTIn0cRgt0OVXS/OXOnz44z7f9tQph1pbvRZMdbHPPmuKyv38pwJdZ/Xpp59GbV0iZdJ6mjCrCTOy\nluhPYQNut9tVWVnZ5x2np6dLkrxerx566CE98sgjoW1erzcU72/uo729Pew+s7KcYb/nQkNSEqUz\nfb5ZVHX8v6+0/6hf7z13INaj9Ork5x9q2PAbYz1GWF97T2rJc39XekZ2rEfplUnr+X83tio943is\nR+mVCevJWg5emZmOiBrWm7ABv9TL5dnZ2dq3b1/YnR8/flzz58/XzJkzVVhYGLre6XTK5/OFLvt8\nPmVkZITdX3Nz+Mhf6ExnV59vEwvpGdlyDP2vWI/Rq462E7Ee4bKxnv2L9ew/rOXg1NrqjahhvUU/\nbMAPHToU+trv92vXrl365z//GfZOW1paNHv2bC1dulS33nprt225ublqampSW1ub0tLSVF9fr4qK\nirD7BAAA54QN+PmSk5P1wx/+UKtXrw77vWvWrFF7e7tWrlyplStXSpJcLpdOnz4tl8slt9utiooK\nBQIBFRcXKzt7YL/cCQDAQBI24K+88kro62AwqI8//lgpKSlhd1xVVaWqqqoet+fn5ys/P/8yxwQA\nAOcLG/B//OMf3c59PnToUD311FOWDgUAAHoXNuAejycacwAAgD4IG/CCggLZbDYFg8GLttlsNr3x\nxhuWDAYAAHoWNuBTp05Venq67rvvPiUlJWn79u1655139Nhjj10y6gAAwHphA75v375ub2QrKSnR\nH//4R1111VWWDgYAAHoW9tPIJOlvf/tb6Otdu3bJbrdbNhAAAAgv7DPwJ554Qo8++qhOnjypYDCo\n3Nxc1dbWRmM2AADQg7AB/853vqPXX39dra2tSklJ6fbRogAAIDbCvoT++eef64EHHtB9990nn8+n\nsrIyHT16NBqzAQCAHoQN+NKlSzV79mzZ7XZlZWVp2rRpcrvd0ZgNAAD0IGzAT506pQkTJpz75oQE\n3XvvvZf10Z8AAMA6YQOempqqL7/8MnT57bff1pAhQywdCgAA9C7sm9jcbrfmzJmjo0ePatq0aWpr\na9Pvf//7aMwGAAB6EDbgra2t2rx5s44cOaJAIKDc3NzL+jQyAABgnbAvodfW1iolJUXXXXedbrjh\nBuINAMAAEPYZeE5OjhYuXKixY8eGfvdts9k0ffp0y4cDAACX1mPAT5w4oW9961u68sorJUkNDQ3d\nthNwAABip8eAz507V1u3bpXH49Hzzz+vioqKaM4FAAB6cVkfZrJt2zar5wAAAH1wWQEHAAADCwEH\nAMBAPf4O/JNPPlFBQYEk6auvvgp9LZ17F/obb7xh/XQAAOCSegz4jh07ojkHAADogx4DPnz48GjO\nAQAA+oDfgQMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgSwPeENDg8rKyi66ft26dSoqKlJZ\nWZnKysr06aefWj0KAABxI+zngf8n1q5dq1dffVV2u/2ibY2NjaqtrdXo0aOtHAEAgLhk6TPwkSNH\nasWKFQoGgxdta2xs1Jo1azRjxgw999xzVo4BAEDcsTTgd9xxhxITEy+5rbCwUDU1NfrDH/6gd955\nR3v37rVyFAAA4oqlL6H3pry8XA6HQ5I0adIkHTx4UHl5eb3eJivL2ef7GZKSKJ2JZEIAAPpHZqYj\noob1JiYBb29v17Rp0/Taa68pLS1NBw4cUHFxcdjbNTe39/m+znR2RTIiAAD9prXVG1HDeot+VAJu\ns9kkSdu3b1dHR4dcLpcWLFigWbNmKSUlRePHj9fEiROjMQoAAHHB8oAPHz5cGzZskCQVFRWFri8q\nKup2GQAAXD5O5AIAgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEI\nOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAg\nAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABrI84A0N\nDSorK7vo+t27d6u4uFglJSXatGmT1WMAABBXkqzc+dq1a/Xqq6/Kbrd3u97v98vj8ejll19Wamqq\nSktLVVBQoGHDhlk5DgAAccPSZ+AjR47UihUrFAwGu11/+PBh5eTkyOl0Kjk5WePGjVN9fb2VowAA\nEFcsDfgdd9yhxMTEi673er1yOp2hy3a7Xe3t7VaOAgBAXLH0JfSeOJ1O+Xy+0GWfz6eMjIywt8vK\ncob9ngsNSUmUzvT5ZgAA9JvMTEdEDetNTAKem5urpqYmtbW1KS0tTfX19aqoqAh7u+bmvj9LP9PZ\nFcmIAAD0m9ZWb0QN6y36UQm4zWaTJG3fvl0dHR1yuVxyu92qqKhQIBBQcXGxsrOzozEKAABxwfKA\nDx8+XBs2bJAkFRUVha7Pz89Xfn6+1XcPAEBc4kQuAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIAD\nAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLg\nAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEI\nOAAABiLgAAAYiIADAGAgAg4AgIGSrNpxIBDQ448/ro8++kjJyclatmyZcnJyQtvXrVunzZs3a+jQ\noZKkmpoajRo1yqpxAACIK5YFfNeuXfL7/dqwYYMaGhrk8Xi0atWq0PbGxkbV1tZq9OjRVo0AAEDc\nsizg7777riZMmCBJGjt2rD744INu2xsbG7VmzRq1tLQoLy9Pc+bMsWoUAADijmUB93q9cjgcocuJ\niYkKBAJKSDj3a/fCwkLNnDlTdrtd8+fP1969e5WXl9frPrOynH2eY0hKonSmzzcDAKDfZGY6ImpY\nbywLuMPhkM/nC10+P96SVF5eHgr8pEmTdPDgwbABb25u7/McZzq7+nwbAAD6U2urN6KG9RZ9y96F\nftNNN2nfvn2SpPfee0/XX399aFt7e7umTp2qjo4OBYNBHThwQGPGjLFqFAAA4o5lz8Bvv/12vfnm\nmyopKZEkLV++XNu3b1dHR4dcLpcWLFigWbNmKSUlRePHj9fEiROtGgUAgLhjWcBtNpuqq6u7XXf+\nn4kVFRWpqKjIqrsHACCucSIXAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAA\nAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcA\nwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMAB\nADCQZQEPBAJasmSJSkpKVFZWps8++6zb9t27d6u4uFglJSXatGmTVWMAABCXLAv4rl275Pf7tWHD\nBlVWVsrj8YS2+f1+eTwevfDCC6qrq9PGjRt18uRJq0YBACDuWBbwd999VxMmTJAkjR07Vh988EFo\n2+HDh5WTkyOn06nk5GSNGzdO9fX1Vo0CAEDcSbJqx16vVw6HI3Q5MTFRgUBACQkJ8nq9cjqdoW12\nu13t7e2WzOH3tSpw2mfJvvtLoK1FXydcGesxwjrd3irJFusxwmLO/sWc/ceEGSXm7G8dbV9Zsl/L\nAu5wOOTz/f9wfhNvSXI6nd22+Xw+ZWRkhN1nVpYz7Pdc6A+r/0+fbwMAwEBn2UvoN910k/bt2ydJ\neu+993T99deHtuXm5qqpqUltbW3q7OxUfX29vve971k1CgAAcccWDAaDVuw4GAzq8ccf17/+9S9J\n0vLly9XY2KiOjg65XC7t2bNHK1euVCAQUHFxsWbMmGHFGAAAxCXLAg4AAKzDiVwAADAQAQcAwEAE\nHAAAAxFwAAAMZNnfgfeXQCCgxx9/XB999JGSk5O1bNky5eTkxHqsAeHHP/5x6GQ5I0aM0G9+85sY\nTxQ7DQ0N+u1vf6u6ujo1NTXJ7XYrISFB1157rZYuXSqbbeCf7MEK56/LwYMH9dOf/lQjR46UJJWW\nluquu+6K8YTR5ff7tWjRIh07dkydnZ2aN2+errnmmkF/vFxqXb797W9r7ty5uvrqqyUNzuOlq6tL\nVVVVOnLkiGw2m6qrq5WSkjJgjpcBH/Dzz6ne0NAgj8ejVatWxXqsmDtz5owkqa6uLsaTxN7atWv1\n6quvym63Szr3J4u/+tWvdPPNN2vp0qV64403NHny5BhPGX0XrktjY6MeeOABPfDAAzGeLHa2bdum\nzMxMPfnkk2pra9OPfvQj3XjjjYP+eLnUuvz85z/X7NmzB/XxsmfPHiUkJGj9+vV666239Lvf/U6S\nBszxMuBfQu/tnOqD2aFDh3T69GlVVFSovLxcDQ0NsR4pZkaOHKkVK1bom7+IPHjwoG6++WZJ0sSJ\nE7V///5YjhczF67LBx98oL179+r+++/X4sWLu50NcbCYMmWKfvnLX0o69+peUlISx4suvS6NjY2D\n/niZPHmyampqJElffPGFMjIy1NjYOGCOlwEf8J7OqT7YpaWlqaKiQs8//7yqq6tVWVk5aNfljjvu\nUGJiYujy+ac2SE9Pt+w8+wPdhesyduxYPfbYY3rxxRc1YsQIrVixIobTxUZ6errsdru8Xq8eeugh\nPfzww93+uxmsx8uF6/LII4/ou9/97qA/XqRzzXG73Vq2bJmmTp06oP59GfAB7+2c6oPZ1VdfrWnT\npoW+vvLKK9Xc3BzjqQaG848Pn8+nK664IobTDBy33367Ro8eLencM4sPP/wwxhPFxvHjx1VeXq7p\n06erqKiI4+V/nL8uhYWFHC/n8Xg82rFjh6qqqtTZ2Rm6PtbHy4AvYW/nVB/MtmzZEvqM9RMnTsjr\n9SorKyvGUw0MN954o9566y1J0r59+/SDH/wgxhMNDA8++KDef/99SdLf//53jRkzJsYTRV9LS4tm\nz56tRx99VHfffbckjhfp0uvC8SJt3bpVzz77rCQpNTVVCQkJGjNmzIA5Xgb8qVQvdU71UaNGxXiq\n2Dt79qwWLlyoY8eOSZIeffTRQf2BMJ9//rkqKyu1YcMGHTlyRL/+9a/l9/t1zTXX6Iknnhh07yr+\nxvnrcujQIVVXVyspKUnZ2dmqqakJvcFtsHjiiSe0Y8eObv+GLF68WMuWLRvUx8ul1qWyslIej2dQ\nHy9ff/213G63WlpadPbsWc2ZM0e5ubkD5t+XAR9wAABwsQH/EjoAALgYAQcAwEAEHAAAAxFwAAAM\nRMABADAQAQcAwEAEHAAAA/03ONSNXm3/XKAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10767e590>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# exercise 4.4.2 \n",
    "x = range(1, 33)\n",
    "\n",
    "y = map(lambda x: (2*x + 1) % 32, x)\n",
    "df = pd.DataFrame({'y':y})\n",
    "df.plot(kind='hist', xlim=(0,32), legend=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.axes._subplots.AxesSubplot at 0x109c46450>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfAAAAFVCAYAAAAQfb27AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAG9BJREFUeJzt3X90k/Xd//FXmra0TWKl2G7n3FCkHn8xzthkejwcgbYH\nldnCmNbYgqVH6mBsTHTUY4DO2h4ZOWVnOG9AlOORnXIEBiIDdJyBwDjTMavOeiwylSP1B4otdb2T\nFG1K8v2D73KotA1Vriaf9Pn4q7k+4cq7l5c8SZpesYXD4bAAAIBRkmI9AAAAGDgCDgCAgQg4AAAG\nIuAAABiIgAMAYCACDgCAgSwP+KlTpzRlyhR98MEHPbbv379fJSUlKi0t1datW60eAwCAhJJs5c6D\nwaAefvhhpaenn7fd6/XqueeeU1pamsrKylRYWKgRI0ZYOQ4AAAnD0mfg9fX1KisrU3Z2do/tx44d\nU25urlwul1JSUjRhwgQ1NjZaOQoAAAnFsoBv375dWVlZuummmyRJ517wze/3y+VyRW47HA75fD6r\nRgEAIOFY9hL69u3bZbPZ9Morr+jo0aPyeDx64oknNGLECLlcLgUCgch9A4GAMjMz+93ffcv+oPf+\n7ztWjXtROb46pm1PLYv1GACQsN59912VL3lWGZk5sR4lqs6Oz9WwYpauuuqqi7pfywK+cePGyNfl\n5eWqq6uL/Iw7Ly9PLS0t6ujoUHp6uhobG1VZWdnv/uzJyUpOTe/3PnGjy67W1sF5RSE72zVoj2US\njkvvOC7n45j0Lt6PS3u7XxmZOXIO/59Yj3JB2tv93+h4Zme7+lyz9E1s5wqHw9q9e7c6Ozvldrvl\n8XhUWVmpUCikkpIS5eTE/7+iAACIF4MS8IaGBklnn3n/V0FBgQoKCgbj4QEASDhcyAUAAAMRcAAA\nDETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwA\nAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEH\nAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwULJVOz5z5oyqq6t1/Phx2Ww2\n1dbW6sorr4ysb9iwQdu2bdPw4cMlSXV1dRozZoxV4wAAkFAsC/iBAweUlJSkTZs26dVXX9WqVau0\ndu3ayHpzc7Pq6+s1duxYq0YAACBhWRbwqVOnqqCgQJL0ySefKDMzs8d6c3Oz1q1bp7a2NuXn52ve\nvHlWjQIAQMKxLOCSZLfb5fF4tHfvXj3++OM91oqKijR79mw5HA4tXLhQBw8eVH5+vpXjDJrkZLuy\ns12D9niD+Vgm4bj0juNyPo5J7+L5uHzxhTPWIwxIVpbzoh9PSwMuSV6vV1VVVXK73XrxxReVlpYm\nSaqoqJDTefY/wJQpU3TkyJGECXh39xm1tvoG5bGys12D9lgm4bj0juNyPo5J7+L9uLS3+2M9woC0\nt/u/0fHsL/qWvQt9x44devLJJyVJaWlpstlsstlskiSfz6fp06ers7NT4XBYhw8f1rhx46waBQCA\nhGPZM/Bp06bJ4/Ho7rvvVnd3t5YtW6a9e/eqs7NTbrdbixcv1pw5c5SamqqJEydq8uTJVo0CAEDC\nsSzgaWlpeuyxx/pcLy4uVnFxsVUPDwBAQuNCLgAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBg\nIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAA\nGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgA\nAAYi4AAAGIiAAwBgIEsDfubMGS1ZskRlZWWaNWuW3nvvvR7r+/fvV0lJiUpLS7V161YrRwEAIKFY\nGvADBw4oKSlJmzZt0v33369Vq1ZF1oLBoLxer5555hk1NDRoy5YtOnXqlJXjAACQMCwN+NSpU1VX\nVydJ+uSTT5SZmRlZO3bsmHJzc+VyuZSSkqIJEyaosbHRynEAAEgYyVY/gN1ul8fj0d69e/X4449H\ntvv9frlcrshth8Mhn89n9TiDInSmW8eOvRf9jhfBF1841d7u/8Z/PhgMSpJSUlIu1kiWGcis3/a4\nfFvxelz7Oi7xOm9vLvasVp4rJh/XWP8/FM2HH7bEeoSYszzgkuT1elVVVSW3260XX3xRaWlpcrlc\nCgQCkfsEAoEez9BN9tXp/9OilTuVkZkT61GiOvXxO0p3jWDWi8ykWSWz5mVWa5g0q3R23hEjr431\nGBcsK8up7GxX9DsOgKUB37Fjh06ePKn58+crLS1NNptNNptNkpSXl6eWlhZ1dHQoPT1djY2Nqqys\ntHKcQdPdfUYZmTlyDv+fWI8SVWfHSWa1gEmzSmbNy6zWMGlW6ey8Jmlv96u1deCvMvcXfUsDPm3a\nNHk8Ht19993q7u7WsmXLtHfvXnV2dsrtdsvj8aiyslKhUEglJSXKyTHjX34AAMSapQFPS0vTY489\n1ud6QUGBCgoKrBwBAICExIVcAAAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAA\nDETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwA\nAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEH\nAMBAyVbtOBgMaunSpTpx4oS6urq0YMECFRYWRtY3bNigbdu2afjw4ZKkuro6jRkzxqpxAABIKJYF\nfNeuXcrKytLKlSvV0dGhmTNn9gh4c3Oz6uvrNXbsWKtGAAAgYVkW8GnTpunWW2+VJIVCIdnt9h7r\nzc3NWrdundra2pSfn6958+ZZNQoAAAnHsoBnZGRIkvx+vxYtWqQHHnigx3pRUZFmz54th8OhhQsX\n6uDBg8rPz7dqHAAAEoplAZekTz/9VAsXLtTs2bNVVFTUY62iokJOp1OSNGXKFB05ciRhAp6cbFdX\nrIcAAMSNrCynsrNdF3WflgW8ra1Nc+fOVU1NjW688cYeaz6fTzNmzNALL7yg9PR0HT58WCUlJVaN\nMui6u89Iw2I9BQAgXrS3+9Xa6hvwn+sv+pYFfN26dfL5fFqzZo3WrFkjSXK73Tp9+rTcbrcWL16s\nOXPmKDU1VRMnTtTkyZOtGgUAgIRjWcCrq6tVXV3d53pxcbGKi4utengAABIaF3IBAMBABBwAAAMR\ncAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADBQ14D/72c/0l7/8\nRcFgcDDmAQAAF+CCAn7o0CHdeuutqq2t1VtvvTUYcwEAgH5E/TSyG264QTfccIO+/PJL7dmzR7/6\n1a/kdDp15513atasWUpNTR2MOQEAwDku6ONEDx8+rD//+c965ZVXNHnyZN122216+eWXtWDBAj39\n9NNWzwgAAL4masALCgo0cuRI3XHHHaqpqVFaWpqks8/M77jjDssHBAAA54sa8A0bNsjhcOiyyy7T\n6dOn1dLSotGjR8tut2vHjh2DMSMAAPiaqG9i+9vf/qZ7771XknTq1CnNnz9fmzdvtnwwAADQt6gB\n37Jli5599llJ0siRI/X8889r48aNlg8GAAD6FjXg3d3dSklJidxOSUmRzWazdCgAANC/qD8Dnzp1\nqioqKnTbbbcpHA7rr3/9qwoLCwdjNgAA0IeoAa+qqtKePXv02muvKTk5WRUVFZo6depgzAYAAPoQ\nNeA2m01XXHGFLrvsMoXDYUlSY2Ojrr/+esuHAwAAvYsa8NraWh04cECjRo3qsb2hocGyoQAAQP+i\nBvzll1/Wnj17IhdwAQAAsRf1XeijRo1SKBQajFkAAMAFivoM/JJLLlFRUZF++MMfatiwYZHtK1as\nsHQwAADQt6gBnzRpkiZNmhT53e9wOMzvgQMAEGNRA3777bfro48+0vvvv6+bbrpJn3322XlvaAMA\nAIMr6s/AX3jhBf3iF7/Q8uXL9Z///EdlZWV8iAkAADEWNeDr16/Xpk2b5HQ6lZ2dre3bt+upp54a\njNkAAEAfor6EnpSUJKfTGbmdk5Mju90edcfBYFBLly7ViRMn1NXVpQULFvS4BOv+/fu1du1aJScn\n64477tCdd975Db8FAACGnqgBv/LKK9XQ0KBgMKh33nlHzz77rK655pqoO961a5eysrK0cuVKdXR0\naObMmZGAB4NBeb1ePffcc0pLS1NZWZkKCws1YsSIb/8dAQAwBER9Cf3hhx/WyZMnNWzYMC1dulRO\np1M1NTVRdzxt2jTdd999kqRQKNTjWfuxY8eUm5srl8ullJQUTZgwQY2Njd/i2wAAYGiJ+gzc4XCo\nqqpqwDvOyMiQJPn9fi1atEgPPPBAZM3v98vlcvV4DJ/PN+DHiFfJyXZ1xXoIAEDcyMpyKjvbFf2O\nAxA14L29XJ6Tk6NDhw5F3fmnn36qhQsXavbs2SoqKopsd7lcCgQCkduBQECZmZkXOnPc6+4+Iw2L\nfj8AwNDQ3u5Xa+vAn6j2F/2oAT969Gjk62AwqH379ulf//pX1Adta2vT3LlzVVNToxtvvLHHWl5e\nnlpaWtTR0aH09HQ1NjaqsrIy6j4BAMBZUQN+rpSUFP34xz/WE088EfW+69atk8/n05o1a7RmzRpJ\nktvt1unTp+V2u+XxeFRZWalQKKSSkhLl5OR8s+8AAIAhKGrAn3/++cjX4XBY7733nlJTU6PuuLq6\nWtXV1X2uFxQUqKCg4ALHBAAA54oa8H/+8589rn0+fPhwrVq1ytKhAABA/6IG3Ov1DsYcAABgAKIG\nvLCwUDabTeFw+Lw1m82ml156yZLBAABA36IGfPr06crIyNBdd92l5ORk7d69W6+//roeeuihXqMO\nAACsFzXghw4d6vFGttLSUv3pT3/SZZddZulgAACgb1EvpSpJf//73yNf79u3Tw6Hw7KBAABAdFGf\ngT/66KN68MEHderUKYXDYeXl5am+vn4wZgMAAH2IGvDvfe97evHFF9Xe3q7U1NQeHy0KAABiI+pL\n6B9//LHuuece3XXXXQoEAiovL9dHH300GLMBAIA+RA14TU2N5s6dK4fDoezsbM2YMUMej2cwZgMA\nAH2IGvAvvvhCkyZNOnvnpCTdeeedCfXRnwAAmChqwNPS0vTZZ59Fbr/22msaNozPygQAIJaivonN\n4/Fo3rx5+uijjzRjxgx1dHToD3/4w2DMBgAA+hA14O3t7dq2bZuOHz+uUCikvLy8C/o0MgAAYJ2o\nL6HX19crNTVVV111la655hriDQBAHIj6DDw3N1dLlizR+PHjIz/7ttlsmjlzpuXDAQCA3vUZ8JMn\nT+o73/mOLr30UklSU1NTj3UCDgBA7PQZ8Pnz52vHjh3yer16+umnVVlZOZhzAQCAflzQh5ns2rXL\n6jkAAMAAXFDAAQBAfCHgAAAYqM+fgb///vsqLCyUJH3++eeRr6Wz70J/6aWXrJ8OAAD0qs+A79mz\nZzDnAAAAA9BnwEeOHDmYcwAAgAHgZ+AAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCDLA97U\n1KTy8vLztm/YsEHFxcUqLy9XeXm5PvjgA6tHAQAgYUT9PPBvY/369dq5c6ccDsd5a83Nzaqvr9fY\nsWOtHAEAgIRk6TPw0aNHa/Xq1QqHw+etNTc3a926dZo1a5aeeuopK8cAACDhWBrwW265RXa7vde1\noqIi1dXV6Y9//KNef/11HTx40MpRAABIKJa+hN6fiooKOZ1OSdKUKVN05MgR5efnx2qciyo52a6u\nWA8BAIgbWVlOZWe7Luo+YxJwn8+nGTNm6IUXXlB6eroOHz6skpKSWIxiie7uM9KwWE8BAIgX7e1+\ntbb6Bvzn+ov+oATcZrNJknbv3q3Ozk653W4tXrxYc+bMUWpqqiZOnKjJkycPxigAACQEywM+cuRI\nbd68WZJUXFwc2V5cXNzjNgAAuHBcyAUAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAw\nEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAA\nDETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwAAAMRcAAADETAAQAwEAEHAMBABBwA\nAAMRcAAADGR5wJuamlReXn7e9v3796ukpESlpaXaunWr1WMAAJBQkq3c+fr167Vz5045HI4e24PB\noLxer5577jmlpaWprKxMhYWFGjFihJXjAACQMCx9Bj569GitXr1a4XC4x/Zjx44pNzdXLpdLKSkp\nmjBhghobG60cBQCAhGJpwG+55RbZ7fbztvv9frlcrshth8Mhn89n5SgAACQUS19C74vL5VIgEIjc\nDgQCyszMjMUolkhOtqsr1kMAAOJGVpZT2dmu6HccgJgEPC8vTy0tLero6FB6eroaGxtVWVkZi1Es\n0d19RhoW6ykAAPGivd2v1taBv9LcX/QHJeA2m02StHv3bnV2dsrtdsvj8aiyslKhUEglJSXKyckZ\njFEAAEgIlgd85MiR2rx5sySpuLg4sr2goEAFBQVWPzwAAAmJC7kAAGAgAg4AgIEIOAAABiLgAAAY\niIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAA\nBiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4A\ngIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABkq2asehUEiPPPKI3n33XaWkpGj58uXKzc2NrG/Y\nsEHbtm3T8OHDJUl1dXUaM2aMVeMAAJBQLAv4vn37FAwGtXnzZjU1Ncnr9Wrt2rWR9ebmZtXX12vs\n2LFWjQAAQMKyLOBvvPGGJk2aJEkaP3683n777R7rzc3NWrdundra2pSfn6958+ZZNQoAAAnHsoD7\n/X45nc7IbbvdrlAopKSksz92Lyoq0uzZs+VwOLRw4UIdPHhQ+fn5Vo0zqJKT7eqK9RAAgLiRleVU\ndrbrou7TsoA7nU4FAoHI7XPjLUkVFRWRwE+ZMkVHjhxJmIB3d5+RhsV6CgBAvGhv96u11TfgP9df\n9C17F/p1112nQ4cOSZLefPNNXX311ZE1n8+n6dOnq7OzU+FwWIcPH9a4ceOsGgUAgIRj2TPwm2++\nWS+//LJKS0slSStWrNDu3bvV2dkpt9utxYsXa86cOUpNTdXEiRM1efJkq0YBACDhWBZwm82m2tra\nHtvO/TWx4uJiFRcXW/XwAAAkNC7kAgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiI\ngAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAG\nIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCA\ngQg4AAAGsizgoVBIDz/8sEpLS1VeXq4PP/ywx/r+/ftVUlKi0tJSbd261aoxAABISJYFfN++fQoG\ng9q8ebOqqqrk9Xoja8FgUF6vV88884waGhq0ZcsWnTp1yqpRAABIOJYF/I033tCkSZMkSePHj9fb\nb78dWTt27Jhyc3PlcrmUkpKiCRMmqLGx0apRAABIOMlW7djv98vpdEZu2+12hUIhJSUlye/3y+Vy\nRdYcDod8Pl+/++s+3aHQqS+sGvei6vK3qrPbFf2OceC0r12SLdZjXBBmtY5J8zKrNUyaVTJr3s6O\nzy3Zr2UBdzqdCgQCkdv/jbckuVyuHmuBQECZmZn97u9/65daMygAAAay7CX06667TocOHZIkvfnm\nm7r66qsja3l5eWppaVFHR4e6urrU2NioH/zgB1aNAgBAwrGFw+GwFTsOh8N65JFH9O9//1uStGLF\nCjU3N6uzs1Nut1sHDhzQmjVrFAqFVFJSolmzZlkxBgAACcmygAMAAOtwIRcAAAxEwAEAMBABBwDA\nQAQcAAADWfZ74BdLKBTSI488onfffVcpKSlavny5cnNzYz1WXPjpT38auVjOqFGj9Nvf/jbGE8VO\nU1OTfve736mhoUEtLS3yeDxKSkrSlVdeqZqaGtlsZlzw4WI797gcOXJEP//5zzV69GhJUllZmW67\n7bYYTzi4gsGgli5dqhMnTqirq0sLFizQFVdcMeTPl96Oy3e/+13Nnz9fl19+uaSheb6cOXNG1dXV\nOn78uGw2m2pra5Wamho350vcB/zca6o3NTXJ6/Vq7dq1sR4r5r766itJUkNDQ4wnib3169dr586d\ncjgcks7+yuKvf/1rXX/99aqpqdFLL72kqVOnxnjKwff149Lc3Kx77rlH99xzT4wni51du3YpKytL\nK1euVEdHh37yk5/o2muvHfLnS2/H5Ze//KXmzp07pM+XAwcOKCkpSZs2bdKrr76q3//+95IUN+dL\n3L+E3t811Yeyo0eP6vTp06qsrFRFRYWamppiPVLMjB49WqtXr9Z/fyPyyJEjuv766yVJkydP1iuv\nvBLL8WLm68fl7bff1sGDB3X33Xdr2bJlPa6GOFRMmzZN9913n6Szr+4lJydzvqj349Lc3Dzkz5ep\nU6eqrq5OkvTJJ58oMzNTzc3NcXO+xH3A+7qm+lCXnp6uyspKPf3006qtrVVVVdWQPS633HKL7HZ7\n5Pa5lzbIyMiIep39RPX14zJ+/Hg99NBD2rhxo0aNGqXVq1fHcLrYyMjIkMPhkN/v16JFi3T//ff3\n+P9mqJ4vXz8uDzzwgL7//e8P+fNFOtscj8ej5cuXa/r06XH190vcB7y/a6oPZZdffrlmzJgR+frS\nSy9Va2trjKeKD+eeH4FAQJdcckkMp4kfN998s8aOHSvp7DOLd955J8YTxcann36qiooKzZw5U8XF\nxZwv/9+5x6WoqIjz5Rxer1d79uxRdXW1urq6Ittjfb7EfQn7u6b6ULZ9+/bIZ6yfPHlSfr9f2dnZ\nMZ4qPlx77bV69dVXJUmHDh3Sj370oxhPFB/uvfdevfXWW5Kkf/zjHxo3blyMJxp8bW1tmjt3rh58\n8EHdfvvtkjhfpN6PC+eLtGPHDj355JOSpLS0NCUlJWncuHFxc77E/aVUe7um+pgxY2I8Vex1d3dr\nyZIlOnHihCTpwQcfHNIfCPPxxx+rqqpKmzdv1vHjx/Wb3/xGwWBQV1xxhR599NEh967i/zr3uBw9\nelS1tbVKTk5WTk6O6urqIm9wGyoeffRR7dmzp8ffIcuWLdPy5cuH9PnS23GpqqqS1+sd0ufLl19+\nKY/Ho7a2NnV3d2vevHnKy8uLm79f4j7gAADgfHH/EjoAADgfAQcAwEAEHAAAAxFwAAAMRMABADAQ\nAQcAwEAEHAAAA/0/88vm4ZunZDcAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x109a35f10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "y = map(lambda x: (3*x + 7) % 32, x)\n",
    "df = pd.DataFrame({'y' : y})\n",
    "df.plot(kind='hist', xlim=(0,32), legend=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.axes._subplots.AxesSubplot at 0x10a107d90>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfAAAAFVCAYAAAAQfb27AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHMVJREFUeJzt3X90k/X99/FX+suWJFaK6XbODUXq8RfjjE2mx8MRaHtQ\nmS2MaY0tWHqkDsbG/DHqMUBnbY98yak703kDohyP7NQjOBCZoOMMBMaZjll11mORqRypP1BsSddv\nksKamtx/cC+HCiVIejX5pM/HX02u7MqbXJ/ladL0ii0SiUQEAACMkpboAQAAwLdHwAEAMBABBwDA\nQAQcAAADEXAAAAxEwAEAMJDlAT927JimTZumjz/+uN/1u3fvVnl5uSoqKrRp0yarxwAAIKVkWLnz\nUCikBx98UDk5Oadd7/V69cILLyg7O1uVlZUqKSnRqFGjrBwHAICUYekr8KamJlVWVsrlcvW7/tCh\nQyooKJDT6VRmZqYmTZqklpYWK0cBACClWBbwLVu2KC8vT9dff70k6dQTvgUCATmdzuhlu90uv99v\n1SgAAKQcy95C37Jli2w2m15//XUdPHhQHo9HTzzxhEaNGiWn06lgMBi9bTAYVG5u7ln3d/fy3+vD\n//2OVePGZWTvuzrUmaURufmJHuU0xz57XznOUUk5W0/3V2peOUeXX355okc5zQcffKCqpc8l5ePG\nMT0/HNPzk8yzJfN6GwqWBfzZZ5+N/lxVVaXGxsbo77gLCwvV3t6u7u5u5eTkqKWlRTU1NWfdX3pG\nhjKycs56m0QJH5dG5ObLMfL/JHqU0/R0H03a2STJ5wuoo2Pw331xuZxx7dfnCyTt4zZcj2m8OKbn\nJ5lnk4Z+vcX73HI+9zcQSz/EdqpIJKLt27erp6dHbrdbHo9HNTU1CofDKi8vV35+8v3XHQAAyWpI\nAt7c3Czp5Cvv/youLlZxcfFQ3D0AACmHE7kAAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEI\nOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAg\nAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAYiIADAGAgAg4AgIEIOAAABiLgAAAY\niIADAGAgAg4AgIEIOAAABsqwasdff/216urqdPjwYdlsNjU0NOiyyy6Lbl+/fr02b96skSNHSpIa\nGxs1btw4q8YBACClWBbwPXv2KC0tTRs2bNAbb7yhRx99VGvWrIlub2trU1NTk8aPH2/VCAAApCzL\nAj59+nQVFxdLkj7//HPl5ub2297W1qa1a9eqs7NTRUVFWrBggVWjAACQciwLuCSlp6fL4/Fo586d\nevzxx/ttKy0t1dy5c2W327V48WLt3btXRUVFVo5jmcysDOlEoqcwU16eQy6X05J9x7Pfri7HIE4y\nvFh5TOPBMU1NiVhvybK+LQ24JHm9XtXW1srtduuVV15Rdna2JKm6uloOx8n/Q02bNk0HDhwwNuCh\n3r5Ej2Asny+gjg7/oO/X5XLGtV+fLzCI0wwvVh3TeHFMU9NQr7d4n1vO5/4GYtmn0Ldu3aonn3xS\nkpSdnS2bzSabzSZJ8vv9mjlzpnp6ehSJRLR//35NmDDBqlEAAEg5lr0CnzFjhjwej+644w719fVp\n+fLl2rlzp3p6euR2u7VkyRLNmzdPWVlZmjx5sqZOnWrVKAAApBzLAp6dna3HHntswO1lZWUqKyuz\n6u4BAEhpnMgFAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAA\nAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQc\nAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxkacC//vpr\nLV26VJWVlZozZ44+/PDDftt3796t8vJyVVRUaNOmTVaOAgBASrE04Hv27FFaWpo2bNige++9V48+\n+mh0WygUktfr1TPPPKPm5mY9//zzOnbsmJXjAACQMiwN+PTp09XY2ChJ+vzzz5WbmxvddujQIRUU\nFMjpdCozM1OTJk1SS0uLleMAAJAyMqy+g/T0dHk8Hu3cuVOPP/549PpAICCn0xm9bLfb5ff7rR4H\nAICUYHnAJcnr9aq2tlZut1uvvPKKsrOz5XQ6FQwGo7cJBoP9XqGbJDMrQzqR6CnMlJfnkMvljH3D\n8xDPfru6HIM4yfBi5TGNB8c0NSVivSXL+rY04Fu3btXRo0e1cOFCZWdny2azyWazSZIKCwvV3t6u\n7u5u5eTkqKWlRTU1NVaOY5lQb1+iRzCWzxdQR8fgv/Picjnj2q/PFxjEaYYXq45pvDimqWmo11u8\nzy3nc38DsTTgM2bMkMfj0R133KG+vj4tX75cO3fuVE9Pj9xutzwej2pqahQOh1VeXq78/HwrxwEA\nIGVYGvDs7Gw99thjA24vLi5WcXGxlSMAAJCSOJELAAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAA\nABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4\nAAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCAC\nDgCAgQg4AAAGIuAAABgow6odh0IhLVu2TEeOHFFvb68WLVqkkpKS6Pb169dr8+bNGjlypCSpsbFR\n48aNs2ocAABSimUB37Ztm/Ly8vTII4+ou7tbs2fP7hfwtrY2NTU1afz48VaNAABAyrIs4DNmzNBN\nN90kSQqHw0pPT++3va2tTWvXrlVnZ6eKioq0YMECq0YBACDlWBbwESNGSJICgYDuuece3Xffff22\nl5aWau7cubLb7Vq8eLH27t2roqIiq8YBACClWBZwSfriiy+0ePFizZ07V6Wlpf22VVdXy+FwSJKm\nTZumAwcOGBvwzKwM6USipzBTXp5DLpfTkn3Hs9+uLscgTjK8WHlM48ExTU2JWG/Jsr4tC3hnZ6fm\nz5+v+vp6XXfddf22+f1+zZo1Sy+//LJycnK0f/9+lZeXWzWK5UK9fYkewVg+X0AdHf5B36/L5Yxr\nvz5fYBCnGV6sOqbx4pimpqFeb/E+t5zP/Q3EsoCvXbtWfr9fq1ev1urVqyVJbrdbx48fl9vt1pIl\nSzRv3jxlZWVp8uTJmjp1qlWjAACQciwLeF1dnerq6gbcXlZWprKyMqvuHgCAlMaJXAAAMBABBwDA\nQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAxEwAEAMBABBwDAQAQcAAADxQz4z372M/35\nz39WKBQainkAAMA5OKeA79u3TzfddJMaGhr07rvvDsVcAADgLGJ+G9m1116ra6+9VidOnNCOHTv0\nq1/9Sg6HQ7fddpvmzJmjrKysoZgTAACc4py+TnT//v3605/+pNdff11Tp07VzTffrNdee02LFi3S\n008/bfWMAADgG2IGvLi4WKNHj9att96q+vp6ZWdnSzr5yvzWW2+1fEAAAHC6mAFfv3697Ha7Lr74\nYh0/flzt7e0aO3as0tPTtXXr1qGYEQAAfEPMD7H99a9/1V133SVJOnbsmBYuXKiNGzdaPhgAABhY\nzIA///zzeu655yRJo0eP1osvvqhnn33W8sEAAMDAYga8r69PmZmZ0cuZmZmy2WyWDgUAAM4u5u/A\np0+frurqat18882KRCL6y1/+opKSkqGYDQAADCBmwGtra7Vjxw69+eabysjIUHV1taZPnz4UswEA\ngAHEDLjNZtOll16qiy++WJFIRJLU0tKia665xvLhAADAmcUMeENDg/bs2aMxY8b0u765udmyoQAA\nwNnFDPhrr72mHTt2RE/gAgAAEi/mp9DHjBmjcDg8FLMAAIBzFPMV+IUXXqjS0lL98Ic/1AUXXBC9\nfuXKlZYOBgAABhYz4FOmTNGUKVOif/sdiUT4O3AAABIsZsBvueUWffrpp/roo490/fXX68svvzzt\nA20AAGBoxfwd+Msvv6xf/OIXWrFihf7973+rsrKSLzEBACDBYgZ83bp12rBhgxwOh1wul7Zs2aKn\nnnpqKGYDAAADiPkWelpamhwOR/Ryfn6+0tPTY+44FApp2bJlOnLkiHp7e7Vo0aJ+p2DdvXu31qxZ\no4yMDN1666267bbbzvOfAADA8BMz4Jdddpmam5sVCoX0/vvv67nnntOVV14Zc8fbtm1TXl6eHnnk\nEXV3d2v27NnRgIdCIXm9Xr3wwgvKzs5WZWWlSkpKNGrUqPj/RQAADAMx30J/8MEHdfToUV1wwQVa\ntmyZHA6H6uvrY+54xowZuvvuuyVJ4XC436v2Q4cOqaCgQE6nU5mZmZo0aZJaWlri+GcAADC8xHwF\nbrfbVVtb+613PGLECElSIBDQPffco/vuuy+6LRAIyOl09rsPv9//re8jWWRmZUgnEj2FmfLyHHK5\nnLFveB7i2W9XlyP2jXBGVh7TeHBMU1Mi1luyrO+YAT/T2+X5+fnat29fzJ1/8cUXWrx4sebOnavS\n0tLo9U6nU8FgMHo5GAwqNzf3XGdOOqHevkSPYCyfL6COjsH/jzeXyxnXfn2+wCBOM7xYdUzjxTFN\nTUO93uJ9bjmf+xtIzIAfPHgw+nMoFNKuXbv0z3/+M+addnZ2av78+aqvr9d1113Xb1thYaHa29vV\n3d2tnJwctbS0qKamJuY+AQDASTEDfqrMzEz9+Mc/1hNPPBHztmvXrpXf79fq1au1evVqSZLb7dbx\n48fldrvl8XhUU1OjcDis8vJy5efnn9+/AACAYShmwF988cXoz5FIRB9++KGysrJi7riurk51dXUD\nbi8uLlZxcfE5jgkAAE4VM+D/+Mc/+p37fOTIkXr00UctHQoAAJxdzIB7vd6hmAMAAHwLMQNeUlIi\nm82mSCRy2jabzaZXX33VksEAAMDAYgZ85syZGjFihG6//XZlZGRo+/bteuutt/TAAw+cMeoAAMB6\nMQO+b9++fh9kq6io0B//+EddfPHFlg4GAAAGFvNUqpL0t7/9Lfrzrl27ZLfbLRsIAADEFvMV+MMP\nP6z7779fx44dUyQSUWFhoZqamoZiNgAAMICYAf/e976nV155RT6fT1lZWf2+WhQAACRGzLfQP/vs\nM9155526/fbbFQwGVVVVpU8//XQoZgMAAAOIGfD6+nrNnz9fdrtdLpdLs2bNksfjGYrZAADAAGIG\nvKurS1OmTDl547Q03XbbbUZ/9ScAAKkgZsCzs7P15ZdfRi+/+eabuuCCCywdCgAAnF3MD7F5PB4t\nWLBAn376qWbNmqXu7m79/ve/H4rZAADAAGIG3OfzafPmzTp8+LDC4bAKCwvP6dvIAACAdWK+hd7U\n1KSsrCxdfvnluvLKK4k3AABJIOYr8IKCAi1dulQTJ06M/u7bZrNp9uzZlg8HAADObMCAHz16VN/5\nznd00UUXSZJaW1v7bSfgAAAkzoABX7hwobZu3Sqv16unn35aNTU1QzkXAAA4i3P6MpNt27ZZPQcA\nAPgWzingAAAguRBwAAAMNODvwD/66COVlJRIkr766qvoz9LJT6G/+uqr1k8HAADOaMCA79ixYyjn\nAAAA38KAAR89evRQzgEAAL4FfgcOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAayPOCtra2q\nqqo67fr169errKxMVVVVqqqq0scff2z1KAAApIyY3wcej3Xr1umll16S3W4/bVtbW5uampo0fvx4\nK0cAACAlWfoKfOzYsVq1apUikchp29ra2rR27VrNmTNHTz31lJVjAACQciwN+I033qj09PQzbist\nLVVjY6P+8Ic/6K233tLevXutHAUAgJRi6VvoZ1NdXS2HwyFJmjZtmg4cOKCioqJEjROXzKwM6USi\npzBTXp5DLpfTkn3Hs9+uLscgTjK8WHlM48ExTU2JWG/Jsr4TEnC/369Zs2bp5ZdfVk5Ojvbv36/y\n8vJEjDIoQr19iR7BWD5fQB0d/kHfr8vljGu/Pl9gEKcZXqw6pvHimKamoV5v8T63nM/9DWRIAm6z\n2SRJ27dvV09Pj9xut5YsWaJ58+YpKytLkydP1tSpU4diFAAAUoLlAR89erQ2btwoSSorK4teX1ZW\n1u8yAAA4d5zIBQAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFw\nAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAE\nHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMRMABADAQAQcAwEAEHAAAAxFwAAAMZHnAW1tb\nVVVVddr1u3fvVnl5uSoqKrRp0yarxwAAIKVkWLnzdevW6aWXXpLdbu93fSgUktfr1QsvvKDs7GxV\nVlaqpKREo0aNsnIcAABShqWvwMeOHatVq1YpEon0u/7QoUMqKCiQ0+lUZmamJk2apJaWFitHAQAg\npVga8BtvvFHp6emnXR8IBOR0OqOX7Xa7/H6/laMAAJBSLH0LfSBOp1PBYDB6ORgMKjc3NxGjDIrM\nrAzpRKKnMFNenkMulzP2Dc9DPPvt6nIM4iTDi5XHNB4c09SUiPWWLOs7IQEvLCxUe3u7uru7lZOT\no5aWFtXU1CRilEER6u1L9AjG8vkC6ugY/HdfXC5nXPv1+QKDOM3wYtUxjRfHNDUN9XqL97nlfO5v\nIEMScJvNJknavn27enp65Ha75fF4VFNTo3A4rPLycuXn5w/FKAAApATLAz569Ght3LhRklRWVha9\nvri4WMXFxVbfPQAAKYkTuQAAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiI\ngAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAG\nIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCAgQg4AAAGIuAAABiIgAMAYCACDgCA\ngQg4AAAGyrBqx+FwWA899JA++OADZWZmasWKFSooKIhuX79+vTZv3qyRI0dKkhobGzVu3DirxgEA\nIKVYFvBdu3YpFApp48aNam1tldfr1Zo1a6Lb29ra1NTUpPHjx1s1AgAAKcuygL/99tuaMmWKJGni\nxIl67733+m1va2vT2rVr1dnZqaKiIi1YsMCqUQAASDmWBTwQCMjhcEQvp6enKxwOKy3t5K/dS0tL\nNXfuXNntdi1evFh79+5VUVGRVeNYKjMrQzqR6CnMlJfnkMvltGTf8ey3q8sR+0Y4IyuPaTw4pqkp\nEestWda3ZQF3OBwKBoPRy6fGW5Kqq6ujgZ82bZoOHDhgbMBDvX2JHsFYPl9AHR3+Qd+vy+WMa78+\nX2AQpxlerDqm8eKYpqahXm/xPrecz/0NxLJPoV999dXat2+fJOmdd97RFVdcEd3m9/s1c+ZM9fT0\nKBKJaP/+/ZowYYJVowAAkHIsewV+ww036LXXXlNFRYUkaeXKldq+fbt6enrkdru1ZMkSzZs3T1lZ\nWZo8ebKmTp1q1SgAAKQcywJus9nU0NDQ77pT/0ysrKxMZWVlVt09AAApjRO5AABgIAIOAICBCDgA\nAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIO\nAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBCDgAAAYi4AAAGIiA\nAwBgIAIOAICBCDgAAAYi4AAAGIiAAwBgIAIOAICBLAt4OBzWgw8+qIqKClVVVemTTz7pt3337t0q\nLy9XRUWFNm3aZNUYAACkJMsCvmvXLoVCIW3cuFG1tbXyer3RbaFQSF6vV88884yam5v1/PPP69ix\nY1aNAgBAyrEs4G+//bamTJkiSZo4caLee++96LZDhw6poKBATqdTmZmZmjRpklpaWqwaBQCAlJNh\n1Y4DgYAcDkf0cnp6usLhsNLS0hQIBOR0OqPb7Ha7/H7/WffXd7xb4WNdVo0bl1Df/6rn+FeJHuOM\njvt9kmyJHuOMerq/0ieftFuy764uh3y+wHn/7z/5pF093RzTb8vKYxovjun5SebZkvV4DhXLAu5w\nOBQMBqOX/xtvSXI6nf22BYNB5ebmnnV//7dpmTWDAmdw3XVXy+3+aaLHwCDimGKwuFzO2DcaApa9\nhX711Vdr3759kqR33nlHV1xxRXRbYWGh2tvb1d3drd7eXrW0tOgHP/iBVaMAAJBybJFIJGLFjiOR\niB566CH961//kiStXLlSbW1t6unpkdvt1p49e7R69WqFw2GVl5drzpw5VowBAEBKsizgAADAOpzI\nBQAAAxFwAAAMRMABADAQAQcAwECW/R34YAmHw3rooYf0wQcfKDMzUytWrFBBQUGix0oKP/3pT6Mn\nyxkzZoz+53/+J8ETJU5ra6t++9vfqrm5We3t7fJ4PEpLS9Nll12m+vp62WzJeSIKq536uBw4cEA/\n//nPNXbsWElSZWWlbr755gRPOLRCoZCWLVumI0eOqLe3V4sWLdKll1467NfLmR6X7373u1q4cKEu\nueQSScNzvXz99deqq6vT4cOHZbPZ1NDQoKysrKRZL0kf8FPPqd7a2iqv16s1a9YkeqyE+89//iNJ\nam5uTvAkibdu3Tq99NJLstvtkk7+yeKvf/1rXXPNNaqvr9err76q6dOnJ3jKoffNx6WtrU133nmn\n7rzzzgRPljjbtm1TXl6eHnnkEXV3d+snP/mJrrrqqmG/Xs70uPzyl7/U/Pnzh/V62bNnj9LS0rRh\nwwa98cYb+t3vfidJSbNekv4t9LOdU304O3jwoI4fP66amhpVV1ertbU10SMlzNixY7Vq1Sr99y8i\nDxw4oGuuuUaSNHXqVL3++uuJHC9hvvm4vPfee9q7d6/uuOMOLV++vN/ZEIeLGTNm6O6775Z08t29\njIwM1ovO/Li0tbUN+/Uyffp0NTY2SpI+//xz5ebmqq2tLWnWS9IHfKBzqg93OTk5qqmp0dNPP62G\nhgbV1tYO28flxhtvVHp6evTyqac2GDFiRMzz7Keqbz4uEydO1AMPPKBnn31WY8aM0apVqxI4XWKM\nGDFCdrtdgUBA99xzj+69995+/78Zruvlm4/Lfffdp+9///vDfr1IJ5vj8Xi0YsUKzZw5M6meX5I+\n4Gc7p/pwdskll2jWrFnRny+66CJ1dHQkeKrkcOr6CAaDuvDCCxM4TfK44YYbNH78eEknX1m8//77\nCZ4oMb744gtVV1dr9uzZKisrY738f6c+LqWlpayXU3i9Xu3YsUN1dXXq7e2NXp/o9ZL0JTzbOdWH\nsy1btkS/Y/3o0aMKBAJyuVwJnio5XHXVVXrjjTckSfv27dOPfvSjBE+UHO666y69++67kqS///3v\nmjBhQoInGnqdnZ2aP3++7r//ft1yyy2SWC/SmR8X1ou0detWPfnkk5Kk7OxspaWlacKECUmzXpL+\nVKpnOqf6uHHjEjxV4vX19Wnp0qU6cuSIJOn+++8f1l8I89lnn6m2tlYbN27U4cOH9Zvf/EahUEiX\nXnqpHn744WH3qeL/OvVxOXjwoBoaGpSRkaH8/Hw1NjZGP+A2XDz88MPasWNHv+eQ5cuXa8WKFcN6\nvZzpcamtrZXX6x3W6+XEiRPyeDzq7OxUX1+fFixYoMLCwqR5fkn6gAMAgNMl/VvoAADgdAQcAAAD\nEXAAAAxEwAEAMBABBwDAQAQcAAADEXAAAAz0/wAimmc95jgmjwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x109a9e3d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "y = map(lambda x: (4*x + 0) % 32, x)\n",
    "df = pd.DataFrame({'y':y})\n",
    "df.plot(kind='hist', xlim=(0,32), legend=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.5 Estimating Moments\n",
    "\n",
    "suppose we have a stream $s = e_1 e_2 \\dotsm e_n \\in {S}^n$.\n",
    "\n",
    "**kth-order moment** = $\\sum_{i \\in S} m_i^k$,     \n",
    "where $m_i$ is the number of occurrences of the $i$-th element in $S$.\n",
    "\n",
    "\n",
    "Example: \n",
    "\n",
    "1. 0th moment: the number of distinct elements, define $0^0 = 0$.\n",
    "\n",
    "2. 1th moment: the length of the stream.\n",
    "\n",
    "3. 2nd moment: named the *surprise number*, since it measure how uneven the distribution of elements in the stream is.\n",
    "\n",
    "\n",
    "#### 4.5.2 The Alon-Matias-Szegedy Algorithm for Second Moments\n",
    "\n",
    "We compute some number of variables,    \n",
    "for each variable $X$, we store:  \n",
    "\n",
    "1. $X.element \\in S$.\n",
    "\n",
    "2. $X.value = 1 + \\sum_{i=k+1}^{n} I(e_i = X.element)$    \n",
    "   where $k = random(1,n)$ and $X.element = e_k$.   \n",
    "   \n",
    "   namely, $X.value$ is the times $e_i$ picked randomly occurs in the position among $i, i+1, \\dotsc, n$.\n",
    "   \n",
    "an **estimate** of the 2nd moment from any variable $X$ is: $$ E_x = n(2 X.value - 1)$$    \n",
    "2nd moment $\\gets Ave_{x \\in S} (E_x)$\n",
    "\n",
    "\n",
    "##### Analysis: Why it works\n",
    "Let $s = e_1 e_2 \\dotsm e_n$, and $e \\in S = {S_1, S_2, \\dotsc, S_u}$.     \n",
    "    $c_i$ is the number of times $e_i$ appears among positions $i, i+1, \\dotsc, n$.\n",
    "    \n",
    "for any picked position $i$,  \n",
    "\\begin{align}\n",
    "    E[n(2X.value - 1)] &= n(2 E[X.value] - 1) \\\\\n",
    "                       &= n(2 \\frac{1}{n} \\sum_{i=1}^{n} (c_i) - 1) \\\\\n",
    "                       &= \\sum_{i=1}^{n} (2 c_i - 1) \\\\\n",
    "                       &\\text{for every $S_j$, existing an arithmetic progression } \\sum_a 1+3+ \\dotsb + (2m_a -1) \\\\\n",
    "                       &= \\color{red}{ \\sum_{j=1}^{u} \\sum_{k=1}^{m_{S_j}} (2k - 1) } \\\\\n",
    "                       &= \\sum_{j=1}^{u} \\frac{m_{S_j}}{2} (1 + (2 m_{S_j} - 1)) \\\\\n",
    "                       &= \\sum_{j=1}^{u} m^2_{S_j} \\quad = \\text{ 2nd moment}\n",
    "\\end{align}\n",
    "\n",
    "\n",
    "##### Higher-Order Moments\n",
    "for any $k \\geq 2$ and $v = X.value$,     \n",
    "estimate $k$th moments is $$n (v^k - (v-1)^k)$$.\n",
    "\n",
    "because for given a, $\\sum_{v=1}^{m_a} (v^k - (v-1)^k) = m_a^k$.\n",
    "\n",
    "\n",
    "#### 4.5.5 Dealing With Infinite \n",
    "In practice, $n$ is not fixed, but it grows with time.       \n",
    "\n",
    "+ store variable: $> log_2 n$ bits.    \n",
    "\n",
    "+ break the condition: every position is picked in **equal probility**.  \n",
    "\n",
    "\n",
    "**Solution**:   \n",
    "idea: maintain as many variable $X$ as possible at all times, and to throw some out as the stream grows.\n",
    "\n",
    "Suppose we have space to store $s$ variables, and we have seen $n$ stream elements.     \n",
    "hence, the probility of any particular position is picked is $\\frac{s}{n}$.\n",
    "\n",
    "When the $(n+1)$th element arrivs, pick that position with probility $\\frac{s}{n+1}$.    \n",
    "+ if not picked, $s$ remained.    \n",
    "+ if picked, one of $s$ is ruled out in equal probility, and replaced by the $(n+1)$ position of element $e(n+1)$ with initial value $1$.  \n",
    "\n",
    "\n",
    "**Analysis**: how the solution correct the probility of any position picked?    \n",
    "\n",
    "1. for the $(n+1)$th position, the probility of being picked is: $$\\frac{s}{n+1}$$\n",
    "\n",
    "2. for the original $s$ position, the probility of being picked(remained) is: \n",
    "$$ \\frac{s}{n} (1 - \\frac{s}{n+1} \\frac{1}{s}) = \\frac{s}{n+1} $$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#todo code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6 Counting Ones in a Window\n",
    "\n",
    "**Question**: how many 1's are there in the last $k$ bits of a window with length $N$, for any $k \\leq N$.\n",
    "\n",
    "**solutions**:\n",
    "\n",
    "1. exact counts: store all $N$ bits at cost.\n",
    "\n",
    "2. approxicate counts: use $O(lg^2 N)$ bits to represent the window, in the Datar-Gionis-Indyk-Motwani Algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.6.2  The Datar-Gionis-Indyk-Motwani Algorithm\n",
    "\n",
    "##### buckets\n",
    "we divide the window into buckets.\n",
    "\n",
    "**construction**\n",
    "    \n",
    "1. The timestamp of its right end.\n",
    "    \n",
    "2. The number of 1's in the bucket.\n",
    "\n",
    "\n",
    "**rules**\n",
    "\n",
    "1. The right end of a bucket is always a position with a 1.\n",
    "\n",
    "2. Every position with a 1 is in some bucket.\n",
    "\n",
    "3. No position is in more than one bucket.\n",
    "\n",
    "4. There are **one or two** buckets of **any given size, up to some maximum size**.     \n",
    "   namely, suppose the size of the maximum bucket is $2^j$,     \n",
    "   then, the buckets of the windows should contain all size $2^j, 2^{j-1}, \\dotsc, 2^0$, and any size of those should appear either one or two times.\n",
    "\n",
    "5. All sizes must be a power of 2.\n",
    "\n",
    "6. Buckets cannot **decrease** in size as we move to the left.\n",
    "\n",
    "![Fig 4.2](./res/fig_4_2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Storage Requirements\n",
    "\n",
    "1. the maximum size of a bucket is $N$, hence it can be represented by $O(lg N)$ bits.\n",
    "\n",
    "2. there are at most two buckets for every size from 1 to the maximu size, $2 * j = 2 lg N$，     \n",
    "   namely, $O(lg N)$ buckets.\n",
    "   \n",
    "above all, the total space required for all the buckets representing a window of size $N$ is $O(lg^2 N)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Query Answering\n",
    "\n",
    "suppose a window of length $N$ is represented by all buckets $\\{b_0, b_1, \\dotsc, b_j, \\dotsc, b_n\\}$, where $b_j$ owns two attributes: timestamp, and size.\n",
    "\n",
    "for a given $k$, the answer is $$\\frac{1}{2} b_j.size + \\sum_{i=0}^{j-1} b_i.size \\quad \\text{for } b_{j+1}\\text{.timestamp} > k \\geq b_j\\text{.timestamp}$$\n",
    "\n",
    "**error analysis**:      \n",
    "supposet $c$ is the correct counts. \n",
    "\n",
    "there are two cases for estimate:\n",
    "\n",
    "1. underestimate.    \n",
    "   + in the worst case, all the 1's of $b_j$ are actually within the query range $k$.     \n",
    "     $\\implies$ the estimate misses half bucket $b_j$, namely, $\\frac{1}{2} b_j.size = 2^{j-1}$ 1's.    \n",
    "   + $c$ is at least $\\frac{1 (1 - 2^{j+1})}{1 - 2} = 2^{j+1} - 1$, since there is at least one bucket of each of the size $2^{j-1}, 2^{j-2}, \\dotsc, 1$.\n",
    "   + in all,     \n",
    "     \\begin{align}\n",
    "         error &= \\frac{miss}{c} \\\\\n",
    "               &= \\frac{2^{j-1}}{2^{j+1} - 1} \\\\\n",
    "               &\\leq \\frac{1}{2}\n",
    "     \\end{align}\n",
    "\n",
    "2. overestimate.   \n",
    "   + in the worse case, only the rightmost bit of bucket $b_j$ is within range $k$.   \n",
    "     $implies$ we overestimate $\\frac{b_j.size}{2} - 1 = 2^{j-1} -1$ 1's.    \n",
    "   + $c$ is at least $1 + 2^j -1 = 2^j$ 1's.    \n",
    "   + in all,    \n",
    "     \\begin{align}\n",
    "         error &= \\frac{overestimate}{c} \\\\\n",
    "               &= \\frac{2^{j-1} - 1}{2^j} \\\\\n",
    "               &\\leq \\frac{1}{2}\n",
    "     \\end{align}\n",
    "   \n",
    " \n",
    "**conclusion**: error is no more than 50% greater than $c$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Maintaining\n",
    "At $t$ time, a new bit enters:\n",
    "\n",
    "1. Check the leftmost bucket.      \n",
    "   if $b_n.timestamp = t - N$, drop it.\n",
    "   \n",
    "2. Check the value of the new bit.    \n",
    "   if it is 0, do nothing;    \n",
    "   if it is 1, create a new bucket with $t$ and size $1$.      \n",
    "   + Check if three same size buckets existed,    \n",
    "     1. if yes, combine the left two adjacent buckets of those, and check the new size bucket again (repeat).      \n",
    "     2. if no, the round end.      \n",
    "     \n",
    "     at most $O(lg N)$ times to check.\n",
    "     \n",
    "![fig 4.3](./res/fig_4_3.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#todo code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Reducing the Error\n",
    "\n",
    "idea:    \n",
    "reduce the error $\\gets$ more buckets of **small** sizes $\\gets$ relax condition: we allow either $r-1$ or $r$ of each of the exponentially growing sizes for $r > 2$.\n",
    "\n",
    "combine rules:     \n",
    "If we get $r+1$ buckets of size $2^j$, combine the leftmost two into a bucket of size $2^{j+1}$.\n",
    "\n",
    "error analysis:    \n",
    "\n",
    "1. overestimate.    \n",
    "   overestimate is $2^{j-1} - 1$.     \n",
    "   $c$ is at least $1 + (r-1)(2^{j-1} + 2^{j-2} + \\dotsb + 1) = 1 + (r-1)(2^j-1)$.     \n",
    "   the fractional error is $$\\frac{2^{j-1} - 1}{1 + (r-1)(2^j - 1)} \\leq \\frac{1}{r-1}$$\n",
    "  \n",
    "2. underestimate.\n",
    "\n",
    "conclusion: by picking $r$ sufficiently large, we can limit the error to any desired $\\epsilon > 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Extensions\n",
    "question: the sum of the last $k$ **integers** for any $1 \\leq k \\leq N$.\n",
    "\n",
    "there are two cases:\n",
    "\n",
    "1. unlikely work out.     \n",
    "   when the stream contains both positive and negative integers.\n",
    "   \n",
    "2. work.    \n",
    "   when the steam contains only positive integers in the range 1 to $2^m$.     \n",
    "   solution:     \n",
    "   + we can treat each of the m bits of each integers as if it were a separate stream.      \n",
    "   + use the DGIM method to count $c_i$ in $i$th bit stream.     \n",
    "   + the sum of the integers is: $$\\sum_{i=0}^{m-1} c_i 2^i$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#todo exercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.7 Decaying Windows\n",
    "\n",
    "#### exponentially decaying window\n",
    "Let a steam $= \\{a_1, a_2, \\dotsc, a_t\\}$,      \n",
    "we define the exponentially decaying window for this stream to be the sum: $$\\sum_{i=0}^{t-1} a_{t-i} (1-c)^i$$\n",
    "\n",
    "![fig 4.4](./res/fig_4_4.png)\n",
    "\n",
    "maintain:    \n",
    "when a new element $a_{t+1}$ arrives, all we need to do is:\n",
    "\n",
    "1. Multiply the current sum by $1-c$.\n",
    "\n",
    "2. Add $a_{t+}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Finding the Most Popular Elements\n",
    "\n",
    "When a new ticket arrives on the stream, do the following:\n",
    "\n",
    "1. For each movie, multiply its score by $(1-c)$.\n",
    "\n",
    "2. Suppose the new ticket is for movie $M$.     \n",
    "   1. if a score for $M$ existed, add 1.    \n",
    "   2. if not, create one and initialize it to 1.\n",
    "   \n",
    "3. If any score is below the threshold $1/2$, drop that score.\n",
    "\n",
    "\n",
    "analysis:\n",
    "\n",
    "Note that the sum of all scores is $1/c$,     \n",
    "there cannot be more than $2/c$ moview with score of $1/2$ or more. $\\gets$ $1/c = 1/2 \\times 2/c$.\n",
    "\n",
    "hence, $2/c$ is a limit on the number of movies being counted at any time."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}