DTSA_5501_Homework4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a55c6e4d82cad380b8cebb62285c516f",
     "grade": false,
     "grade_id": "cell-11e6289c84816863",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Assignment 4\n",
    "\n",
    "In this assignment, we will explore countmin sketches and bloom filters. We will use two text files `great-gatsby-fitzgerald.txt` and `war-and-peace-tolstoy.txt` to load up the text of two famous novels courtesy of Project Guttenberg. \n",
    "\n",
    "We will explore two tasks:\n",
    "  - Counting the frequency of words of length 5 or more in both novels using a count-min sketch \n",
    "  - Using a bloom filter to approximately count how many words in the War and Peace novel already appears in the Great Gatsby."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "f7a2a9b0f0fe586464a31d8e4ecda728",
     "grade": false,
     "grade_id": "cell-dfc8e09426234a08",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Step 1:  Making a Universal Hash Family (Already Done For You)\n",
    "\n",
    "We will use a family of hash function that first starts by (a) generating a random prime number $p$ (we will use the Miller-Rabin primality test for this purpopse); (b) generating random numbers a, b between 2 and p-1.\n",
    "\n",
    "The hash function $h_{a,b,p} (n) = (an + b) \\mod p$. \n",
    "\n",
    "Note that this function will be between 0 and p-1. We will need to also make sure to take the hash value modulo $m$ where $m$ is the size of the hashtable.\n",
    "\n",
    "To hash strings, we will first use python's inbuilt hash function and then use $h_{a,b,p}$ on the result.\n",
    "\n",
    "As a first step, we will generate a random prime number.\n",
    "\n",
    "### (A) Generate Random Prime Numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "655633cc8179edf1da08316324a305a5",
     "grade": false,
     "grade_id": "cell-29b403a91ab960c0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All primes smaller than 100: \n",
      "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 "
     ]
    }
   ],
   "source": [
    "# Python3 program Miller-Rabin randomized primality test\n",
    "# Copied from geeksforgeeks: https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/\n",
    "import random \n",
    "\n",
    "# Utility function to do \n",
    "# modular exponentiation. \n",
    "# It returns (x^y) % p \n",
    "def power(x, y, p): \n",
    "\t\n",
    "\t# Initialize result \n",
    "\tres = 1; \n",
    "\t\n",
    "\t# Update x if it is more than or \n",
    "\t# equal to p \n",
    "\tx = x % p; \n",
    "\twhile (y > 0): \n",
    "\t\t\n",
    "\t\t# If y is odd, multiply \n",
    "\t\t# x with result \n",
    "\t\tif (y & 1): \n",
    "\t\t\tres = (res * x) % p; \n",
    "\n",
    "\t\t# y must be even now \n",
    "\t\ty = y>>1; # y = y/2 \n",
    "\t\tx = (x * x) % p; \n",
    "\t\n",
    "\treturn res; \n",
    "\n",
    "# This function is called \n",
    "# for all k trials. It returns \n",
    "# false if n is composite and \n",
    "# returns false if n is \n",
    "# probably prime. d is an odd \n",
    "# number such that d*2<sup>r</sup> = n-1 \n",
    "# for some r >= 1 \n",
    "def miillerTest(d, n): \n",
    "\t\n",
    "\t# Pick a random number in [2..n-2] \n",
    "\t# Corner cases make sure that n > 4 \n",
    "\ta = 2 + random.randint(1, n - 4); \n",
    "\n",
    "\t# Compute a^d % n \n",
    "\tx = power(a, d, n); \n",
    "\n",
    "\tif (x == 1 or x == n - 1): \n",
    "\t\treturn True; \n",
    "\n",
    "\t# Keep squaring x while one \n",
    "\t# of the following doesn't \n",
    "\t# happen \n",
    "\t# (i) d does not reach n-1 \n",
    "\t# (ii) (x^2) % n is not 1 \n",
    "\t# (iii) (x^2) % n is not n-1 \n",
    "\twhile (d != n - 1): \n",
    "\t\tx = (x * x) % n; \n",
    "\t\td *= 2; \n",
    "\n",
    "\t\tif (x == 1): \n",
    "\t\t\treturn False; \n",
    "\t\tif (x == n - 1): \n",
    "\t\t\treturn True; \n",
    "\n",
    "\t# Return composite \n",
    "\treturn False; \n",
    "\n",
    "# It returns false if n is \n",
    "# composite and returns true if n \n",
    "# is probably prime. k is an \n",
    "# input parameter that determines \n",
    "# accuracy level. Higher value of \n",
    "# k indicates more accuracy. \n",
    "def isPrime( n, k): \n",
    "\t\n",
    "\t# Corner cases \n",
    "\tif (n <= 1 or n == 4): \n",
    "\t\treturn False; \n",
    "\tif (n <= 3): \n",
    "\t\treturn True; \n",
    "\n",
    "\t# Find r such that n = \n",
    "\t# 2^d * r + 1 for some r >= 1 \n",
    "\td = n - 1; \n",
    "\twhile (d % 2 == 0): \n",
    "\t\td //= 2; \n",
    "\n",
    "\t# Iterate given nber of 'k' times \n",
    "\tfor i in range(k): \n",
    "\t\tif (miillerTest(d, n) == False): \n",
    "\t\t\treturn False; \n",
    "\n",
    "\treturn True; \n",
    "\n",
    "# Driver Code \n",
    "# Number of iterations \n",
    "k = 4; \n",
    "\n",
    "print(\"All primes smaller than 100: \"); \n",
    "for n in range(1,100): \n",
    "\tif (isPrime(n, k)): \n",
    "\t\tprint(n , end=\" \"); \n",
    "\n",
    "# This code is contributed by mits (see citation above)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All primes smaller than 1000: \n",
      "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 "
     ]
    }
   ],
   "source": [
    "print(\"All primes smaller than 1000: \"); \n",
    "for n in range(1,1000): \n",
    "\tif (isPrime(n, k)): \n",
    "\t\tprint(n , end=\" \"); \n",
    "\n",
    "# This code is contributed by mits (see citation above)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "8ac8a3f52da6274beeda7e3ec8bbeac1",
     "grade": false,
     "grade_id": "cell-73221461b19b5567",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Step 2: Universal Hash Families\n",
    "\n",
    "We will provide three useful functions for you:\n",
    "\n",
    "  - `get_random_hash_function`: Generate triple of numbers `(p, a, b)` at random, where p is  prime, a and b are numbers between 2 and p-1. The hash function $h_{p,a,b}(n)$ is given by $ (an + b) \\mod p$.\n",
    "  \n",
    "  - `hashfun`: apply the random hash function on a number `num`.\n",
    "  - `hash_string`: apply the hash function on a string `hstr`. Note that the result is between 0 and p-1. If your hash table has size `m`, you should take a `mod m` on this result where you call `hash_string`.\n",
    "  \n",
    "  Please use these functions in your code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "ef7c5ab31c424ee21d9a1c3b81ff2fd8",
     "grade": false,
     "grade_id": "cell-1c9654f9fcd91883",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Get a random triple (p, a, b) where p is prime and a,b are numbers betweeen 2 and p-1\n",
    "def get_random_hash_function():\n",
    "    n = random.getrandbits(64)\n",
    "    if n < 0: \n",
    "        n = -n \n",
    "    if n % 2 == 0:\n",
    "        n = n + 1\n",
    "    while not isPrime(n, 20):\n",
    "        n = n + 1\n",
    "    a = random.randint(2, n-1)\n",
    "    b = random.randint(2, n-1)\n",
    "    return (n, a, b)\n",
    "\n",
    "# hash function fora number\n",
    "def hashfun(hfun_rep, num):\n",
    "    (p, a, b) = hfun_rep\n",
    "    return (a * num + b) % p\n",
    "\n",
    "# hash function for a string.\n",
    "def hash_string(hfun_rep, hstr):\n",
    "    n = hash(hstr)\n",
    "    return hashfun(hfun_rep, n)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "575e46059b43af6f541a7c5e74e6e956",
     "grade": false,
     "grade_id": "cell-f383acfe5e19ce49",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Step 3: Loading Data\n",
    "\n",
    "We are going to load two files `great-gatsby-fitzgerald.txt` and `war-and-peace-tolstoy.txt` to load up the text of two famous novels courtesy of Project Guttenberg. We will filter all wordsd of length >= 5 and also count the frequency of each word in a dictionary. This will be fast because it is going to use highly optimized hashtable (dictionaries) built into python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "012317538b0b54757a490f1ebcf19045",
     "grade": false,
     "grade_id": "cell-22b93e681d415b67",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21342\n",
      "8849\n"
     ]
    }
   ],
   "source": [
    "# Let us load the \"Great Gatsby\" novel and extract all words of length 5 or more\n",
    "filename = 'great-gatsby-fitzgerald.txt'\n",
    "file = open (filename,'r')\n",
    "txt = file.read()\n",
    "txt = txt.replace('\\n',' ')\n",
    "words= txt.split(' ')\n",
    "longer_words_gg = list(filter(lambda s: len(s) >= 5, words))\n",
    "print(len(longer_words_gg))\n",
    "# Let us count the precise word frequencies\n",
    "word_freq_gg = {}\n",
    "for elt in longer_words_gg:\n",
    "    if elt in word_freq_gg:\n",
    "        word_freq_gg[elt] += 1\n",
    "    else:\n",
    "        word_freq_gg[elt] = 1\n",
    "print(len(word_freq_gg))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "1be2b84b70b54d25daae840d3c5a007a",
     "grade": false,
     "grade_id": "cell-ad7310bc2a593322",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "237611\n",
      "38777\n"
     ]
    }
   ],
   "source": [
    "# Let us load the \"War and Peace\" novel by Tolstoy translation and extract all words of length 5 or more\n",
    "filename = 'war-and-peace-tolstoy.txt'\n",
    "file = open (filename,'r')\n",
    "txt = file.read()\n",
    "txt = txt.replace('\\n',' ')\n",
    "words= txt.split(' ')\n",
    "longer_words_wp = list(filter(lambda s: len(s) >= 5, words))\n",
    "print(len(longer_words_wp))\n",
    "word_freq_wp = {}\n",
    "for elt in longer_words_wp:\n",
    "    if elt in word_freq_wp:\n",
    "        word_freq_wp[elt] += 1\n",
    "    else:\n",
    "        word_freq_wp[elt] = 1\n",
    "print(len(word_freq_wp))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "56e7a5e610cd3780396524e82e81003c",
     "grade": false,
     "grade_id": "cell-4a80bf43ea35608c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 1: Implement count-min sketch\n",
    "\n",
    "Implement `CountMinSketch` class below where `num_counters` is the number of counters.  You are given the constructor that already generates a random representative of a hash function family. Implement the functions:\n",
    "  - `increment`\n",
    "  - `approximateCount`.\n",
    "  \n",
    "Please read the constructor carefully: it initializes the counters and generates the hash function for you.\n",
    "Also, when you call `hash_string` function defined previously, do not forget to take result modulo m."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "031189883fee31a6a51def4aff506813",
     "grade": false,
     "grade_id": "cell-4f9b9b03abdcfe40",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# Class for implementing a count min sketch \"single bank\" of counters\n",
    "class CountMinSketch:\n",
    "    # Initialize with `num_counters`\n",
    "    def __init__ (self, num_counters):\n",
    "        self.m = num_counters\n",
    "        self.hash_fun_rep = get_random_hash_function()\n",
    "        self.counters = [0]*self.m\n",
    "    \n",
    "    # function: increment \n",
    "    # given a word, increment its count in the countmin sketch\n",
    "    def increment(self, word): \n",
    "        i = (hash_string(self.hash_fun_rep,word)%self.m)\n",
    "        self.counters[i] +=1\n",
    "        \n",
    "        \n",
    "        \n",
    "    # function: approximateCount\n",
    "    # Given a word, get its approximate count\n",
    "    def approximateCount(self, word): \n",
    "        i = (hash_string(self.hash_fun_rep,word)%self.m)\n",
    "        return self.counters[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "377"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = CountMinSketch(25)\n",
    "for i in word_freq_gg.keys():\n",
    "    y.increment(i)\n",
    "y.approximateCount('sense')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3  Times\n",
      "sense\n"
     ]
    }
   ],
   "source": [
    "x= 177\n",
    "print(word_freq_gg[list(word_freq_gg.keys())[x]],\" Times\")\n",
    "print(list(word_freq_gg.keys())[x]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "e86661497abeaf155d311f90314b2c50",
     "grade": false,
     "grade_id": "cell-52b69c2c1b76f6a8",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "# We will now implement the algorithm for a bank of k counters\n",
    "\n",
    "# Initialize k different counters\n",
    "def initialize_k_counters(k, m): \n",
    "    return [CountMinSketch(m) for i in range(k)]\n",
    "\n",
    "# Function increment_counters\n",
    "# increment each of the individual counters with the word\n",
    "def increment_counters(count_min_sketches, word):\n",
    "    return([cms.increment(word) for cms in count_min_sketches]) \n",
    "    \n",
    "        \n",
    "# Function: approximate_count\n",
    "# Get the approximate count by querying each counter bank and taking the minimum\n",
    "def approximate_count(count_min_sketches, word):\n",
    "    return min([cms.approximateCount(word) for cms in count_min_sketches])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "9092f909c1bde4f0b80c67144ace3e49",
     "grade": true,
     "grade_id": "cell-f46918d88bcfc44c",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Passed all tests: 10 points\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD4CAYAAAAAczaOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAOOUlEQVR4nO3df6jd9X3H8edrSau2nVTnVWySLQ6yHyprncFl6xilFsxqafxHyKAzG0JA3GZHRxf7T9kg4GCUTliF0HZGWiqhLTPUuS1LW7aB0121w8ZUDNVpZmZuN7ra/WGnfe+P85Wd5d7knjTJOd77fj7gcL7nc77fc77ng3neL9/zw1QVkqQefmzWOyBJmh6jL0mNGH1JasToS1IjRl+SGlk76x1YziWXXFIbN26c9W5I0ory2GOPfaeq5k4cf8NHf+PGjczPz896NyRpRUnyr0uNe3pHkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGnnDfyN3Jdq468GZPfdzd904s+eW9Mbnkb4kNWL0JakRoy9JjRh9SWrE6EtSI0Zfkhox+pLUiNGXpEb8ctYqM6svhvmlMGll8Ehfkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjE0U/ye8nOZTkm0m+kOT8JBcnOZDkmeH6orH170xyJMnTSW4YG782yZPDfXcnybl4UZKkpS0b/STrgN8DNlfV1cAaYDuwCzhYVZuAg8Ntklw53H8VsBX4VJI1w8PdA+wENg2XrWf11UiSTmnS0ztrgQuSrAXeArwIbAP2DvfvBW4alrcB91fVK1X1LHAEuC7J5cCFVfVwVRVw39g2kqQpWDb6VfVvwJ8CzwPHgP+qqr8FLquqY8M6x4BLh03WAS+MPcTRYWzdsHzi+CJJdiaZTzK/sLBweq9IknRSk5zeuYjR0fsVwDuAtyb50Kk2WWKsTjG+eLBqT1VtrqrNc3Nzy+2iJGlCk5zeeR/wbFUtVNX/AF8GfgV4aThlw3B9fFj/KLBhbPv1jE4HHR2WTxyXJE3JJNF/HtiS5C3Dp22uBw4D+4Edwzo7gAeG5f3A9iTnJbmC0Ru2jw6ngF5OsmV4nFvGtpEkTcGyv6dfVY8k+SLwOPAq8ASwB3gbsC/JrYz+MNw8rH8oyT7gqWH926vqteHhbgPuBS4AHhoukqQpmeh/olJVHwc+fsLwK4yO+pdafzewe4nxeeDq09xHSdJZ4jdyJakRoy9JjRh9SWrE6EtSI0Zfkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGjH6ktSI0ZekRoy+JDVi9CWpEaMvSY0YfUlqxOhLUiNGX5IaMfqS1IjRl6RGjL4kNWL0JakRoy9JjRh9SWrE6EtSI0Zfkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGpko+knenuSLSb6V5HCSX05ycZIDSZ4Zri8aW//OJEeSPJ3khrHxa5M8Odx3d5KcixclSVrapEf6fwb8dVX9HPBO4DCwCzhYVZuAg8NtklwJbAeuArYCn0qyZnice4CdwKbhsvUsvQ5J0gSWjX6SC4FfAz4DUFU/qKrvAtuAvcNqe4GbhuVtwP1V9UpVPQscAa5LcjlwYVU9XFUF3De2jSRpCiY50v9pYAH4iyRPJPl0krcCl1XVMYDh+tJh/XXAC2PbHx3G1g3LJ45LkqZkkuivBX4RuKeqrgH+m+FUzkksdZ6+TjG++AGSnUnmk8wvLCxMsIuSpElMEv2jwNGqemS4/UVGfwReGk7ZMFwfH1t/w9j264EXh/H1S4wvUlV7qmpzVW2em5ub9LVIkpaxbPSr6t+BF5L87DB0PfAUsB/YMYztAB4YlvcD25Ocl+QKRm/YPjqcAno5yZbhUzu3jG0jSZqCtROu97vA55O8Gfg28NuM/mDsS3Ir8DxwM0BVHUqyj9EfhleB26vqteFxbgPuBS4AHhoukqQpmSj6VfUNYPMSd11/kvV3A7uXGJ8Hrj6dHZQknT1+I1eSGjH6ktSI0ZekRoy+JDVi9CWpEaMvSY0YfUlqxOhLUiNGX5IaMfqS1IjRl6RGjL4kNWL0JakRoy9JjRh9SWrE6EtSI0Zfkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGjH6ktSI0ZekRoy+JDVi9CWpEaMvSY0YfUlqxOhLUiNGX5IaMfqS1IjRl6RGjL4kNWL0JakRoy9JjUwc/SRrkjyR5CvD7YuTHEjyzHB90di6dyY5kuTpJDeMjV+b5MnhvruT5Oy+HEnSqZzOkf4dwOGx27uAg1W1CTg43CbJlcB24CpgK/CpJGuGbe4BdgKbhsvWM9p7SdJpmSj6SdYDNwKfHhveBuwdlvcCN42N319Vr1TVs8AR4LoklwMXVtXDVVXAfWPbSJKmYNIj/U8CHwV+ODZ2WVUdAxiuLx3G1wEvjK13dBhbNyyfOL5Ikp1J5pPMLywsTLiLkqTlLBv9JB8AjlfVYxM+5lLn6esU44sHq/ZU1eaq2jw3Nzfh00qSlrN2gnXeDXwwyfuB84ELk3wOeCnJ5VV1bDh1c3xY/yiwYWz79cCLw/j6JcYlSVOy7JF+Vd1ZVeuraiOjN2i/WlUfAvYDO4bVdgAPDMv7ge1JzktyBaM3bB8dTgG9nGTL8KmdW8a2kSRNwSRH+idzF7Avya3A88DNAFV1KMk+4CngVeD2qnpt2OY24F7gAuCh4SJJmpLTin5VfR34+rD8H8D1J1lvN7B7ifF54OrT3UlJ0tnhN3IlqRGjL0mNGH1JasToS1IjRl+SGjH6ktSI0ZekRoy+JDVi9CWpEaMvSY0YfUlqxOhLUiNGX5IaMfqS1IjRl6RGjL4kNWL0JakRoy9JjRh9SWrE6EtSI0Zfkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGjH6ktSI0ZekRoy+JDVi9CWpEaMvSY0YfUlqxOhLUiNGX5IaWTb6STYk+VqSw0kOJbljGL84yYEkzwzXF41tc2eSI0meTnLD2Pi1SZ4c7rs7Sc7Ny5IkLWXtBOu8Cnykqh5P8uPAY0kOAL8FHKyqu5LsAnYBf5jkSmA7cBXwDuDvkvxMVb0G3APsBP4J+CtgK/DQ2X5Rr9u468Fz9dCStCIte6RfVceq6vFh+WXgMLAO2AbsHVbbC9w0LG8D7q+qV6rqWeAIcF2Sy4ELq+rhqirgvrFtJElTcFrn9JNsBK4BHgEuq6pjMPrDAFw6rLYOeGFss6PD2Lph+cTxpZ5nZ5L5JPMLCwuns4uSpFOYOPpJ3gZ8CfhwVX3vVKsuMVanGF88WLWnqjZX1ea5ublJd1GStIyJop/kTYyC//mq+vIw/NJwyobh+vgwfhTYMLb5euDFYXz9EuOSpCmZ5NM7AT4DHK6qT4zdtR/YMSzvAB4YG9+e5LwkVwCbgEeHU0AvJ9kyPOYtY9tIkqZgkk/vvBv4TeDJJN8Yxj4G3AXsS3Ir8DxwM0BVHUqyD3iK0Sd/bh8+uQNwG3AvcAGjT+2cs0/uSJIWWzb6VfWPLH0+HuD6k2yzG9i9xPg8cPXp7KAk6ezxG7mS1IjRl6RGjL4kNWL0JakRoy9JjRh9SWpkks/pS8ua5S+aPnfXjTN7bmml8Uhfkhox+pLUiNGXpEaMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGjH6ktSI0ZekRoy+JDVi9CWpEaMvSY0YfUlqxOhLUiNGX5IaMfqS1IjRl6RGjL4kNWL0JakRoy9JjRh9SWrE6EtSI0Zfkhox+pLUiNGXpEbWznoHpDO1cdeDM3ne5+66cSbPK50Jj/QlqRGjL0mNGH1JamTq0U+yNcnTSY4k2TXt55ekzqYa/SRrgD8Hfh24EviNJFdOcx8kqbNpf3rnOuBIVX0bIMn9wDbgqSnvh3TGZvWpIfCTQ/rRTTv664AXxm4fBX7pxJWS7AR2Dje/n+TpH/H5LgG+8yNuu1o5J4utuDnJn5zzp1hxczIlK2lefmqpwWlHP0uM1aKBqj3AnjN+smS+qjaf6eOsJs7JYs7JYs7J0lbDvEz7jdyjwIax2+uBF6e8D5LU1rSj/8/ApiRXJHkzsB3YP+V9kKS2pnp6p6peTfI7wN8Aa4DPVtWhc/iUZ3yKaBVyThZzThZzTpa24uclVYtOqUuSVim/kStJjRh9SWpkVUbfn3oYSfLZJMeTfHNs7OIkB5I8M1xfNMt9nLYkG5J8LcnhJIeS3DGMt52XJOcneTTJvwxz8kfDeNs5eV2SNUmeSPKV4faKn5NVF31/6uH/uRfYesLYLuBgVW0CDg63O3kV+EhV/TywBbh9+O+j87y8Ary3qt4JvAvYmmQLvefkdXcAh8dur/g5WXXRZ+ynHqrqB8DrP/XQTlX9PfCfJwxvA/YOy3uBm6a6UzNWVceq6vFh+WVG/6DX0XheauT7w803DZei8ZwAJFkP3Ah8emx4xc/Jaoz+Uj/1sG5G+/JGdFlVHYNRAIFLZ7w/M5NkI3AN8AjN52U4jfEN4DhwoKrazwnwSeCjwA/Hxlb8nKzG6E/0Uw/qLcnbgC8BH66q7816f2atql6rqncx+pb8dUmunvU+zVKSDwDHq+qxWe/L2bYao+9PPZzaS0kuBxiuj894f6YuyZsYBf/zVfXlYbj9vABU1XeBrzN6L6jznLwb+GCS5xidIn5vks+xCuZkNUbfn3o4tf3AjmF5B/DADPdl6pIE+AxwuKo+MXZX23lJMpfk7cPyBcD7gG/ReE6q6s6qWl9VGxk15KtV9SFWwZysym/kJnk/o/Nxr//Uw+4Z79JMJPkC8B5GPwf7EvBx4C+BfcBPAs8DN1fViW/2rlpJfhX4B+BJ/u9c7ccYnddvOS9JfoHRm5JrGB0I7quqP07yEzSdk3FJ3gP8QVV9YDXMyaqMviRpaavx9I4k6SSMviQ1YvQlqRGjL0mNGH1JasToS1IjRl+SGvlf1f/O1LceHZgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "\n",
    "%matplotlib inline\n",
    "from matplotlib import pyplot as plt \n",
    "\n",
    "# Let's see how well your solution performs for the Great Gatsby words\n",
    "cms_list = initialize_k_counters(5, 1000)\n",
    "for word in longer_words_gg:\n",
    "    increment_counters(cms_list, word)\n",
    "\n",
    "discrepencies = []\n",
    "for word in longer_words_gg:\n",
    "    l = approximate_count(cms_list, word)\n",
    "    r = word_freq_gg[word]\n",
    "    assert ( l >= r)\n",
    "    discrepencies.append( l-r )\n",
    "    \n",
    "plt.hist(discrepencies)\n",
    "\n",
    "assert(max(discrepencies) <= 200), 'The largest discrepency must be definitely less than 200 with high probability. Please check your implementation'\n",
    "print('Passed all tests: 10 points')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "f5f9d0e915170f181348ff78d61fac1f",
     "grade": true,
     "grade_id": "cell-592d2f3552e20599",
     "locked": true,
     "points": 5,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Passed all tests: 5 points\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAD4CAYAAADy46FuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAARlklEQVR4nO3df6zd9V3H8efL1jF+BORHIdiiF0OjAokyGqzOmMVOqbKs/AHxmiCNqWlCUNmiMWX/EDVNIDGiJEJCYKOwZdB0JDQStpGiURNSdhkmrFTCzUC4o6NXYYgmsBXf/nE+V04vt5/Se0rPLX0+kpPz/b6/n8/3fO4nvXn1+/mec26qCkmSDuXHxj0ASdLSZlBIkroMCklSl0EhSeoyKCRJXcvHPYCj7ZxzzqmJiYlxD0OSjitPP/30f1TVioWOfeSCYmJigqmpqXEPQ5KOK0n+/VDHXHqSJHUZFJKkLoNCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1feQ+mX28mtjy6Nhe+6Vbrxrba0ta+ryikCR1GRSSpC6DQpLUZVBIkroMCklSl0EhSeoyKCRJXQaFJKnLoJAkdRkUkqSuwwZFki8m2Z/kO0O1s5I8nuSF9nzm0LGbk0wneT7JlUP1y5M8247dkSStflKSh1p9d5KJoT4b22u8kGTj0fqhJUkf3Ae5orgPWD+vtgXYVVWrgV1tnyQXA5PAJa3PnUmWtT53AZuB1e0xd85NwBtVdRFwO3BbO9dZwC3ALwFXALcMB5Ik6dg4bFBU1T8Br88rbwC2te1twNVD9Qer6p2qehGYBq5Icj5welU9WVUF3D+vz9y5dgDr2tXGlcDjVfV6Vb0BPM77A0uS9CFb7D2K86pqH0B7PrfVVwKvDLWbabWVbXt+/aA+VXUAeBM4u3Ou90myOclUkqnZ2dlF/kiSpIUc7ZvZWaBWnfpi+xxcrLq7qtZU1ZoVK1Z8oIFKkj6YxQbFa205ifa8v9VngAuG2q0CXm31VQvUD+qTZDlwBoOlrkOdS5J0DC02KHYCc+9C2gg8MlSfbO9kupDBTeun2vLUW0nWtvsP18/rM3eua4An2n2MbwC/meTMdhP7N1tNknQMHfYv3CX5KvAp4JwkMwzeiXQrsD3JJuBl4FqAqtqTZDvwHHAAuLGq3m2nuoHBO6hOBh5rD4B7gQeSTDO4kphs53o9yV8C32rt/qKq5t9UlyR9yA4bFFX1u4c4tO4Q7bcCWxeoTwGXLlB/mxY0Cxz7IvDFw41RkvTh8ZPZkqQug0KS1GVQSJK6DApJUtdhb2afaCa2PDruIUjSkuIVhSSpy6CQJHUZFJKkLoNCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1GRSSpC6DQpLUZVBIkroMCklSl0EhSeoyKCRJXQaFJKnLoJAkdRkUkqQug0KS1GVQSJK6DApJUpdBIUnqMigkSV0jBUWSzyfZk+Q7Sb6a5ONJzkryeJIX2vOZQ+1vTjKd5PkkVw7VL0/ybDt2R5K0+klJHmr13UkmRhmvJOnILTookqwE/hhYU1WXAsuASWALsKuqVgO72j5JLm7HLwHWA3cmWdZOdxewGVjdHutbfRPwRlVdBNwO3LbY8UqSFmfUpaflwMlJlgOnAK8CG4Bt7fg24Oq2vQF4sKreqaoXgWngiiTnA6dX1ZNVVcD98/rMnWsHsG7uakOSdGwsOiiq6nvAXwEvA/uAN6vqm8B5VbWvtdkHnNu6rAReGTrFTKutbNvz6wf1qaoDwJvA2YsdsyTpyI2y9HQmg//xXwj8JHBqkut6XRaoVafe6zN/LJuTTCWZmp2d7Q9cknRERll6+jTwYlXNVtWPgIeBXwFea8tJtOf9rf0McMFQ/1UMlqpm2vb8+kF92vLWGcDr8wdSVXdX1ZqqWrNixYoRfiRJ0nyjBMXLwNokp7T7BuuAvcBOYGNrsxF4pG3vBCbbO5kuZHDT+qm2PPVWkrXtPNfP6zN3rmuAJ9p9DEnSMbJ8sR2raneSHcC3gQPAM8DdwGnA9iSbGITJta39niTbgeda+xur6t12uhuA+4CTgcfaA+Be4IEk0wyuJCYXO15J0uIsOigAquoW4JZ55XcYXF0s1H4rsHWB+hRw6QL1t2lBI0kaDz+ZLUnqMigkSV0GhSSpy6CQJHUZFJKkLoNCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1GRSSpC6DQpLUZVBIkroMCklSl0EhSeoyKCRJXQaFJKnLoJAkdRkUkqQug0KS1GVQSJK6DApJUpdBIUnqMigkSV0GhSSpy6CQJHUZFJKkLoNCktQ1UlAk+YkkO5L8W5K9SX45yVlJHk/yQns+c6j9zUmmkzyf5Mqh+uVJnm3H7kiSVj8pyUOtvjvJxCjjlSQduVGvKP4W+HpV/RzwC8BeYAuwq6pWA7vaPkkuBiaBS4D1wJ1JlrXz3AVsBla3x/pW3wS8UVUXAbcDt404XknSEVp0UCQ5Hfg14F6AqvphVf0A2ABsa822AVe37Q3Ag1X1TlW9CEwDVyQ5Hzi9qp6sqgLun9dn7lw7gHVzVxuSpGNjlCuKnwFmgS8leSbJPUlOBc6rqn0A7fnc1n4l8MpQ/5lWW9m259cP6lNVB4A3gbPnDyTJ5iRTSaZmZ2dH+JEkSfONEhTLgU8Ad1XVZcD/0JaZDmGhK4Hq1Ht9Di5U3V1Va6pqzYoVK/qjliQdkVGCYgaYqardbX8Hg+B4rS0n0Z73D7W/YKj/KuDVVl+1QP2gPkmWA2cAr48wZknSEVp0UFTV94FXkvxsK60DngN2AhtbbSPwSNveCUy2dzJdyOCm9VNteeqtJGvb/Yfr5/WZO9c1wBPtPoYk6RhZPmL/PwK+kuRjwHeB32cQPtuTbAJeBq4FqKo9SbYzCJMDwI1V9W47zw3AfcDJwGPtAYMb5Q8kmWZwJTE54nglSUdopKCoqn8F1ixwaN0h2m8Fti5QnwIuXaD+Ni1oJEnj4SezJUldBoUkqcugkCR1GRSSpC6DQpLUZVBIkroMCklSl0EhSeoyKCRJXQaFJKnLoJAkdRkUkqQug0KS1GVQSJK6DApJUpdBIUnqMigkSV0GhSSpy6CQJHUZFJKkLoNCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1GRSSpC6DQpLUZVBIkrpGDooky5I8k+Tv2/5ZSR5P8kJ7PnOo7c1JppM8n+TKofrlSZ5tx+5IklY/KclDrb47ycSo45UkHZmjcUVxE7B3aH8LsKuqVgO72j5JLgYmgUuA9cCdSZa1PncBm4HV7bG+1TcBb1TVRcDtwG1HYbySpCMwUlAkWQVcBdwzVN4AbGvb24Crh+oPVtU7VfUiMA1ckeR84PSqerKqCrh/Xp+5c+0A1s1dbUiSjo1Rryj+Bvgz4H+HaudV1T6A9nxuq68EXhlqN9NqK9v2/PpBfarqAPAmcPb8QSTZnGQqydTs7OyIP5IkadiigyLJZ4D9VfX0B+2yQK069V6fgwtVd1fVmqpas2LFig84HEnSB7F8hL6fBD6b5LeBjwOnJ/ky8FqS86tqX1tW2t/azwAXDPVfBbza6qsWqA/3mUmyHDgDeH2EMUuSjtCiryiq6uaqWlVVEwxuUj9RVdcBO4GNrdlG4JG2vROYbO9kupDBTeun2vLUW0nWtvsP18/rM3eua9prvO+KQpL04RnliuJQbgW2J9kEvAxcC1BVe5JsB54DDgA3VtW7rc8NwH3AycBj7QFwL/BAkmkGVxKTH8J4JUkdRyUoquofgX9s2/8JrDtEu63A1gXqU8ClC9TfpgWNJGk8/GS2JKnLoJAkdRkUkqQug0KS1GVQSJK6DApJUpdBIUnqMigkSV0GhSSpy6CQJHUZFJKkLoNCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1fRh/M1vHmYktj47ldV+69aqxvK6kI+MVhSSpy6CQJHUZFJKkLoNCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1LTooklyQ5B+S7E2yJ8lNrX5WkseTvNCezxzqc3OS6STPJ7lyqH55kmfbsTuSpNVPSvJQq+9OMrH4H1WStBijXFEcAP6kqn4eWAvcmORiYAuwq6pWA7vaPu3YJHAJsB64M8mydq67gM3A6vZY3+qbgDeq6iLgduC2EcYrSVqERQdFVe2rqm+37beAvcBKYAOwrTXbBlzdtjcAD1bVO1X1IjANXJHkfOD0qnqyqgq4f16fuXPtANbNXW1Iko6No3KPoi0JXQbsBs6rqn0wCBPg3NZsJfDKULeZVlvZtufXD+pTVQeAN4GzF3j9zUmmkkzNzs4ejR9JktSMHBRJTgO+Bnyuqv6r13SBWnXqvT4HF6rurqo1VbVmxYoVhxuyJOkIjBQUSX6cQUh8paoebuXX2nIS7Xl/q88AFwx1XwW82uqrFqgf1CfJcuAM4PVRxixJOjKjvOspwL3A3qr666FDO4GNbXsj8MhQfbK9k+lCBjetn2rLU28lWdvOef28PnPnugZ4ot3HkCQdI6P8hbtPAr8HPJvkX1vtC8CtwPYkm4CXgWsBqmpPku3AcwzeMXVjVb3b+t0A3AecDDzWHjAIogeSTDO4kpgcYbySpEVYdFBU1b+w8D0EgHWH6LMV2LpAfQq4dIH627SgkSSNh5/MliR1GRSSpC6DQpLUZVBIkroMCklSl0EhSeoyKCRJXQaFJKnLoJAkdRkUkqQug0KS1GVQSJK6DApJUpdBIUnqMigkSV0GhSSpy6CQJHUZFJKkLoNCktRlUEiSugwKSVLX8nEPQCeuiS2PjuV1X7r1qrG8rnS88opCktRlUEiSugwKSVKXQSFJ6jIoJEldBoUkqcugkCR1GRSSpK7jIiiSrE/yfJLpJFvGPR5JOpEs+U9mJ1kG/B3wG8AM8K0kO6vqufGOTMercX0iHPxUuI5PSz4ogCuA6ar6LkCSB4ENgEGh4844Q2pcDMfj3/EQFCuBV4b2Z4BfGm6QZDOwue3+d5LnR3i9c4D/GKH/R53zc3jO0ZDc9r6S83N445ijnz7UgeMhKLJArQ7aqbobuPuovFgyVVVrjsa5Poqcn8Nzjvqcn8NbanN0PNzMngEuGNpfBbw6prFI0gnneAiKbwGrk1yY5GPAJLBzzGOSpBPGkl96qqoDSf4Q+AawDPhiVe35EF/yqCxhfYQ5P4fnHPU5P4e3pOYoVXX4VpKkE9bxsPQkSRojg0KS1GVQNH5NyPsluSDJPyTZm2RPkpta/awkjyd5oT2fOe6xjlOSZUmeSfL3bd/5aZL8RJIdSf6t/Tv6ZefnYEk+336/vpPkq0k+vtTmyKDgoK8J+S3gYuB3k1w83lEtCQeAP6mqnwfWAje2edkC7Kqq1cCutn8iuwnYO7Tv/Lznb4GvV9XPAb/AYJ6cnybJSuCPgTVVdSmDN+xMssTmyKAY+P+vCamqHwJzXxNyQquqfVX17bb9FoNf8pUM5mZba7YNuHo8Ixy/JKuAq4B7hsrOD5DkdODXgHsBquqHVfUDnJ/5lgMnJ1kOnMLgc2JLao4MioGFviZk5ZjGsiQlmQAuA3YD51XVPhiECXDu+EY2dn8D/Bnwv0M152fgZ4BZ4Ettae6eJKfi/Py/qvoe8FfAy8A+4M2q+iZLbI4MioHDfk3IiSzJacDXgM9V1X+NezxLRZLPAPur6ulxj2WJWg58Arirqi4D/ocTeJlpIe3ewwbgQuAngVOTXDfeUb2fQTHg14QcQpIfZxASX6mqh1v5tSTnt+PnA/vHNb4x+yTw2SQvMViu/PUkX8b5mTMDzFTV7ra/g0FwOD/v+TTwYlXNVtWPgIeBX2GJzZFBMeDXhCwgSRisL++tqr8eOrQT2Ni2NwKPHOuxLQVVdXNVraqqCQb/Zp6oqutwfgCoqu8DryT52VZax+DPAzg/73kZWJvklPb7to7BvcAlNUd+MrtJ8tsM1pvnviZk65iHNHZJfhX4Z+BZ3luD/wKD+xTbgZ9i8A/92qp6fSyDXCKSfAr406r6TJKzcX4ASPKLDG70fwz4LvD7DP6D6vw0Sf4c+B0G7zJ8BvgD4DSW0BwZFJKkLpeeJEldBoUkqcugkCR1GRSSpC6DQpLUZVBIkroMCklS1/8BIsAiS5RzWDcAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Let's see how well your solution performs for the War and Peace\n",
    "cms_list = initialize_k_counters(5, 5000)\n",
    "for word in longer_words_wp:\n",
    "    increment_counters(cms_list, word)\n",
    "\n",
    "discrepencies = []\n",
    "for word in longer_words_wp:\n",
    "    l = approximate_count(cms_list, word)\n",
    "    r = word_freq_wp[word]\n",
    "    assert ( l >= r)\n",
    "    discrepencies.append( l-r )\n",
    "\n",
    "plt.hist(discrepencies)\n",
    "print('Passed all tests: 5 points')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "695a620d4ee55c5fa4aa7da9ff06e626",
     "grade": false,
     "grade_id": "cell-05bbe5025159958a",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Problem 1B\n",
    "\n",
    "Check the data obtained above with calculations along the lines of what was done in class. If we had\n",
    "$5$ banks of counters  with $5000$ counters each and a uniform hash function family, what is the probability that when counting a total of $N = 2.5\\times 10^{5}$ words, we have a discrepency by 80 or more.\n",
    "\n",
    "This problem will not be graded but simply for you to understand the calculations involved."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "be6067bdf327e5f738dbffa50c9ce755",
     "grade": true,
     "grade_id": "cell-8a8072c81e421aee",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "The accuracy of each bank is n/m. Accuracy of combination is (1/m)k.\n",
    "\n",
    "(( 2.5 * 10^5) / 5000 * 80) ~ 5/8 ~ .625\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "47928f051cd28ea645c638e167be3b44",
     "grade": false,
     "grade_id": "cell-344a83e8908d1faf",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 2: Using a Bloom Filter to Count Common Words.\n",
    "\n",
    "In this problem, we will implement a Bloom filter to count how many elements of `longer_words_wp` (the words of length 5 or more in War and Peace) appear in the Great-Gatsby novel.  To do so, we will do the following:\n",
    " - Instantiate a Bloom filter with number of bits `n` and number of hash functions `k`.\n",
    " - Insert all words from great-gatsby into the filter.\n",
    " - For each word from war and peace, check membership in the Bloom filter and count the number of yes answers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "8ddf045e806dbb4e195888e8cd87d73a",
     "grade": false,
     "grade_id": "cell-fae86832b7a1eb5e",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [],
   "source": [
    "class BloomFilter:\n",
    "    def __init__(self, nbits, nhash):\n",
    "        self.bits = [False]*nbits # Initialize all bits to fals\n",
    "        self.m = nbits\n",
    "        self.k = nhash\n",
    "        # get k randdom hash functions\n",
    "        self.hash_fun_reps = [get_random_hash_function() for i in range(self.k)]\n",
    "    \n",
    "    # Function to insert a word in a Bloom filter.\n",
    "    def insert(self, word):\n",
    "        for l in range(k):\n",
    "            i = (hash_string(self.hash_fun_reps[l],word)%self.m)\n",
    "            self.bits[i] = 1\n",
    "        \n",
    "    # Check if a word belongs to the Bloom Filter\n",
    "    def member(self, word):\n",
    "        for l in range(k):\n",
    "            i = (hash_string(self.hash_fun_reps[l],word)%self.m)\n",
    "            if self.bits[i] != 1:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "3e6d8bde939a16edca749ffe1098aa91",
     "grade": false,
     "grade_id": "cell-92fcbb197bfe3661",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exact common word count = 124595\n"
     ]
    }
   ],
   "source": [
    "#do the exact count\n",
    "# it is a measure of how optimized python data structures are under the hood that\n",
    "# this operation finishes very quickly.\n",
    "all_words_gg = set(longer_words_gg)\n",
    "exact_common_wc = 0\n",
    "for word in longer_words_wp:\n",
    "    if word in all_words_gg:\n",
    "        exact_common_wc = exact_common_wc + 1\n",
    "print(f'Exact common word count = {exact_common_wc}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "code",
     "checksum": "350ca6a04e5883ce24905f0268d0fc12",
     "grade": true,
     "grade_id": "cell-c43547e8c520ff88",
     "locked": true,
     "points": 10,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of common words of length >= 5 equals : 125345\n",
      "All Tests Passed: 10 points\n"
     ]
    }
   ],
   "source": [
    "# Try to use the same using a bloom filter.\n",
    "bf = BloomFilter(100000, 5)\n",
    "for word in longer_words_gg:\n",
    "    bf.insert(word)\n",
    "    \n",
    "for word in longer_words_gg:\n",
    "    assert (bf.member(word)), f'Word: {word} should be a member'\n",
    "\n",
    "common_word_count = 0\n",
    "for word in longer_words_wp:\n",
    "    if bf.member(word):\n",
    "        common_word_count= common_word_count + 1\n",
    "print(f'Number of common words of length >= 5 equals : {common_word_count}')\n",
    "assert ( common_word_count >= exact_common_wc)\n",
    "print('All Tests Passed: 10 points')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "a058c200be3f1999b4e8b74116969230",
     "grade": false,
     "grade_id": "cell-686a6bc365e25c35",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Problem 2 B\n",
    "\n",
    "Given a Bloom filter with $m = 100000$ bits and $k = 5$ hash functions that  map each key uniformly at random to one of the bits (assumption), estimate the probability that $k$ bits $i_1, \\ldots, i_k$ are simultaneously set when $n = 10000$ words are inserted. Assume that whether or not a particular bit is set is independent of another."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "6d5522eb5b7340b3e1613d6842b41160",
     "grade": true,
     "grade_id": "cell-be6d976534e0936c",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "Probability of any bit not being set = (1-(1/m))^kn \n",
    "\n",
    "(1-(1/100000))^(5*10000) = .6065291\n",
    "\n",
    "Probability of all 5 not being turned on is (1-.6065291)^5 = .00943 (A little under 1%)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "5d5d44dcb9fc84475835cb3bc34b5246",
     "grade": false,
     "grade_id": "cell-80241300e0a5159c",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Manually Graded Solutions\n",
    "\n",
    "### Problem 1 B \n",
    "\n",
    "\n",
    "Note that for each word we have $\\mathbb{E}( \\text{approxCount}(word) - \\text{count}(word)) \\leq \\frac{N}{m}$.\n",
    "The probability that for some word, the approximate count differs from the real one by at least $80$ for one of the counter banks is bounded by Markov Inequality as:  \n",
    "$$ \\mathbb{P}( \\text{approxCount}(word) - \\text{count}(word) \\geq 80) \\leq \\frac{\\mathbb{E}(\\text{approxCount}(word) - \\text{count}(word))}{80} \\leq \\frac{2.5\\times 10^5}{80 \\times 5000} \\approx \\frac{5}{8} $$.\n",
    "\n",
    "The probability that this happens for all five counter banks is bounded by $\\left(\\frac{5}{8}\\right)^5 \\approx 0.095$.\n",
    "\n",
    "\n",
    "However, this bound happens to be not so tight. Empirically, we see that this happens for roughly one word out of the nearly quarter million words in the corpus.\n",
    "\n",
    "### Problem 2 B\n",
    "\n",
    "The probability that any given bit is not set when $n$ words are inserted is \n",
    "$(1 - \\frac{1}{m})^{kn} = (1 - \\frac{1}{100000})^{5\\times 10000} = e^{-0.5}$.\n",
    "\n",
    "The probability that all five bits are simultaneously set is $(1-e^{-0.5})^5 = 0.009$.\n",
    "\n",
    "Therefore, we will expect the false positive rate to be roughly $1\\%$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "21327ec3f51109e1a65a2b7541dd1139",
     "grade": false,
     "grade_id": "cell-e24134f3086d63a4",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## That's All Folks!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}