Hash Applications.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": null,
   "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",
    "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",
    "\n"
   ]
  },
  {
   "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": null,
   "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": 13,
   "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",
    "from __future__ import annotations\n",
    "from typing import List\n",
    "\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",
    "    \n",
    "    def get_hash(self, word: int) -> int:\n",
    "        raw_hash: int = hash_string(self.hash_fun_rep, word)\n",
    "        return raw_hash % self.m\n",
    "    \n",
    "    \n",
    "    # function: increment \n",
    "    # given a word, increment its count in the countmin sketch\n",
    "    def increment(self, word: str) -> None:\n",
    "        \n",
    "        word_hash: int = self.get_hash(word)\n",
    "        self.counters[word_hash] += 1\n",
    "        \n",
    "    # function: approximateCount\n",
    "    # Given a word, get its approximate count\n",
    "    def approximateCount(self, word) -> int:\n",
    "        \n",
    "        word_hash: int = self.get_hash(word)\n",
    "        return self.counters[word_hash]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "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",
    "    \n",
    "    for cms in count_min_sketches:\n",
    "        cms.increment(word)\n",
    "    return count_min_sketches\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": 15,
   "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": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAD6CAYAAACh4jDWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAQhUlEQVR4nO3df6zd9V3H8efLdjLGxJVxIayt3s7UH9DMbdzU6syyyJQqxjIj2iWTakiqyJQZE1f2D9OkSV3mMolCUseknZPasCmNrLrajcwlSHfL0FI6pBkV7lrbO8k28A8m3ds/zod4dnvube895Z5zuc9HcnK+532+n+/33U+AV78/zpdUFZIkfc+gG5AkDQcDQZIEGAiSpMZAkCQBBoIkqTEQJEnAOQRCko8nOZXksa7aJUn2JXmyvS/r+u62JEeTPJHk2q761UkOte/uSJJWvyDJ37b6w0lGz+8fUZJ0LnK23yEkeTvwPLCzqta02oeAZ6tqW5ItwLKqen+SK4F7gbXAG4B/Bn64qk4nOQDcCvwr8Bngjqram+R3gDdV1W8n2Qi8q6p+7WyNX3rppTU6OjrHP7YkLU4HDx78elWN9Ppu6dkGV9UXevytfQPwjra8A3gQeH+r76qqF4CnkhwF1iY5BlxcVQ8BJNkJXA/sbWM+2LZ1H/DnSVJnSarR0VHGx8fP1r4kqUuS/5zuu7leQ7i8qk4AtPfLWn058EzXehOttrwtT61/15iqehH4JvD6OfYlSZqj831ROT1qNUN9pjFnbjzZnGQ8yfjk5OQcW5Qk9TLXQDiZ5AqA9n6q1SeAlV3rrQCOt/qKHvXvGpNkKfD9wLO9dlpV26tqrKrGRkZ6ngKTJM3RXANhD7CpLW8C7u+qb2x3Dq0CVgMH2mml55Ksa3cX3ThlzEvb+hXgc2e7fiBJOv/OelE5yb10LiBfmmQCuB3YBuxOchPwNHADQFUdTrIbeBx4Ebilqk63Td0M3ANcSOdi8t5Wvxv4RLsA/Syw8bz8ySRJs3LW206H1djYWHmXkSTNTpKDVTXW6zt/qSxJAgwESVJjIEiSgHO4qKxXhtEtDwxs38e2XTewfUs6dx4hSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJjYEgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1BoIkCTAQJEmNgSBJAgwESVJjIEiSAANBktQYCJIkwECQJDUGgiQJMBAkSY2BIEkCDARJUmMgSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJTV+BkOT3kxxO8liSe5O8OsklSfYlebK9L+ta/7YkR5M8keTarvrVSQ617+5Ikn76kiTN3pwDIcly4PeAsapaAywBNgJbgP1VtRrY3z6T5Mr2/VXAeuDOJEva5u4CNgOr22v9XPuSJM1Nv6eMlgIXJlkKvAY4DmwAdrTvdwDXt+UNwK6qeqGqngKOAmuTXAFcXFUPVVUBO7vGSJLmyZwDoaq+BnwYeBo4AXyzqj4LXF5VJ9o6J4DL2pDlwDNdm5hoteVteWpdkjSP+jlltIzO3/pXAW8ALkrynpmG9KjVDPVe+9ycZDzJ+OTk5GxbliTNoJ9TRu8Enqqqyar6X+DTwE8BJ9tpINr7qbb+BLCya/wKOqeYJtry1PoZqmp7VY1V1djIyEgfrUuSpuonEJ4G1iV5Tbsr6BrgCLAH2NTW2QTc35b3ABuTXJBkFZ2LxwfaaaXnkqxr27mxa4wkaZ4snevAqno4yX3AI8CLwJeB7cBrgd1JbqITGje09Q8n2Q083ta/papOt83dDNwDXAjsbS9J0jyacyAAVNXtwO1Tyi/QOVrotf5WYGuP+jiwpp9eJEn98ZfKkiTAQJAkNQaCJAkwECRJjYEgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1BoIkCTAQJEmNgSBJAgwESVJjIEiSAANBktQYCJIkwECQJDUGgiQJMBAkSY2BIEkCDARJUmMgSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJjYEgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1fQVCktcluS/JV5IcSfKTSS5Jsi/Jk+19Wdf6tyU5muSJJNd21a9Ocqh9d0eS9NOXJGn2+j1C+DPgH6vqR4EfB44AW4D9VbUa2N8+k+RKYCNwFbAeuDPJkradu4DNwOr2Wt9nX5KkWZpzICS5GHg7cDdAVX27qr4BbAB2tNV2ANe35Q3Arqp6oaqeAo4Ca5NcAVxcVQ9VVQE7u8ZIkuZJP0cIbwQmgb9K8uUkH0tyEXB5VZ0AaO+XtfWXA890jZ9oteVteWpdkjSP+gmEpcBbgbuq6i3A/9BOD02j13WBmqF+5gaSzUnGk4xPTk7Otl9J0gz6CYQJYKKqHm6f76MTECfbaSDa+6mu9Vd2jV8BHG/1FT3qZ6iq7VU1VlVjIyMjfbQuSZpqzoFQVf8FPJPkR1rpGuBxYA+wqdU2Afe35T3AxiQXJFlF5+LxgXZa6bkk69rdRTd2jZEkzZOlfY7/XeCTSb4X+Crwm3RCZneSm4CngRsAqupwkt10QuNF4JaqOt22czNwD3AhsLe9JEnzqK9AqKpHgbEeX10zzfpbga096uPAmn56kST1x18qS5IAA0GS1BgIkiTAQJAkNQaCJAkwECRJjYEgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1BoIkCTAQJEmNgSBJAgwESVJjIEiSAANBktQYCJIkoM//p7Jmb3TLA4NuQZJ68ghBkgQYCJKkxkCQJAEGgiSpMRAkSYCBIElqDARJEmAgSJIaA0GSBBgIkqTGQJAkAQaCJKkxECRJgIEgSWr6DoQkS5J8Ock/tM+XJNmX5Mn2vqxr3duSHE3yRJJru+pXJznUvrsjSfrtS5I0O+fjCOFW4EjX5y3A/qpaDexvn0lyJbARuApYD9yZZEkbcxewGVjdXuvPQ1+SpFnoKxCSrACuAz7WVd4A7GjLO4Dru+q7quqFqnoKOAqsTXIFcHFVPVRVBezsGiNJmif9HiF8FPhD4Dtdtcur6gRAe7+s1ZcDz3StN9Fqy9vy1LokaR7NORCS/CJwqqoOnuuQHrWaod5rn5uTjCcZn5ycPMfdSpLORT9HCG8DfinJMWAX8DNJ/ho42U4D0d5PtfUngJVd41cAx1t9RY/6Gapqe1WNVdXYyMhIH61LkqaacyBU1W1VtaKqRulcLP5cVb0H2ANsaqttAu5vy3uAjUkuSLKKzsXjA+200nNJ1rW7i27sGiNJmidLX4ZtbgN2J7kJeBq4AaCqDifZDTwOvAjcUlWn25ibgXuAC4G97SVJmkfnJRCq6kHgwbb838A106y3Fdjaoz4OrDkfvUiS5ublOEKQvsvolgcGst9j264byH6lhcpHV0iSAANBktQYCJIkwECQJDUGgiQJMBAkSY2BIEkCDARJUmMgSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJjYEgSQIMBElSYyBIkgADQZLUGAiSJMBAkCQ1BoIkCTAQJEmNgSBJAgwESVJjIEiSAANBktQYCJIkwECQJDUGgiQJMBAkSY2BIEkCDARJUmMgSJKAPgIhycokn09yJMnhJLe2+iVJ9iV5sr0v6xpzW5KjSZ5Icm1X/eokh9p3dyRJf38sSdJs9XOE8CLwB1X1Y8A64JYkVwJbgP1VtRrY3z7TvtsIXAWsB+5MsqRt6y5gM7C6vdb30ZckaQ7mHAhVdaKqHmnLzwFHgOXABmBHW20HcH1b3gDsqqoXquop4CiwNskVwMVV9VBVFbCza4wkaZ6cl2sISUaBtwAPA5dX1QnohAZwWVttOfBM17CJVlvelqfWJUnzqO9ASPJa4FPA+6rqWzOt2qNWM9R77WtzkvEk45OTk7NvVpI0rb4CIcmr6ITBJ6vq0618sp0Gor2favUJYGXX8BXA8VZf0aN+hqraXlVjVTU2MjLST+uSpCn6ucsowN3Akar6SNdXe4BNbXkTcH9XfWOSC5KsonPx+EA7rfRcknVtmzd2jZEkzZOlfYx9G/DrwKEkj7baB4BtwO4kNwFPAzcAVNXhJLuBx+ncoXRLVZ1u424G7gEuBPa2lyRpHs05EKrqi/Q+/w9wzTRjtgJbe9THgTVz7UWS1D9/qSxJAgwESVJjIEiSAANBktQYCJIkwECQJDX9/A5BGmqjWx4YyH6PbbtuIPuV+uURgiQJMBAkSY2BIEkCDARJUmMgSJIAA0GS1BgIkiTAQJAkNQaCJAkwECRJzaJ8dMWgHmkgScPMIwRJEmAgSJIaA0GSBBgIkqTGQJAkAQaCJKkxECRJgIEgSWoMBEkSYCBIkppF+egK6eU0yEejHNt23cD2rYXPIwRJEmAgSJIaA0GSBBgIkqTGQJAkAUMUCEnWJ3kiydEkWwbdjyQtNkNx22mSJcBfAD8LTABfSrKnqh4fbGfSwjKoW1693fWVYViOENYCR6vqq1X1bWAXsGHAPUnSojIURwjAcuCZrs8TwE8MqBdJs+SP8V4ZhiUQ0qNWZ6yUbAY2t4/PJ3lijvu7FPj6HMcOij3Pj4XW80LrF85zz/mT87WlGb2S5vkHpxswLIEwAazs+rwCOD51paraDmzvd2dJxqtqrN/tzCd7nh8LreeF1i/Y83yZS8/Dcg3hS8DqJKuSfC+wEdgz4J4kaVEZiiOEqnoxyXuBfwKWAB+vqsMDbkuSFpWhCASAqvoM8Jl52l3fp50GwJ7nx0LreaH1C/Y8X2bdc6rOuHYrSVqEhuUagiRpwBZdICzER2QkOZbkUJJHk4wPup9eknw8yakkj3XVLkmyL8mT7X3ZIHvsNk2/H0zytTbPjyb5hUH2OFWSlUk+n+RIksNJbm31oZznGfod2nlO8uokB5L8W+v5j1p9KOcYZux51vO8qE4ZtUdk/Addj8gA3j3sj8hIcgwYq6qhvQ86yduB54GdVbWm1T4EPFtV21r4Lquq9w+yz5dM0+8Hgeer6sOD7G06Sa4ArqiqR5J8H3AQuB74DYZwnmfo91cZ0nlOEuCiqno+yauALwK3Ar/MEM4xzNjzemY5z4vtCMFHZLxMquoLwLNTyhuAHW15B53/GAyFafodalV1oqoeacvPAUfo/Mp/KOd5hn6HVnU83z6+qr2KIZ1jmLHnWVtsgdDrERlD/Q9oU8Bnkxxsv9ZeKC6vqhPQ+Y8DcNmA+zkX703y7+2U0tCcFpgqySjwFuBhFsA8T+kXhniekyxJ8ihwCthXVUM/x9P0DLOc58UWCOf0iIwh9Laqeivw88At7XSHzr+7gB8C3gycAP50sO30luS1wKeA91XVtwbdz9n06Heo57mqTlfVm+k8MWFtkjWD7ulspul51vO82ALhnB6RMWyq6nh7PwX8HZ1TXwvByXYe+aXzyacG3M+Mqupk+xfrO8BfMoTz3M4Rfwr4ZFV9upWHdp579bsQ5hmgqr4BPEjnXPzQznG37p7nMs+LLRAW3CMyklzULsiR5CLg54DHZh41NPYAm9ryJuD+AfZyVi/9C9+8iyGb53bx8G7gSFV9pOuroZzn6fod5nlOMpLkdW35QuCdwFcY0jmG6XueyzwvqruMANqtVx/l/x+RsXXALc0oyRvpHBVA55flfzOMPSe5F3gHnScsngRuB/4e2A38APA0cENVDcWF3Gn6fQedw+sCjgG/9dJ542GQ5KeBfwEOAd9p5Q/QOS8/dPM8Q7/vZkjnOcmb6Fw0XkLnL8y7q+qPk7yeIZxjmLHnTzDLeV50gSBJ6m2xnTKSJE3DQJAkAQaCJKkxECRJgIEgSWoMBEkSYCBIkhoDQZIEwP8BG+RN/T0GzKsAAAAASUVORK5CYII=",
      "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": null,
   "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": "iVBORw0KGgoAAAANSUhEUgAAAZEAAAD4CAYAAAAtrdtxAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAULUlEQVR4nO3dcayd9X3f8fdndkNIIqgBg4jNZiqstmCtS7GI20xVNFfBLSzmD1Bv1Awr9WQNsYVUnTq7nYTWzhJoVWiZBhIKFEMzwHKjYTWjiWVapZOoySVUIsZl3AUGLi6+rQllnSA1/e6P87vL8c31tfmda47t+35JR+d5vs/ze57fz8D58Dy/5xynqpAkqcc/GHcHJElnLkNEktTNEJEkdTNEJEndDBFJUrel4+7AQrvoootq1apV4+6GJJ1Rnnnmmb+qquXvtd1ZFyKrVq1icnJy3N2QpDNKkv/d087bWZKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuJ/zGepIHgOuBw1W1ptX+E/DPge8B/wv4XFV9t23bBmwG3gU+X1Vfa/WrgQeBc4H/DtxWVZXkHOAh4Grgr4FfqKqXW5tNwL9vXfmPVbVjAcY8r1Vbv3qqTzGnl++4biznlaRRnMyVyIPAhlm1PcCaqvrHwP8EtgEkuRKYAK5qbe5JsqS1uRfYAqxur5ljbgbeqKorgLuAO9uxLgBuBz4OXAPcnmTZex+iJOlUOWGIVNU3gCOzal+vqqNt9U+BlW15I/BoVb1TVS8BU8A1SS4Fzquqp2rw9/E+BNww1GbmCmMXsD5JgGuBPVV1pKreYBBcs8NMkjRGCzEn8kvAE215BfDq0LaDrbaiLc+uH9OmBdObwIXzHOsHJNmSZDLJ5PT09EiDkSSdvJFCJMmvA0eBL8+U5tit5qn3tjm2WHVfVa2tqrXLl7/nXzKWJHXqDpE26X098IvtFhUMrhYuG9ptJfBaq6+co35MmyRLgfMZ3D473rEkSaeJrhBJsgH4d8Cnq+r/Dm3aDUwkOSfJ5Qwm0J+uqkPAW0nWtfmOm4HHh9psass3Ak+2UPoa8Kkky9qE+qdaTZJ0mjiZR3wfAT4JXJTkIIMnprYB5wB7BpnAn1bVv6qq/Ul2As8zuM11a1W92w51C99/xPcJvj+Pcj/wcJIpBlcgEwBVdSTJbwLfbPv9RlUdM8EvSRqvE4ZIVX1mjvL98+y/Hdg+R30SWDNH/W3gpuMc6wHggRP1UZI0Hn5jXZLUzRCRJHUzRCRJ3QwRSVI3Q0SS1M0QkSR1M0QkSd0MEUlSN0NEktTNEJEkdTNEJEndDBFJUjdDRJLUzRCRJHUzRCRJ3QwRSVI3Q0SS1M0QkSR1M0QkSd0MEUlSN0NEktTNEJEkdTNEJEndDBFJUjdDRJLU7YQhkuSBJIeTfHuodkGSPUlebO/LhrZtSzKV5IUk1w7Vr07yXNt2d5K0+jlJHmv1fUlWDbXZ1M7xYpJNCzVoSdLCOJkrkQeBDbNqW4G9VbUa2NvWSXIlMAFc1drck2RJa3MvsAVY3V4zx9wMvFFVVwB3AXe2Y10A3A58HLgGuH04rCRJ43fCEKmqbwBHZpU3Ajva8g7ghqH6o1X1TlW9BEwB1yS5FDivqp6qqgIemtVm5li7gPXtKuVaYE9VHamqN4A9/GCYSZLGqHdO5JKqOgTQ3i9u9RXAq0P7HWy1FW15dv2YNlV1FHgTuHCeY/2AJFuSTCaZnJ6e7hySJOm9WuiJ9cxRq3nqvW2OLVbdV1Vrq2rt8uXLT6qjkqTR9YbI6+0WFe39cKsfBC4b2m8l8Fqrr5yjfkybJEuB8xncPjvesSRJp4neENkNzDwttQl4fKg+0Z64upzBBPrT7ZbXW0nWtfmOm2e1mTnWjcCTbd7ka8CnkixrE+qfajVJ0mli6Yl2SPII8EngoiQHGTwxdQewM8lm4BXgJoCq2p9kJ/A8cBS4tarebYe6hcGTXucCT7QXwP3Aw0mmGFyBTLRjHUnym8A3236/UVWzJ/glSWN0whCpqs8cZ9P64+y/Hdg+R30SWDNH/W1aCM2x7QHggRP1UZI0Hn5jXZLUzRCRJHUzRCRJ3QwRSVI3Q0SS1M0QkSR1O+Ejvnp/rNr61bGd++U7rhvbuSWd2bwSkSR1M0QkSd0MEUlSN0NEktTNEJEkdTNEJEndDBFJUjdDRJLUzRCRJHUzRCRJ3QwRSVI3Q0SS1M0QkSR1M0QkSd0MEUlSN0NEktTNEJEkdTNEJEndRgqRJL+cZH+Sbyd5JMkHk1yQZE+SF9v7sqH9tyWZSvJCkmuH6lcnea5tuztJWv2cJI+1+r4kq0bpryRpYXWHSJIVwOeBtVW1BlgCTABbgb1VtRrY29ZJcmXbfhWwAbgnyZJ2uHuBLcDq9trQ6puBN6rqCuAu4M7e/kqSFt6ot7OWAucmWQp8CHgN2AjsaNt3ADe05Y3Ao1X1TlW9BEwB1yS5FDivqp6qqgIemtVm5li7gPUzVymSpPHrDpGq+gvgt4BXgEPAm1X1deCSqjrU9jkEXNyarABeHTrEwVZb0ZZn149pU1VHgTeBC2f3JcmWJJNJJqenp3uHJEl6j0a5nbWMwZXC5cBHgQ8n+ex8Teao1Tz1+docW6i6r6rWVtXa5cuXz99xSdKCGeV21s8CL1XVdFX9HfAV4KeB19stKtr74bb/QeCyofYrGdz+OtiWZ9ePadNumZ0PHBmhz5KkBTRKiLwCrEvyoTZPsR44AOwGNrV9NgGPt+XdwER74upyBhPoT7dbXm8lWdeOc/OsNjPHuhF4ss2bSJJOA0t7G1bVviS7gG8BR4FngfuAjwA7k2xmEDQ3tf33J9kJPN/2v7Wq3m2HuwV4EDgXeKK9AO4HHk4yxeAKZKK3v5KkhdcdIgBVdTtw+6zyOwyuSubafzuwfY76JLBmjvrbtBCSJJ1+/Ma6JKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkroZIpKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkroZIpKkboaIJKnbSCGS5IeT7Ery50kOJPmpJBck2ZPkxfa+bGj/bUmmkryQ5Nqh+tVJnmvb7k6SVj8nyWOtvi/JqlH6K0laWKNeifwO8IdV9WPATwAHgK3A3qpaDext6yS5EpgArgI2APckWdKOcy+wBVjdXhtafTPwRlVdAdwF3DlifyVJC6g7RJKcB/wMcD9AVX2vqr4LbAR2tN12ADe05Y3Ao1X1TlW9BEwB1yS5FDivqp6qqgIemtVm5li7gPUzVymSpPEb5UrkR4Bp4HeTPJvkS0k+DFxSVYcA2vvFbf8VwKtD7Q+22oq2PLt+TJuqOgq8CVw4uyNJtiSZTDI5PT09wpAkSe/FKCGyFPhJ4N6q+hjwt7RbV8cx1xVEzVOfr82xhar7qmptVa1dvnz5/L2WJC2YUULkIHCwqva19V0MQuX1douK9n54aP/LhtqvBF5r9ZVz1I9pk2QpcD5wZIQ+S5IWUHeIVNVfAq8m+dFWWg88D+wGNrXaJuDxtrwbmGhPXF3OYAL96XbL660k69p8x82z2swc60bgyTZvIkk6DSwdsf2/Ab6c5APAd4DPMQimnUk2A68ANwFU1f4kOxkEzVHg1qp6tx3nFuBB4FzgifaCwaT9w0mmGFyBTIzYX0nSAhopRKrqz4C1c2xaf5z9twPb56hPAmvmqL9NCyFJ0unHb6xLkroZIpKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkroZIpKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkrqNHCJJliR5NskftPULkuxJ8mJ7Xza077YkU0leSHLtUP3qJM+1bXcnSaufk+SxVt+XZNWo/ZUkLZyFuBK5DTgwtL4V2FtVq4G9bZ0kVwITwFXABuCeJEtam3uBLcDq9trQ6puBN6rqCuAu4M4F6K8kaYGMFCJJVgLXAV8aKm8EdrTlHcANQ/VHq+qdqnoJmAKuSXIpcF5VPVVVBTw0q83MsXYB62euUiRJ4zfqlchvA78K/P1Q7ZKqOgTQ3i9u9RXAq0P7HWy1FW15dv2YNlV1FHgTuHB2J5JsSTKZZHJ6enrEIUmSTlZ3iCS5HjhcVc+cbJM5ajVPfb42xxaq7quqtVW1dvny5SfZHUnSqJaO0PYTwKeT/DzwQeC8JL8HvJ7k0qo61G5VHW77HwQuG2q/Enit1VfOUR9uczDJUuB84MgIfZYkLaDuK5Gq2lZVK6tqFYMJ8yer6rPAbmBT220T8Hhb3g1MtCeuLmcwgf50u+X1VpJ1bb7j5lltZo51YzvHD1yJSJLGY5QrkeO5A9iZZDPwCnATQFXtT7ITeB44CtxaVe+2NrcADwLnAk+0F8D9wMNJphhcgUycgv5KkjotSIhU1R8Df9yW/xpYf5z9tgPb56hPAmvmqL9NCyFJ0unHb6xLkroZIpKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkroZIpKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkrp1h0iSy5L8UZIDSfYnua3VL0iyJ8mL7X3ZUJttSaaSvJDk2qH61Umea9vuTpJWPyfJY62+L8mq/qFKkhbaKFciR4FfqaofB9YBtya5EtgK7K2q1cDetk7bNgFcBWwA7kmypB3rXmALsLq9NrT6ZuCNqroCuAu4c4T+SpIWWHeIVNWhqvpWW34LOACsADYCO9puO4Ab2vJG4NGqeqeqXgKmgGuSXAqcV1VPVVUBD81qM3OsXcD6masUSdL4LcicSLvN9DFgH3BJVR2CQdAAF7fdVgCvDjU72Gor2vLs+jFtquoo8CZw4Rzn35JkMsnk9PT0QgxJknQSRg6RJB8Bfh/4QlX9zXy7zlGreerztTm2UHVfVa2tqrXLly8/UZclSQtkpBBJ8kMMAuTLVfWVVn693aKivR9u9YPAZUPNVwKvtfrKOerHtEmyFDgfODJKnyVJC2dpb8M2N3E/cKCqvji0aTewCbijvT8+VP+vSb4IfJTBBPrTVfVukreSrGNwO+xm4D/POtZTwI3Ak23eRAto1davjuW8L99x3VjOK2nhdIcI8AngXwDPJfmzVvs1BuGxM8lm4BXgJoCq2p9kJ/A8gye7bq2qd1u7W4AHgXOBJ9oLBiH1cJIpBlcgEyP0V5K0wLpDpKr+B3PPWQCsP06b7cD2OeqTwJo56m/TQkiSdPrxG+uSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkroZIpKkboaIJKmbISJJ6maISJK6GSKSpG6GiCSpmyEiSepmiEiSuhkikqRuhogkqZshIknqZohIkroZIpKkbkvH3QEtXqu2fnUs5335juvGcl7pbOSViCSpmyEiSepmiEiSup0RIZJkQ5IXkkwl2Tru/kiSBk77EEmyBPgvwM8BVwKfSXLleHslSYIz4+msa4CpqvoOQJJHgY3A82Ptlc5Y43oqbJx8Ik2nypkQIiuAV4fWDwIfH94hyRZgS1v9P0leGOF8FwF/NUL7M5ljP0vlzhPuclaP/wQW89jh++P/Rz2Nz4QQyRy1Omal6j7gvgU5WTJZVWsX4lhnGse+OMcOi3v8i3nsMPr4T/s5EQZXHpcNra8EXhtTXyRJQ86EEPkmsDrJ5Uk+AEwAu8fcJ0kSZ8DtrKo6muRfA18DlgAPVNX+U3jKBbktdoZy7IvXYh7/Yh47jDj+VNWJ95IkaQ5nwu0sSdJpyhCRJHUzRJrF9NMqSS5L8kdJDiTZn+S2Vr8gyZ4kL7b3ZePu66mUZEmSZ5P8QVtfFONP8sNJdiX58/bvwE8tlrEDJPnl9u/9t5M8kuSDZ+v4kzyQ5HCSbw/VjjvWJNvaZ+ALSa49mXMYIizKn1Y5CvxKVf04sA64tY13K7C3qlYDe9v62ew24MDQ+mIZ/+8Af1hVPwb8BIM/g0Ux9iQrgM8Da6tqDYOHdSY4e8f/ILBhVm3OsbbPgAngqtbmnvbZOC9DZOD//7RKVX0PmPlplbNSVR2qqm+15bcYfIisYDDmHW23HcAN4+nhqZdkJXAd8KWh8lk//iTnAT8D3A9QVd+rqu+yCMY+ZClwbpKlwIcYfO/srBx/VX0DODKrfLyxbgQerap3quolYIrBZ+O8DJGBuX5aZcWY+vK+SrIK+BiwD7ikqg7BIGiAi8fXs1Put4FfBf5+qLYYxv8jwDTwu+1W3peSfJjFMXaq6i+A3wJeAQ4Bb1bV11kk42+ON9auz0FDZOCEP61yNkryEeD3gS9U1d+Muz/vlyTXA4er6plx92UMlgI/CdxbVR8D/paz59bNCbX7/xuBy4GPAh9O8tnx9uq00fU5aIgMLLqfVknyQwwC5MtV9ZVWfj3JpW37pcDhcfXvFPsE8OkkLzO4dfnPkvwei2P8B4GDVbWvre9iECqLYewAPwu8VFXTVfV3wFeAn2bxjB+OP9auz0FDZGBR/bRKkjC4J36gqr44tGk3sKktbwIef7/79n6oqm1VtbKqVjH4Z/1kVX2WRTD+qvpL4NUkP9pK6xn8tQpn/dibV4B1ST7U/jtYz2BOcLGMH44/1t3ARJJzklwOrAaePtHB/MZ6k+TnGdwnn/lple1j7tIpk+SfAn8CPMf35wR+jcG8yE7gHzL4j+2mqpo9KXdWSfJJ4N9W1fVJLmQRjD/JP2HwQMEHgO8An2PwP5Rn/dgBkvwH4BcYPKX4LPAvgY9wFo4/ySPAJxn83PvrwO3Af+M4Y03y68AvMfiz+UJVPXHCcxgikqRe3s6SJHUzRCRJ3QwRSVI3Q0SS1M0QkSR1M0QkSd0MEUlSt/8HGQ5Avo/eQcgAAAAASUVORK5CYII=",
      "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": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "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": null,
   "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": [
    "from __future__ import annotations\n",
    "from typing import List\n",
    "\n",
    "class BloomFilter:\n",
    "    def __init__(self, nbits, nhash):\n",
    "        self.bits: List[bool] = [False]*nbits # Initialize all bits to fals\n",
    "        self.m: int = nbits\n",
    "        self.k: int = nhash\n",
    "        # get k randdom hash functions\n",
    "        self.hash_fun_reps: List[(int, int, int)] = \\\n",
    "            [get_random_hash_function() for i in range(self.k)] \n",
    "            \n",
    "    def get_hash(self, hash_fun_rep: (int, int, int), word: int) -> int:\n",
    "        raw_hash: int = hash_string(hash_fun_rep, word) \n",
    "        return raw_hash % self.m\n",
    "    \n",
    "    # Function to insert a word in a Bloom filter.\n",
    "    def insert(self, word) -> None:\n",
    "        \n",
    "        for _k in range(self.k):\n",
    "            word_hash = self.get_hash(self.hash_fun_reps[_k], word)\n",
    "            self.bits[word_hash] = True\n",
    "            \n",
    "        \n",
    "    # Check if a word belongs to the Bloom Filter\n",
    "    def member(self, word) -> bool:\n",
    "              \n",
    "        word_hashes: List[int] = [self.get_hash(self.hash_fun_reps[_k], word) for _k in range(self.k)]\n",
    "        return all([self.bits[num_bit] for num_bit in word_hashes])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "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": 24,
   "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 : 125232\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": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "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
}