assignment1/Assignment1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Assignment1.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 2",
      "language": "python",
      "name": "python2"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "[View in Colaboratory](https://colab.research.google.com/github/janchorowski/nn_assignments/blob/nn18/assignment1/Assignment1.ipynb)"
      ]
    },
    {
      "metadata": {
        "id": "P7IFJ5_Y33-8",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Assignment 1\n"
      ]
    },
    {
      "metadata": {
        "id": "goqGXGZT2DKK",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Important notes"
      ]
    },
    {
      "metadata": {
        "id": "-3FKET1A2GRK",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Submission deadline:**\n",
        "* **Problems 1-4: last lab session before or on Friday, 19.10.18**\n",
        "* **Problems 5-6: last lab session before or on Friday, 26.10.18**\n",
        "\n",
        "**Points: 10 + 4 bonus points**\n",
        "\n",
        "Please note: some of the assignments are tedious or boring if you are already a NumPy ninja. The bonus problems were designed to give you a more satisfying alternative.\n",
        "\n",
        "The assignment is in the form of a Jupyter notebook. We will be using [Google Colab](https://colab.research.google.com) to solve it. Below you will find a \"Setup\" section. Follow instructions from this paragraph to download the notebook and open it using [Google Colab](https://colab.research.google.com). \n",
        "\n",
        "Your goal is to solve problems posted below. Whenever possible, add your solutions to the notebook.\n",
        "\n",
        "Please email us about any problems with it - we will try to correct them quickly. Also, please do not hesitate to use GitHub’s pull requests to send us corrections!"
      ]
    },
    {
      "metadata": {
        "id": "1CMDOrsc2K-K",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Setup"
      ]
    },
    {
      "metadata": {
        "id": "tNjavUUC7yuM",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### 1. Open the notebook using Google Colab\n",
        "\n",
        "1. From Github: Click on \"View in Colaboratory\", then save to your Google Drive.\n",
        "2. Alternatively upload manually to Drive:\n",
        "  1. Download the notebook or clone https://github.com/janchorowski/nn_assignments.\n",
        "  2. Go to  [Google Colab](https://colab.research.google.com).\n",
        "  3. Go to \"UPLOAD\" tab and select a local copy of the notebook that you downloaded in point 1.\n",
        "  \n",
        "Colab Tips:\n",
        "1. Set tab width to 4 spaces under `Tools -> Preferences`.\n",
        "  \n",
        "### 2. Open the notebook offline using Jupyter/IPython\n",
        "\n",
        "This notebook can be opened using Jupyter notebook. Simply install a scientific Python distribution on your computer (e.g. [Anaconda](https://www.anaconda.com/) or [WinPython](http://winpython.github.io/)), clone the repository https://github.com/janchorowski/nn_assignments and run `jupyter notebook`."
      ]
    },
    {
      "metadata": {
        "id": "zq_ZRu87C_OC",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "###   3. Install required dependencies, download data and import packages\n",
        "\n",
        "Run cells below. To run a cell either click it and click a run button or press \"shift + enter\"\n"
      ]
    },
    {
      "metadata": {
        "id": "onui8xrw5dKi",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Please note that this code needs only to be run in a fresh runtime.\n",
        "# However, it can be rerun afterwards too.\n",
        "!pip install -q gdown httpimport\n",
        "![ -e cifar.npz ] || gdown 'https://drive.google.com/uc?id=1oBzZdtg2zNTPGhbRy6DQ_wrf5L5OAhNR' -O cifar.npz\n",
        "![ -e mnist.npz ] || gdown 'https://drive.google.com/uc?id=1QPaC3IKB_5tX6yIZgRgkpcqFrfVqPTXU' -O mnist.npz"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "YxzWq6iO2KPm",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Standard IPython notebook imports\n",
        "%matplotlib inline\n",
        "\n",
        "from __future__ import absolute_import\n",
        "from __future__ import division\n",
        "from __future__ import print_function\n",
        "\n",
        "import os\n",
        "\n",
        "import httpimport\n",
        "import matplotlib.pyplot as plt\n",
        "import numpy as np\n",
        "\n",
        "import seaborn as sns\n",
        "from sklearn import datasets\n",
        "\n",
        "# In this way we can import functions straight from github\n",
        "with httpimport.github_repo('janchorowski', 'nn_assignments', \n",
        "                            module='common', branch='nn18'):\n",
        "     from common.plotting import plot_mat\n",
        "\n",
        "sns.set_style('whitegrid')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "AfmjDoxi6JNA",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### 4. Follow the notebook and solve problems posted below"
      ]
    },
    {
      "metadata": {
        "id": "3hr81V8T8ccB",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Problems"
      ]
    },
    {
      "metadata": {
        "id": "0eT1x_VG33_E",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Problem 0 [0p]\n",
        "\n",
        " \n",
        "1. To learn more about Jupyter,  read [Jupyter tutorial from Data Analysis in Biological Sciences course at Caltech](http://bebi103.caltech.edu/2015/tutorials/t0b_intro_to_jupyter_notebooks.html) (which itself can be downloaded as a Jupyter notebook). Feel free to skip the tutorial if you have some prior experience with Jupyter notebook.\n",
        "2. To learn more about basic Google Colab features, go to [Google Colab](https://colab.research.google.com) and select \"Overview of Colaboratory Features\" in \"EXAMPLES\" tab. To learn more about / set up useful keyboard shortcuts (e.g. to add a new cell without clicking \"\"+ code\"), go to \"Tools --> Keyboard shortcuts\""
      ]
    },
    {
      "metadata": {
        "id": "AsOC0voR33_F",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Problem 1 [2p]\n",
        "\n",
        "First, get familiar with Python at https://docs.python.org/2/tutorial/. Then, get\n",
        "to know the capabilities of NumPy, the prime numerical library of Python http://www.numpy.org/, for instance with the tutorial at http://wiki.scipy.org/Tentative_NumPy_Tutorial.\n",
        "\n",
        "You might also need:\n",
        "  1. another intro to NumPy,\n",
        "http://people.duke.edu/~ccc14/pcfb/numerics.html\n",
        "  2. a better interactive shell for Python,\n",
        "http://ipython.org/\n",
        "  3. access to IPython through an ordinary web browser,\n",
        "http://ipython.org/notebook.html\n",
        "  4. a plotting library for Python.\n",
        "http://matplotlib.org/\n",
        "\n",
        "**a) Declare variables:**\n",
        "1. $a=10$,\n",
        "2. $b=2.5\\times 10^{23}$,\n",
        "3. $c=2+3i$, where $i$ is an imaginary unit,\n",
        "4. $d=e^{i2\\pi/3}$, where $i$ is an imaginary unit, $e$ is the Euler's number (use `exp`, `pi`)."
      ]
    },
    {
      "metadata": {
        "id": "8sd7jJhd33_G",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# TODO: Complete the declarations\n",
        "a = \n",
        "b = \n",
        "c = \n",
        "d = "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "bP0hAHvN33_K",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**b) Declare vectors:**\n",
        "1. $aVec=\\begin{bmatrix} 3.14 & 15 & 9 & 26 \\end{bmatrix}$,\n",
        "2. $bVec=\\begin{bmatrix} 2.71 & 8 & 28 & 182 \\end{bmatrix}^\\intercal$ (column vector),\n",
        "3. $cVec=\\begin{bmatrix} 5 & 4.8 & \\cdots & -4.8 & -5 \\end{bmatrix}$ (vector of numbers from $5$ to $-5$ decreasing by $0.2$),\n",
        "4. $dVec=\\begin{bmatrix} 10^0 & 10^{0.01} & \\cdots & 10^{0.99} & 10^1 \\end{bmatrix}$ (logarithmically spaced numbers from 1 to 10, use `logspace` and make sure, that the result has correct length!),\n",
        "5. $eVec=Hello$ ($eVec$ is a string of characters, thus a vector)."
      ]
    },
    {
      "metadata": {
        "id": "37RmkuW533_L",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "aVec = \n",
        "bVec = \n",
        "cVec = \n",
        "dVec = \n",
        "eVec = "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "C58YJtEU33_O",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**c) Declare matrices:**\n",
        "1. $aMat=\\begin{bmatrix}\n",
        "                    2      & \\cdots & 2 \\\\\n",
        "                    \\vdots & \\ddots & \\vdots \\\\\n",
        "                    2      & \\cdots & 2\n",
        "                \\end{bmatrix}$,\n",
        "<br/>\n",
        "matrix $9\\times 9$ filled with 2s (use `ones` or `zeros`),\n",
        "2. $bMat=\\begin{bmatrix}\n",
        "                    1      & 0      & \\cdots &        & 0      \\\\\n",
        "                    0      & \\ddots & 0      &        & 0      \\\\\n",
        "                    \\vdots & 0      & 5      & 0      & \\vdots \\\\\n",
        "                           &        & 0      & \\ddots & 0      \\\\\n",
        "                    0      &        & \\cdots & 0      & 1\n",
        "                \\end{bmatrix}$,\n",
        "<br/>\n",
        "matrix $9\\times 9$ filled with zeros, with $\\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 4 & 3 & 2 & 1 \\end{bmatrix}$ on its diagonal (use `zeros`, `diag`),\n",
        "3. $cMat=\\begin{bmatrix}\n",
        "                    1      & 11     & \\cdots & 91     \\\\\n",
        "                    2      & 12     & \\ddots & 92     \\\\\n",
        "                    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
        "                    10     & 20     & \\cdots & 100\n",
        "                \\end{bmatrix}$,\n",
        "<br/>\n",
        "matrix $10\\times 10$, columns of which form the vector $1:100$ (use `reshape`),\n",
        "4. $dMat=\\begin{bmatrix}\n",
        "                    NaN & NaN & NaN & NaN \\\\\n",
        "                    NaN & NaN & NaN & NaN \\\\\n",
        "                    NaN & NaN & NaN & NaN\n",
        "                \\end{bmatrix}$,\n",
        "<br/>\n",
        "matrix $3\\times 4$ filled with `NaN`s (use... `NaN`),\n",
        "5. $eMat=\\begin{bmatrix}\n",
        "                    13  & -1  & 5  \\\\\n",
        "                    -22 & 10  & -87\n",
        "                \\end{bmatrix}$,\n",
        "<br/>\n",
        "6. $fMat$ filled with random natural numbers from $[-3,3]$ (use `rand` and `floor` or `ceil`)."
      ]
    },
    {
      "metadata": {
        "id": "Bdd1oUeI33_P",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "aMat = \n",
        "bMat = \n",
        "cMat = \n",
        "dMat = \n",
        "eMat = \n",
        "fMat = "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "DqtKQi1Q33_T",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "** d) Declare a multiplication table ** as a $10\\times 10$ matrix `mulMat`. Use matrix/vector multiplication."
      ]
    },
    {
      "metadata": {
        "id": "OWqHq-vK33_U",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "mulMat = "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "0xIm6lT133_Y",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "** e) Compute elemwise using values from b).**\n",
        "For instance, the first element of $xVec[0]$ should be equal to\n",
        "\n",
        "\\begin{equation}\n",
        "1/(\\sqrt{2\\pi2.5^2}) e^{-cVec[0]^2 / (2\\cdot\\pi 2.5^2)}.\n",
        "\\end{equation}\n",
        "\n",
        "1. $xVec=1/(\\sqrt{2\\pi2.5^2}) e^{-cVec^2 / (2\\cdot\\pi 2.5^2)}$\n",
        "2. $yVec=\\sqrt{(aVec^\\intercal)^2 + bVec^2}$\n",
        "3. $zVec=\\log_{10}(1/dVec)$, using `log10`"
      ]
    },
    {
      "metadata": {
        "id": "LtH-kSU733_Z",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "xVec = \n",
        "yVec = \n",
        "zVec = "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "EBhf74F_33_d",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "** f) Compute with matrix/vector operations using values from c).**\n",
        "\n",
        "**NOTE:** Every multiplication (and power) in this subtask is a [matrix multiplication](https://en.wikipedia.org/wiki/Matrix_multiplication).\n",
        "1. $xMat=(aVec\\cdot bVec)aMat^2$,\n",
        "2. $yMat=bVec\\cdot aVec$\n",
        "<br/>\n",
        "(remember, that matrix multiplication is not commutative),\n",
        "4. $zMat=\\lvert cMat\\rvert (aMat\\cdot bMat)^\\intercal$, where $\\lvert A\\rvert$ denotes determinant of $A$ (use `det`)."
      ]
    },
    {
      "metadata": {
        "id": "UjdLR34u33_e",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "xMat = \n",
        "yMat = \n",
        "zMat = "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "QJ3xTXgV33_i",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "** g) Declare `ismagic(A)` function ** which checks if matrix $A$ is a [magic square](https://en.wikipedia.org/wiki/Magic_square) and returns a boolean."
      ]
    },
    {
      "metadata": {
        "id": "uCNJUx_G33_j",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def ismagic(A):\n",
        "    # TODO"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "Es80_WJM33_n",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### k-Nearest Neighbors\n",
        "\n",
        "The following excerpt of code loads the data describing iris flowers\n",
        "and shows relations between their length and petal width for three\n",
        "species (namely: setosa, versicolor, virginica)."
      ]
    },
    {
      "metadata": {
        "id": "hOvm2SEE33_q",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 313
        },
        "outputId": "3b5eeae1-f4d9-44b1-bb70-a78723214b6d"
      },
      "cell_type": "code",
      "source": [
        "# sklearn is a large collection of machine learning algorithms\n",
        "# here we’ll use it only for the built-in iris dataset\n",
        "from sklearn import datasets\n",
        "\n",
        "iris = datasets.load_iris()\n",
        "\n",
        "print('Features: ', iris.feature_names)\n",
        "print('Targets: ', iris.target_names)\n",
        "\n",
        "petal_length = iris.data[:, iris.feature_names.index('petal length (cm)')]\n",
        "petal_width = iris.data[:, iris.feature_names.index('petal width (cm)')]\n",
        "\n",
        "for target in set(iris.target):\n",
        "    example_ids = target == iris.target\n",
        "    plt.scatter(petal_length[example_ids], petal_width[example_ids],\n",
        "                label=iris.target_names[target], color='bgr'[target],\n",
        "                marker='x', alpha=0.7)\n",
        "unknown = np.array([\n",
        "    [1.5, 0.3],\n",
        "    [4.5, 1.2],\n",
        "    [5.5, 2.3],\n",
        "    [5.1, 1.7]\n",
        "])\n",
        "plt.scatter(unknown[:, 0], unknown[:, 1], marker='v',\n",
        "            color='gray', s=50, label='??')\n",
        "plt.xlabel('petal length (cm)')\n",
        "plt.ylabel('petal width (cm)')\n",
        "plt.grid(True)\n",
        "plt.legend(loc='upper left');"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Features:  ['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']\n",
            "Targets:  ['setosa' 'versicolor' 'virginica']\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAEGCAYAAABsLkJ6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJztnXlclNX+xz8jMG6jIBDivuduymLK\nJqJYWnrVVBBEr7neqzcp6CdipVcJ1FDJpVRIKy3FsFwKLyqBEosI4QauqYW4AIrIPizP74+neYaB\nZ5iBWWG+79drXjDnOec83zMw5/ucc76LgGEYBgRBEITB0UrXAhAEQRC6gRQAQRCEgUIKgCAIwkAh\nBUAQBGGgkAIgCIIwUIx1LYCypKen61oEgiCIZomtrS1vebNRAID8QShDenq6Su31CRqLfkJj0U8M\nfSwNPTzTFhBBEISBQgqAIAjCQCEFQBAEYaCQAiAIgjBQSAEQBEEYKKQACIIgDBRSAARBEAYKKQCC\nIPST+HhALJYtE4vZ8qa0PXuWfTWlvxaKRh3BtmzZgvT0dFRVVWHZsmWYNGkSd83NzQ3W1tYwMjIC\nAISGhqJz586aFEdn3Lx5E61bt0afPn10LQpBNA/i44GtW4Hz54E1awChkJ2sQ0KAtDS2jqurcm0B\nduJfuZL9fdcuwN1d+f5aMBpbAaSkpODOnTuIjIxEREQEgoOD69UJDw/HwYMHcfDgQY1P/mlpoiY/\nTKjK2bNn8eDBA83fiCBaCg4OgJ0dOzmHhAAlJdLJ2s6Ova5k21ZlZcCFC9LrCQmN668Fo7EVgL29\nPUaMGAEA6NixI8rKylBdXc098WuT+Hjgu+8648mTxj9MNMSjR4/w4YcfolWrVqiursZnn32G3bt3\nIzs7G1VVVXjvvfdgbm6OI0eOwNzcHBYWFigrK8P27dthbGyMzp07IyQkBPn5+fX6MTU1hZ+fH0pL\nS1FeXo6PP/6Y+zwJosUjFLJfVsmX1NOTLbezk36JlWzbJzYWMDUF5swBBAIgI6Nx/bVgBNpICRkZ\nGYm0tDR89tlnXJmbmxtsbGyQk5MDW1tb+Pn5QSAQyO1DlWBwlZUCHDhgjRs32mHw4FL4+DzFwYOd\nufcLFz6BiUnjP4ZffvkFFRUVmDlzJu7fv4+MjAxUVVVhzpw5ePnyJT799FNs3rwZe/bswejRo2Fj\nYwM/Pz8EBgbCwsICBw4cQJ8+fVBSUiLTT1VVFUQiER4+fAh7e3tkZmbizJkzeP/995v8GRBEc6RV\nWRn6BAZy7+8HB6OmbdsmtwXQ5P6aMzoLBnfu3DlERUVh//79MuXvvfcenJ2dYWpqihUrViAmJgZv\nvvlmg32pFtDpd8TE2CAtzQybN3cFAEyYAKxZYwahsGuTeuzQoQNWrlyJDh064I033sC1a9dw5coV\nhIWFAQBatWqF4cOHw8LCAv3790e/fv3Qtm1b7iwkPz8fly5dgqenp0w/o0aNQlFRETZs2IDz589D\nLBajXbt23PgNPbiVvkJjUTOSZbqpKVc0KjZWuSf2Wm1fFBbCzNQUo2Ji2BVAU/rTE5pVMLiEhATs\n2bMH4eHh6NChg8y16dOnw8LCAsbGxnBxccHt27c1KQpMTBj4+8uW+fur9nd/9dVXceLECdjZ2WHb\ntm1ISEjA8uXLuXONM2fOQFjrBgKBALUXXJWVlRAIBPX6OX78OL755ht07twZhw8fxvr165suJEE0\nR2rv0drZAUeOyJ4J1D3Qa6Dt/eBgYORI4OhRIDISGDWqcf21YDSmAIqKirBlyxbs3bsXZmZm9a4t\nWrQI4r8/9EuXLmHAgAGaEgUAuw0UGipbFhqq2t/9l19+wZ07dzBx4kSsWrUKJiYmiI2NBQA8e/YM\n27ZtA8BO/NXV1TA1NYVAIMCjR48AAKmpqRg2bFi9fq5fv46CggL07NkTALuKqqysbLqgBNHcSEqS\nTv5r1gDt27M/JZN2UpLSbWvatgVcXKTXnZ0b118LRmNbQNHR0SgoKICvry9X9vrrr2PgwIFwd3eH\ni4sLPDw80Lp1awwZMkTh9o8qiMXAgQPWePSI/Xv7+7OTv0T5N3UF2Lt3b6xbtw7t2rWDkZERduzY\ngW+//Raenp6orq7Gyr/Nzuzs7BAUFIT27dtj48aN8PPzg7GxMXr06IG33noLt27dkunno48+QklJ\nCVavXo3//e9/8Pb2xs8//4xjx47hnXfeUfOnQxANEB/PWsjU/oKIxeyEqU6zybAwYPFiQCRi37u6\nAmVlQGam9N6Sw11F95Zcqy23uztr/in5vTH9tWSYZkJaWlqT28bFMYyzcwGzfj3DVFSwZRUVDLN+\nPcO8/TZ7vTmhymehb9BY9JO0tDT2i/H224zGvzjbtzOMlRXDuLoyTFERW1ZUxL63smKvq0CL+7uo\nsY1BeAK7ugLe3k9lnvQlyt/Pz3CVP0E0iCq2+I1h8WJgyBAgKwuYOhXIzWV/ZmWx5YsXq+c+RD0M\nQgEAgJ1dcb1tHqGQJn+CkIvkKUmiBDw9Zffl1WU5IxIBp05JlcDw4dLJ/9Qp6bYQoXYMRgEQBNEE\nhEKo3XyOD5GItdCpTWQkTf4ahhQAQRDyEYuhdvM5PoqLAQ8P2TIPD7ac0BikAAiC4EcVW/zGUFws\nu+d/7ZrsmQApAY1BCoAgCH5UscVvDBERsnv+VlayZwIREeq5D1EPUgB6wI8//oizdeOUK8DHx0fj\n3tOEgePqysZL8fOTNZ/z8wN69apvBcQXb79OWVVVFR7ev4+HJ07g4cOH7GvWLDz88EM83LsXVW3a\nsBVFIuDDD9lXLV8i3hC+yuYNUCW/gLbQsowajwWkL6Tlp2F49XAIjaSHV+JqMZKyk+Da21V3ggGY\nOXOmTu9PELzExwOxsUBhoWwY3ZUrgdOnWbPQvXvZcr54+zxlTEUFfvz2WxQAwOXLMrczj4nB8uXL\npff+8kt2tSEWyw/hq0zegA4dVMsvoC2UHYsaMYgVQPyDeHx37zuEJIRAXM1qV3G1GCEJIdiavBXx\nD+Kb1O+MGTO4sA45OTmYPn06AgMD4ePjg7lz5yI5ORkA+7S+YcMGbNiwAVlZWfDw8ICPjw8WLVqE\nly9fYufOnTh06BAAICgoCHPmzMHcuXO5J/wtW7bA09MTs2fPxvHjx2VkKCoqwooVK7h7ZmZmAgAm\nTZoEX19f/PDDD00aG0HI9QPIy2O3Z3JzpeUJCdJ2Fy6wZTwx+E1CQzEiJ4f3dsOHD4eJiUnD967r\ng6DuerpEBzIaxArAoYcDBpsNRtrjNIQkhMDfwR+hSaFIe5wGuy52cOjRtA924sSJiIuLg7e3N2Jj\nYzFx4kRUVlYiODgYz58/x4IFC3Dq1CkAwIABAzB37lwEBQVh7ty5mD59OpKTk5GXl8f1l5SUhCdP\nnuDo0aO4dOkSoqOjUVhYiDt37uDIkSMoLS3FtGnTZILDffPNN3jttdewdOlSXLt2DSEhITh06BCy\ns7Oxe/dujcdYIlow8mLyjx7NbgNt3Spb7uEBMAz7ZC8p44nB72hnh0wLC+Q/e8bdytLSEo6Ojorv\nXdcHQd31dIkOZDSIFYDQSIiF/RfCrosd0h6nwfOYJzf5r3FeI7Mt1BgmTZqEX3/9FQAQGxuLy5cv\nIzY2Fj4+Pli1ahUqKiq4gHeSZC4TJkzAl19+ibCwMFhYWKBfv35cf5mZmbCxsQHAJtTx9fXF9evX\nYW9vDwBo164d+vfvjydPnnBtrl+/jtdffx0A+wT1559/AgDatm1Lkz+hOvL8AESi+uWrVwMBAbJl\nAQFseS1M/P0xdNgwmbKhQ4dKn/4V3ZvPo1Od9XSJlmU0CAUAACatTODvIPvB+jv4N3nyB9in+tzc\nXDx+/BhFRUXo3bu33HDQkn/usWPHIioqCn379kVAQABSUlK4/oyMjFBTUyNzj7pJciQhpGtfZ2qF\nmJa0r/dlIoimIM8PoLi4fvnmzcCmTbJlmzax5XXaO9rbw9LSEgDP07+ie/Mdkqqzni7RsowGowAq\nayoRmiT7wYYmhXJnAk3F1dUV27dvh5ubG1577TXecNC1OXToEF68eIFp06ZhwYIFuHHjBndt+PDh\nuHjxIgAgKysL//3vfzFs2DCurKSkBH/99Resra1521y+fJme+gn1Ic8PIDWVtc9PTZWWjxrFeu4e\nPcrG3j9ypMEY/CahoRg6aBAAOU//yvogqLueLtGBjAahAMTVYhy4e4Db9jnyzhFuO6j2wXBTcHd3\nx88//4w333wTkydPRrt27eDp6Ynly5fzZu7p2bMnVq1ahQULFuDnn3/G1KlTuWv29vbo168fvLy8\nEBQUBE9PT9jZ2WHYsGHw9vbGu+++Cz8/P7SRmMoBmD9/PjIzMzF//nxs3boVa9eubfJYCEIGeX4A\nr7zC2udbWUnLnZ2l7Vxc2DIFMfgdAXTp0oX/6V9ZHwR119MlupBRhcikWkWlcND34xjnL5yZ9XHr\nmYoqNqxtRVUFsz5uPfP2928zcffj1CSldjD08Lb6SoscS1ycNBS0hIoKNkRz3fIzZ9iXorKKCi6U\ndIWkD777KNufgnsoHIs24sEre28F9dQdDtogrIBce7vCu683Fjov5Pb8hUZCrHFeoxd+AASht/DZ\nxguFss5ZEiSJVhSV1QrDKxQK5du/S56ITUykNv87drBPxOPGya9X5x4Kx6Jp+//G+CBoWUaD2AIC\nADtLu3oHvkIjIU3+BKFrWpItPx96LLfBKACCIPQUZfMOaCs/gbrRY7lJARAEoXtaki0/H3oqNykA\ngiB0T0uy5edDT+UmBUAQhG5pSbb8fOix3KQA1MiFCxfw/fffq6Xuvn37kJGRoS7RCEJ/aUm2/Hzo\nsdwGYQYKAKK0NDbZdO09N4kJmZpMrFxqO76oWHfp0qWqikMQuic+nrVyqf29k+QHkJiIurqyE+GQ\nIbIHvvb27GRZ20SyslJ6XfLTwYF91f4eq/m73Sjqjlme3GvW6E7GvzEMBRAfj87ffQc8eaLWWOAz\nZszA7t270bVrV+Tk5GDmzJmYOXMmvL298eGHH6Jdu3aYN28eCgsL8dVXX8Ha2hqdOnXCmDFjAAB3\n7tyBt7c3AgIC0KNHD9y6dQuDBw/Gp59+ioCAALzxxhtwcnJCQEAAcnJy0Lp1a2zZsgWlpaVYtmwZ\nSktLUV5ejo8//pgLNkcQegOf/bu8vAHh4WyZiYm07P332bLXXmPLGuMboMEY+o0ec2N8FbSMYWwB\nOTigdPBgtdvhSsJBA2w00IULF3LXbty4gdDQUIwbNw7btm3DgQMH8PnnnyNN8k9Zi8zMTHzwwQeI\niorC+fPn8fLlS+7a8ePHYWlpiSNHjmDOnDmIjY1FYWEhZs+ejYMHD+KDDz5AuOTLQxD6BJ/9u5J5\nA3jrNQffAH2TRwGGsQIQCvFk4UJ0jYlRa5ztSZMmYdOmTVw+gClTpqCwsBAA0KNHD3Tq1AnPnj2D\nSCTiIh+OHTu2Xj89e/bEK6+8AgCwsrJCUVERdy0zM5Nr89ZbbwEAEhIScPLkSXz11VcQi8Vo165d\nk+QnCI0iL769knkDeOvpe5x/fZNHAYaxAgDAmJio3Q63bjjo2hENJb8zDINWraQfc93wzgAbBlpG\n1lrhnflCRJ8+fRqdO3fG4cOHZZLDEITewWf/rmTeAN56zcE3QN/kaQCDUQCCykqN2OHWDgfNh5mZ\nGV68eIHCwkKUl5cjNTW1Uf0PHz6cyxkQFxeHPXv2oKioCD179gQAnDt3DpWSAyaC0Df47N+VzRvA\nV685+AbomzwNYBgKQCyG9YEDGrHDrR0Omg9jY2P861//gre3N/z8/DBs2DCZFYEipkyZgrKyMsyb\nNw/ffPMNZsyYAWdnZxw4cADvvvsuRowYgby8PBw7dqzJYyAIjcBn/65s3gC+es3BN0Df5FFEo2OL\n6giVQu3GxTEFzs4Ms369NNRqRQX7/u23NR4O9vTp00xBQQHDMAzz7rvvMunp6Sr11yLDDrcAaCx1\niItjv1+1v3dnzjDMq6+yL0kIZ2XL+L6zfPeoU0+rfxcl5FEFdYeDNgwFwDDMzT17dBYL/KeffmKm\nTZvGeHh4MOvXr1e5P5po9JNmNRYF8fe5sciLtc+XD0DZ+PZqivPf4D1UjKHPiyox/ZUdiwKaVT6A\nLVu2ID09HVVVVVi2bBkmTZrEXUtKSsK2bdtgZGQEFxcXrFixQpOioNjOjv/wSAt2uNOnT8f06dM1\nfh+CUApl7PPNzflt9sViYOlS4PRp4MoVYO/exse3VzZvgIJcAhzaiKGvSkx/ZXwVdOQPoLEzgJSU\nFNy5cweRkZGIiIhAcHCwzPWgoCDs3LkThw8fRmJiIu7evaspUQiCqI0S9vmtysrk2+Ln5bFeu7m5\nzcLWXS2oYt+vx74BGlsB2Nvbc96pHTt2RFlZGaqrq2FkZITs7GyYmpqiS5cuAIBx48YhOTkZ/fv3\n15Q4BEFIUMI+v8/584CpKb8t/ujRgJ8f+0TcDGzd1YIq9v167BugMQVgZGTEOShFRUXBxcWFs3fP\ny8uDubk5V9fc3BzZ2dkK+0xPT1dJJlXb6xM0Fv2kOY2l1YQJ6BMby72///cWbZ/z5wEALwoL65UB\nwP0JE1Bz61b99hMmoObaNW2I3mjU9XdRZczq+rzU+T+mcU/gc+fOISoqCvv371e5L1tb2ya3TU9P\nV6m9PkFj0U+a1Vgke9CmplzRqDNn2Kd9U1O8KCyEmampTBlXLzZWugKoW66HKwC1/V34PjNlx6xK\n21o0ZSwNKQyN+gEkJCRgz549CA8PR4daAZmsrKyQn5/PvX/69CmsrKw0KYrGqK6uxrp16+Dt7Y05\nc+YgOjoaGRkZ8PLygo+PD1asWCET24cgdI4S9vn3g4Pl2+KnpgJTp7I/m4OtuzpQxb5fj30DNKYA\nioqKsGXLFuzduxdmZmYy17p3747i4mI8fPgQVVVViIuLg6Ojo6ZEQVVVFQoKCvDw4UPeV1VVVZP7\nPnHiBIyNjfHdd99h//79CA0Nhb+/P7Zu3YqDBw/itddewzfffKPG0RCEivDFp3d2ll53cUFN27b1\nyrg49q+8AmRlAVZWehffXmOoEtPfEPMBREdHo6CgAL6+vlzZ66+/joEDB8Ld3R3r16+Hn58fANbb\ntU+fPpoSBQzDICMjA4mJifWumZubY/ny5U3ue/jw4XBycgIAiEQimJmZISAggDvgHjBgAE6fPt3k\n/glC7UhMDmvHrHd3B5YsYa173N2B9HT257hxQK9eUpNMoRDYtg0oLJSagErK9S0uf134chMoKx/f\nZ6ZsTH9V2moYjSkADw8PeHh4yL1ub2+PyMhITd1eBhMTE3Tr1g137typd2348OEyQdway4ABA7jf\nL126hNLSUm6PrqqqCt999x3efvvtJvdPEBqBz1b9/HnWRHHiRLYsNBT4/nugTRvAxgaYPBkoLgbe\neYddAXzxBSB5wNNjW3dOPmXt+OWhir+BNnwVmoBhxAIC0L9/fy4kswRLS0u1bT1dvXoV69atwxdf\nfMFZO/n5+WHQoEHkBEboP3Vs1VuVlQEFBezkX17OBmXLzWX3/rOy2JXC4sVy2+uTrXuzkE9HGIwC\nMDIywtChQ2XKhg4dqtLTf2127NiB0NBQ9O3bFwBw5coViMVi+NcNC0sQ+ohkS+LvSbJPYCBw9Sqw\nbBlgawvcvMmmVJVM/qdOASKR3Pbw9JTd99a1ZZC+y6cjDEYBAICjoyO3ClDn0z8AfPzxxxgyZAj3\nvl+/fggKClJb/wShcfji2AcGAj/8IFsWGSk7+TfUXp/i4Ou7fDrAoBSAiYkJtwpQ59M/AISFhaG8\nvJx7//vvvyMmJkZt/ROExuGLYx8cDMyeLVvm4cGeBSjTXp/i4Ou7fDrAoBQAwK4CunTponaz0+3b\nt6NNmzbcexcXF3h5ean1HgShMerYqt8PDgZGjGAtfdLTgUGDgGvX2O2frCz2LKC2EtBjW/dmIZ+O\nMDgFYGJign/+859qffoniGZPHVv1mrZtgU6d2APgNm3Y1IxWVuzev0QJRETIba9Ptu7NQj4dYXAK\nAACEBrznRxgedz9ZCXHhc5myquAg3F29VFrg6gr8+9/sxCj5fvj7Az4+wP79rAkowO79HzvGbgvV\n8vGBqysbHoIvYbufn6y5Y1hY/S2k6Oj62zNiMWu+WZv4eP6UkIrquboC773Hb4tfV77G3KeZo/FY\nQARB6I67n6yExefhyDn1C7rFp0Noao6q4CBg3Tr0YhjcBdB/8z52Qt6yhX2yNzZmvYDj44GHD4GM\nDODNN6W28zt3An/+yV6vPXEqY+seFsZuuZw4IbUkio4G5s9nVxsAq3j4bPSVteWvWw+QOnylpQEm\nJlKZ+Gzx1eEz0EwwyBUAQRgKPf024EXfrjC79wg5rrYoeXgfD4+Eg2EYCAQC9EnMkm/frwnb+cWL\nZc8RcnPZ5O+Srabnz+XfR1l5+HwaGiO3AfkM0AqAIFowQlNzdItPR46rLczuPYJ46CCYAsgZ0gM9\nOvaA0Z07rH0/UN++XxNx7EUi9h4ShSO5t60t4OjIHjTLu4+y8tSp1yc2lo3Cqazcehy/X93QCoAg\nWjhCU3NYnfpVpuyV6HgY/fijbEU++35N2M6LROy9avPDD8DatYrvo6w8qsptID4DpAAIooUjLnyO\n3KluMmV5U1xRPXOmbEU++35N2M4XF7P3qs3s2cCnnyq+j7LyqCq3gfgMkAIgiBaMuPA5t/3zom9X\nCDNvorCXNbplZYO5mIzqAQPk2/drwna+uFj2vOHaNdbHID0d2LeP3RKSdx9l5eHzaWiM3AbkM6CU\nAsjPz8fVq1dx9epVmUQuBEHoN39t/YSb/LvFp6N99z7o7rkEAoEADMPgvuMQ+fb9mrCdj4iQjSdk\nZQWsXi0NOmduLv8+ysrD59PQGLkNyGegwUPg6Oho7Nu3D3l5ebC2tgYAPH78GJ07d8bSpUsxWWIb\nTBCEZmliLPv+G3bhLlhrIKEpm4fbOPAjVAH4s/Av1gQUAEQiXNj5IRxismDs6wukp6PKyQkPC57h\namfAJjdX2un8+cDIkbB2cmq8FYnEd2DxYul5w5QpwLffsopBsu/OFy9f2bj6qsbf1+P4/epG7t8v\nICAAVVVV2LRpEwYNGiRz7ebNm4iIiMD58+exadMmjQtJEAaNinbp/TfsqldmHPgR+te+xYN4bL32\nJexs7bCmmt3iqKiqwDe3rwNXgQxcl2lvbm6O5QzTtPHUdiCTMGUK+6oNn42+snH1VY2/r6fx+9WN\n3C2giRMnIjQ0tN7kDwCDBg1CaGgoJkoSRxAEoTm0YJfu0MMBdl3skPY4DSEJISirKkNoSihy2uXw\n1lc1kRKhH8hdAUgm96dPnyImJgZFRUVgamn8lStXkgIgCG2gBbt0oZEQa5zXICQhBGmP0xD7Iham\nZqawG2IHixsWePbsGVdX3aHUCd2h8BB4yZIluHHjBiorK1FVVcW9CILQIlqwSxcaCeHvIHsPf2d/\nDBs2TKZM3aHUCd2h8AzHzMwMISEh2pCFIAh5yLNLV6NnqrhajNAk2XuEJoXCf4w/MjMzkZ+fT0//\nLQyFKwB3d3ecPHkS2dnZePToEfciCEJLaMEuXVwt5rZ/7LrYIdgmmDsTCE0JxaDB7FkgPf23LBSu\nAG7duoVTp07BzMyMKxMIBIhvYWFRCUJvqWuXXvdMQA2miUnZSdzkv8Z5Da5dviZzJuBk76SRREqE\nblGoAK5cuYJLly5RDH2C0BWurrj85DKG/GOx9HsoFEL8f37IOhGBkbUm//gH8XDo4QChkfT7Kq4W\nIyk7Ca69XSEPybXabYVGQjj0cIBDDwdM6DcBzj2dYWJiolR/GqOJ/hAEPwq3gIYNG4aKigptyEIQ\nBA/xD+LxMROLkItbIf7bRl9cLUbIxa34mIlF/IN4rt7W5K0ISQiRrZcQgq3JW7l68nDt7SqjOOIf\nxGNH6g4kZSdBXC2GUChsVH9qR+IPwRf2YevWFpesRRsoVABPnz6Fm5sbPD094e3tDS8vL3h7e2tD\nNoIgUN9Gv0RcIrNf79DDoVH11H1frWFAcfq1hcItoOXLl2tDDoIg5FDXRt/zGOsHINmvr71lo0w9\ndd9XaxhQnH5toXAF0Lt3b9y8eROjR4/G6NGjkZiYiF69emlDNoIg/obXRt/Bv94krGw9dd9XaxhI\nnH5toVABrFmzBpaWltz7gQMHIjAwUKNCEQQhizwbfclef2Prqfu+WsNA4vRrC4UKQCwWY0qtIE1T\npkyBmD5sgtAadW30j7xzRGZvvu6Br6J66r6v1jCgOP3aQql8ABcuXEB5eTlKS0sRExMDgUCgabkI\ngvibujb67YXtscZ5DTcZJ2UnNaqeuu+rNQwoTr+2UHgIHBQUhHXr1mHVqlVo1aoVRo0ahY0bN2pD\nNoIgIN9Gf43zGhl7fGXrqfu+WsOA4vRrC7krgOzsbABAr1698PXXXyMjIwPp6emIiIjgDoEldeRx\n+/ZtTJw4EYcOHap3zc3NDV5eXvDx8YGPjw+ePn2qyjgIQq+JfxDPu1+vrC39R79+hCfFT2TKjmUe\nQ+A52fO4yupKnH9wXmF/YSlhKBbL5v8tO3saOxJk99dd71RC+Ktsf8JqwPWBUmKrH1dX/gTwNPk3\niQYTwvzjH//AzJkzYWwsW626uhrHjh3DyZMneSd3ACgtLcXGjRsxduxYuTcPDw9H+/btmyg6QTQP\nJA5a5x+c58wna++vA2jwadppvxMSsxMxcOdA3PrPLfQ07YnDVw9j3vF5qGFq4BDhgKTFSTj7x1ms\njF4JCIBdk3fBvZ87733CUsIQ8lsITtw8gVNepyASilB29jQyPvRBuVU5dnwMOLYbD5w9C6xcyQqx\naxfg7t6oRDSE/iN3BRAeHo6bN2/C1dUVvr6+2Lx5MzZv3oxVq1bB1dUVt27dwr59++R2LBQKER4e\nDisrK40IThDNBVUdqr5/53u0MWqD8upyDNw5EJdyLmHhyYWoYWrQStAKY7qNQYm4BBf+vAAIADBA\nwl8Jcu+z2GYxhlgOQVZ+FqZ+PxW5xbmY9ucm/GZVDqfcNlh2tgCtysqACxekQiQkkONVC0TAMA3n\ndXv+/DmSk5Px+PFjAECXLl3g97n7AAAgAElEQVQwduxYmJubK3WDnTt3olOnTpg3b55MuZubG2xs\nbJCTkwNbW1v4+fk1eLicnp4OW1tbpe6pifb6BI1FP2loLHWfxIHGOVT9VfgXBu4ciPLqcq6stVFr\n/Nv237jz4g5XNrLzSAgEAmQ8yWjwPsXiYkz9fiqy8rO4shFmg/DzX05onXEVLwoLYWZqCowcCQgE\nQIa0v+bmeGUo/2NNaaNQAaiKPAVw/PhxODs7w9TUFCtWrMCMGTPw5ptvyu0nPT1dk2IShMYpqypD\n4O/SPftgm2C0NW6rdPvMgkwsSFzAvf/G8Rv07dC3Xp8AlLrP8/Ln8Lzgyb0/4nIElkxb9Knl53M/\nmO2vbllNW+XlJnSPPAWg0ApIU0yfPp373cXFBbdv325QAQDyB6EMhv4UoK8YylgkKwBTM1OuLLYs\ntlErgGU7l8mULU1Zin/b/lumz5gS1kxb0X0kKwBjE+kUsOVGELsCMDXlVgCjYmLYFYCptL9RsbG0\nAtARTV0ByEMpPwB1U1RUhEWLFnEOZZcuXcKAAQN0IQpBaBxVHapqb/+0MWqD1MWpaG3UGhXVFfj8\n0ucYYDYAR945gpGdR+Jo1lFEXo/EKOtRcu9Te/tniOUQXFt+DSPMBsH9aDrST+5FxagR7JP/yJHA\n0aNAZCQwahQ5XrVAlFIAhYWFyM7Olnkp4vr16/Dx8cFPP/2Eb7/9Fj4+Pjhw4ADOnj2LDh06wMXF\nBR4eHvD09IS5ubnCp3+CaK6o6lDldcyLm/xv/ecW7LvZ48C0A2glaIUapgYpOSloL2wPl14uAANA\nADj3dJZ7n4jfI7jJ/5TXKViJrHCyVwCcctvgN6ty7HXvxG7xuLhIhXB2JserlgijgA0bNjCjRo1i\n3NzcmPHjxzPjx49n3NzcFDVTO2lpaTptr0/QWHRD3P04pqKqQqasoqqCibsfxzBMw2NR1LY225O3\nM0UVRTJlY/aNYT4695FM2UfnPmJe3/e6TNmS40uYjfEbZcpO3DjBLD+1XKbss8TPmOjb0TJlpWei\nmc8vfCY7ljNn2JeM4BUME1dfbpWIi2P71cB9mtP/mCKaMpaG2ig8A0hNTUVKSgplBCMMGmVs+Tug\ng9z2fHb+QiNhvXI+G/1icTHamLTBvox9sGhvAd8xvoh/EI/LuZcxecBkNlmLkRChSaH4PvN7tDFu\nA9uutpg8YDJO3zmNd0++i/KqcvQz7wd/B3+Iq8UoEZfgi7Qv0NakLSdDW/fJeA+TZYV0d68/GHU7\nXkkSvZw/Lz1bIH8DraBwC6hPnz6UBJoweLSVHIXPRr/2fv1im8Vy5SkoK0Ab4zYoryrHpt82Ibc4\nF5t+24TyqnK0MW6DgrIC3Sd14YMSvegMuSuAzz//HADQvn17zJs3D7a2tjAyMuKur1q1SvPSEYSe\noK3kKCKhCKe8TnGT/vA9wwGA268XCUUNyrPMdhl+++s33Hx2k2tr28UWTj2dcDX3qu6TuvBBiV50\nhtwVgJGREYyMjNCtWzeMHTsWQqGQK6utCAjCUNBWchSRUITIWZEyZZGzIrnJvyF5Ap0D8cPsH2TK\nfpj9AwKdZWMG6TSpCx+U6EUnyFUAK1euxMqVKyESibjfJa+amhptykgQeoG2kqMUi4vhEeUhU+YR\n5VEveBufPMEJwZj9w2yZstk/zEZwQrBMmU6TuvBBiV50glwFkJKSgrCwMHz77bf4/PPPudfWrVsR\nGRkprxlBtEi0lRyFz0a/9pmARAnwyTPCagT2pu9F+uN0DLIYhGvLr2GQxSCkP07H3vS9GGE1QvdJ\nXfigRC86Q64C6Nu3L/r27QsAMls/bdq0wbZt27QmIEHoA9pKjsJno3/K6xSnBCJ+j5ArT6e2nbgD\n3wCnAFiJrBDgFMAdDHdq20n3SV34oEQvOkPuIbCVlRWmTZsGW1tbdOvWTZsyEYTGiH8QL5PgBGCf\nphUlOJGXHOVJ0RMsHrkYrr1dkf6Mdbn/9MKn+PPFn9g3TRotd1PCJgBAgHMAV1YsLobPjz44OPMg\nt7/vO8YXWU+z0NOsJ1cmEorg+7ov/nf3f/Ad48vJk5aThiGvDOHk8XfwR1V1FQBg8oDJ3M+DMw4i\nMy+TOy/QaVIXPijRi86QqwDc3NwajM4ZGxurEYEIQlOoGpe/7rWV0Sux/8p+/O+P/8G5tzMAdvL/\nJP4TMH/HWNw3bR82JWzCJ/GfcO0CnANQLC7GyD0jca/gHkbuGYnLyy9DJBQh+nY0frz1I/ck7+/o\nj7N/nMX/xf4fwABn/zgL937uOPvHWYT/Hg4IABMjEy72f0V1BdIepyH+QTwn7+QBkzmFIIHPB0Gn\n8E3ylOhF48jdAvr6669x4MABvPnmm/Dx8cHu3buxY8cOeHh4YOrUqdqUkSDUgrpt+TeM34Cuoq54\nVPwItnttkVOSg33p+8AwDAQCAbLys5BbnItf7vzCtfnl7i+cbf/LipcwbW2KlxUvOZv/zYmbpXb7\n5azdfsJfCVyIhwt/XmhU7H+CaAi5K4CePXsCALKysnDgwAGufOjQoVi2bJm8ZgSht6jblt+8rTnS\nl6XDdq8tHhU/wqz4WRC0EqBHxx7oYdoDd57f4WzxX+/2OiAAbj+7zZUNfWUoDs86jLlRc2Vs/vns\n9j2GeYBhGFx+epkrmzNkDhf7Xy/t+wm9R6En8LNnz/Dbb7+htLQU5eXlSE5OxqNHj7QhG0GoHXXb\n8pu3NcevC36VKYv/Zzx+nPOjTNmxOcdwbPYxmbLIWZGwFlnXs/nns9tf7bgaAU4BMmUBTgFY7bha\nbWMhDA+FsYDWr1+PLVu24Pbt22AYBgMGDMDHH3+sDdkIQu3Is+Vv6lPz87LncPvGTabM9WtX9DDt\nIVP2ztF32C2bWnhEeXArgNrM/mE2nHo6yZRtTtzMnStI2PTbpnrndKqMhTA8FK4AbGxscOTIEfz+\n++/IyMjA0aNHMXr0aG3IRhBqRd22/M/LnnPbP11FXRHlGgXr9tbIfpmN5IfJGGA+ANeWX8Or5q/i\nYs5FXHx4Ea9avMrZ9mfmZWLwrsHIzMvkbP757PZHWY9C5PVIHM06ipGdRzYq9j9BNIRcBRAUFAQA\n8PLygre3d70XQTQ31G3L/0ncJ9zkn74sHd3ad8NS26UQCARgGAZDLIfASmSFtwa8xbV5q/9bnG1/\nx9YdUVhRiI6tO3I2/6sdV0vt9tuwdvvOPZ25A1+XXi6Niv1PEA0hdwto1qxZAABfX1+tCUMQmkSe\nLb+yNvF1fQh2TdmFvwr/woIRC2De1hz3cR9rXdaiqroKlx5f4vwAApwDcO/5PfQ068n5AYiEIqQu\nScW0w9Pwv3n/42z+p7w6Bf5j2TMKf0f25/he47HRZiPuv7iPwa0H4+HDhxjcejCC7YO565KxOPRw\ngEMPB5mxKOPnQBgmchXAoEGDAAAbN26Ek5MTnJycYG9vT3kBiGaNsnH568LnQ3D2j7O4lX8LgXGB\n6NimI8xhzm69CACBQMDZ4sc/iMfj0sfoZtqNi90vrhZj58Wd6NS2E9IepXH3j38Qj8SHibDrYsfV\nraiqwI2EG0A58NWlr2TkMjc3B2PLcG13pO6AXRc7jOs9rtF+DoThofAM4MCBAxg2bBhiYmIwe/Zs\nLF68GF9//bUWRCMI/YHPh6CuLX5ZVRmvLX5j/A/46oamhCKnXQ6vXMOHD+fydWgrZwHRchAwdU0L\n5PDkyROkpqYiOjoaV65cQXJysqZlkyE9PR22trY6a69P0Fh0Q92naQAY2XkkZ4tf+KIQpmamvLb4\nfG3l2ezz1rWyg8UNCzx79owrs7S0xNKlS2USNjXmPg3RnP4uijD0sTTURuEKIDAwED4+PtiyZQuK\niorw/vvva33yJwh9gM+HQFlb/Mb4H/DWdfbHsGHDZMqGDh1aL1uftnIWEC0DhQqgtLQUACASiWBm\nZgZzc3ONC0UQ+gifD8Gm3zZhc+JmmTK+WPuNySUgr679GHtYWloCYJ/+HR0dlW5LZqEEHwoVQFhY\nGA4ePAhvb288f/4ca9asweTJkxU1I4gWBZ8PQV1b/GCbYF5b/Mb4HzRUNzQlFIMGs8YZfE//2spZ\nQLQcFCqA4uJinD9/HidPnkR0dDSKi4vh7u6uDdkIQm/g8yGoa4vf1rgtry1+Y/wPFNVFT6BLly68\nT//ayllAtCAYBbi5uTEfffQR88svvzAFBQWKqmuMtLQ0nbbXJ5r7WOLuxzEVVRUMw0jHUlFVwcTd\nj9OhVLLUllHCZ799xvxy6xeZsujb0cxniZ8xDNPwWPj6kzdmRXUrKirqtWnKfRqiuf+P1cbQx9JQ\nG4WxgCjuP6FO6trTA/UtV3Rtqy7P5j88IxxgZOPvp+aksk/dXe3QAR0A8PsVNMb/QFHdhnxxmurn\nQBgmCreACEKd1LVVl2c7r08yyovJr29yE0RjUbgCIAh1Ujcmf+yLWLm28/oiY0Mx+fVJboJoLHIV\ngCJb/7Fjx6pdGMIwkNiqSyZRQP9s1flklNj767PcBNEY5CqAL774Qm4jgUBACoBoMuqOya8J+GTk\ni8mvb3ITRGOQqwAOHjwot1FMTIxGhCFaPnVt1Sf0nYDYslhuv10fJtO6Mvo7+GNz4mZEXo8EBGwq\nxgCnAIQmhcrITRDNDYVnAI8ePcKhQ4dQUFAAABCLxbh48SLeeOMNjQtHtDzq2qpfu3xNZr9dH8IW\n15VRaCSEc09nRGZGysTkryu3xAqIIJoLCq2A/u///g9mZma4fPkyhg0bhoKCAmzZskUbshEtENfe\nrvAb6yfzpC85dPUb66dw8g9LCUOxuFimrFhcjLCUsCbXjX8QL+Ml69rbFe+Nfk8m9r97P3fsmrwL\nu6bsgns/d05uhx4OeG/0ezJyn/3jLM7+cVbmHuJqMeIfxDc4NoLQNgoVgJGREZYuXQpLS0t4e3vj\nyy+/xHfffadU57dv38bEiRNx6NCheteSkpIwa9YseHh4YPfu3Y2XnGi2uPZ25Q2WpszkH/JbCKZ+\nP5Wb2IvFxZj6/VSE/BYiM7ErW1di8183dENSdhJ2pO6QmbTd+7lzk7+k7Y7UHUjKTuLanv3jLFZG\nr8TK0ys5JSDZUtqavJWUAKFXKFQAFRUVePLkCQQCAbKzs2FsbIycHP7Y5LUpLS3Fxo0b5R4WBwUF\nYefOnTh8+DASExNx9+7dxktPGBSLbRZjiOUQZOVnYer3U5FbnIup309FVn4WhlgOwWKbxY2uq0oM\nfT6fhro5AshfgNBnFJ4BLF68GMnJyVi0aBH+8Y9/wMjICG+//bbCjoVCIcLDwxEeHl7vWnZ2NkxN\nTdGlSxcAwLhx45CcnIz+/fs3YQiEoSASinDK6xQ3kQ/fMxwAMMRyCE55neLSKjamrjybf2Xs++X5\nNMwZMofLEUD+AoQ+o1AB9OnTB/369QMApKamoqSkBPfv31fcsbExjI35u8/Ly5MJK21ubo7s7GyF\nfaanpyuso8n2+oQhjyVwQCA8H3vKvL917ZZKdSe0nYDYF9KwJxP6TsC1y9eUkqd228IXhXijL2sg\nEf8ivkn96QuG/D+mz6hzLHIVwMuXL/HixQsEBgYiNFRqD11ZWYnVq1frxBSUMoKxGPJYJPv4xibS\nf93gO8H1VgCNqSvZozc1M+XKYstilXpir91WkhEspiQGAoGgSf3pC4b8P6bPNDUjmDzkngFkZGRg\n/fr1uHHjBhYsWMC9li5dqrITmJWVFfLz87n3T58+hZWVlUp9Ei0fyYQu2ce/tvyazD5/bYsfZeuq\nEkO/bttgm+B6OQIoJj+hz8hVAOPGjcP+/fuxZs0a/Prrr9zr3LlzWL9+vUo37d69O4qLi/Hw4UNU\nVVUhLi6ON745QdQm4vcIbkI/5XUKViIrnPI6xU3sEb9HNLquKjH067Zta9y2Xo4AislP6DWKYkkX\nFBQwmzZtYvz9/RmGYZjY2Fjm2bNnCmNQX7t2jZk3bx4zfvx4xt3dnZk3bx6zf/9+5syZMwzDMExq\naiozZ84cZs6cOUxERIRKMa2VwdBjgusrjR3L9uTtTFFFkUxZUUURsz15e5PrqhJDny+3wZm7Z5gz\nd880qT99wZD/x/QZrecD+Pjjj2Fvb4+MjAwArCfw6tWrea17ajNs2LAGw0nY29sjMjKykeqKMHR8\nx/jWKxMJRbzlytZVJYY+X53avgKN7Y8gtIlCP4Dnz59j/vz5XP7RN998E+Xl5RoXjCAIgtAsSiWE\nqayshEAgAADk5+ejtLRUo0IRBEEQmkfhFtC8efMwa9Ys5OXlYfny5bh27RrWrl2rDdkIgiAIDaJQ\nAUyePBmjRo1CRkYGhEIhNmzYQCabBEEQLQCFCqCkpATnzp3D3bt3IRAIkJeXh+nTp6NNmzbakI8g\nCILQEAoVwAcffABTU1PY2NiAYRikpaXhwoULDWYMIwiCIPQfhQqgsLAQe/fu5d7PnTsXXl5eGhWK\nIAiC0DwKrYC6d++OvLw87n1+fj569eqlUaEIgiAIzaNUSkh3d3f0798fNTU1uH//Pvr16wdvb28A\nUDo5DEEQBKFfKFQAvr71vSkJgiCI5o9CBTB69GhtyEEQBEFoGaU8gQmCIIiWBykAgiAIA4UUAEEQ\nhIFCCoAgCMJAIQVAEARhoJACIAiCMFBIARAEQRgopAAIgiAMFFIABEEQBgopAIIgCAOFFABBEISB\nQgpAQ8THA2KxbJlYzJYTBEHoA6QANEB8PLB1KxASIlUCYjH7futWUgIEQegHpAA0gIMDYGcHpKWx\nk35JCfszLY0td3DQtYQEQRCkADSCUAisWSNVAp6e0sl/zRr2OkEQhK4hBaAhhELA31+2zN+fJn+C\nIPQHUgAaQiwGQkNly0JD6x8MEwRB6ApSABpAcuAr2fY5ckT2TICUAEEQ+gApAA2QlCS759++veyZ\nQFKSriUkCIJQIicw0XhcXdmfDg7SPX+hkH3v4CC9DrCrgaQk2TKCIAhtoFEFEBwcjCtXrkAgECAw\nMBAjRozgrrm5ucHa2hpGRkYAgNDQUHTu3FmT4miVuhN6fDywYwe7Chg3jlUItbeK+NoQBEFoEo0p\ngNTUVPz555+IjIzEH3/8gcDAQERGRsrUCQ8PR/v27TUlgl7h4ACcPy89B/D3Zw+FyTeAIAhdobEz\ngOTkZEycOBEA0K9fPxQWFqK4uFhTt9N7yDeAIAh9Q2MrgPz8fAwdOpR7b25ujry8PIhEIq5s3bp1\nyMnJga2tLfz8/CAQCBrsMz09XSWZVG2vDiZMaIXY2D613t/HtWs1je5HH8aiLmgs+gmNRT9R51i0\ndgjMMIzM+/feew/Ozs4wNTXFihUrEBMTgzfffLPBPmxtbZt8//T0dJXaqwPJnr+pqbQsNnZUo1cA\n+jAWdUFj0U9oLPpJU8bSkMLQ2BaQlZUV8vPzufe5ubl45ZVXuPfTp0+HhYUFjI2N4eLigtu3b2tK\nFL2AfAMIgtA3NKYAHB0dERMTAwDIzMyElZUVt/1TVFSERYsWQfz3rHfp0iUMGDBAU6LoBeQbQBCE\nvqExBWBjY4OhQ4fC09MTQUFBWLduHX788UecPXsWHTp0gIuLCzw8PODp6Qlzc3OF2z/aRtl4/itX\nAs+fy5Y9fw7MmCHb3tWVNf8cPVrWN8DPD5gwQdYElHIJEAShDTR6BuBfJxraoEGDuN8XLFiABQsW\naPL2TUYSz//8eamFDp/N/sqVQHg48MsvQHo6YG7OTv5DhgC5uYCTE/Dbb2z7s2fZugBgbAy4u7N9\nbt3K9jlyJNunMvfu0EH7nwlBEC0PCgXBg7Lx/DdsALp2BR49Amxtgfv32Z8FBexBb6dO0vYJCdL+\nL1yQ3yflEiAIQltQKAgeJDb7konX05Mtr2uzb27OPvnb2rJKQLLA6doVSE4G9u6Vbe/hATAMcPmy\n/D6VvTdBEISq0ApADsrG8zc3B379Vbbs118Ba+v67VevBgICFPdJuQQIgtAGpADkoGw8/+fPATc3\n2TI3N+DJk/rtN28GNm1S3CflEiAIQhuQAuBBWZv958+l2z9duwI3b0rPBAYPZk07Je1HjQIiI4Gj\nR9kDX3l9kr8AQRDaghQAD8ra7H/yiXTyT08H+vRhf3bqBBQWsofBkvbOztL+XVzk90n+AgRBaAs6\nBObB1RWIigL+8x/Zw9m//gKsrKQ2+2FhVXjy5AnMzYHSUvYFADEx7KQdFWUNoZD9iN3dgSVLgKFD\n2d8lffr5ARER0j7l5RJYs0aaN6AFhTUhCEKHkALgISwM+OEHIDMTOHUKEImApUuBAwcAgQDo2xdY\nuxb4+WcG3bv/iE6dCvDVV7J9vPaaOZKTl2PCBPZ9fDxr219Swjp+Sez76/oBAPx5AYRCyhdAEIR6\noS0gHhYvZp25srKAqVNZp66sLHbyZxhg3z7W5t/X1wRXrozg7aNNm+Fwdjbh3pN9P0EQ+gatAHgQ\nidgn/6lT2Yl/+HC2fOxYIDubtfCR2PwbGTmiujoTRkb5tXqwhL+/o4zZJtn3EwShb9AKQA4iEWu1\nU5sff6wfj+fcORM4OQ2VKXNwGIr27U1QF7LvJwhCnyAFIIfiYtZztzYzZ9bfhx8/Hvj1V0eUlloC\nAEpLLZGU5Mhrrkn2/QRB6BOkAHgoLpZu/wwZAly7BgwYwIZ3yM5mvXxv3gS6dAEePgR27DCBiQm7\nCmjXbijS0kzq2eyTfT9BEPoGKQAeIiKkk/+pU6zp55Ah7AGwQMBaBPXpA+zYIbXmefbMEV26dIG/\nvyOvzT7Z9xMEoW/QITAPvr7sz8WL2bMAgLX8AYBevVgTUACYNo19kj99GvjySxOIxf+EUGgiY7Mv\nQRn7foIgCG3SolcAyiZWCQtjt31qc+5c/f3648fZ8tq8/z7rNAYAwr9n9r/+AiZPZn/W5vFj5SZ6\nSghDEIQ2aLErgLqJVQD+pC5hYWzZiRNSp6+332aTvERHs/XWr2e3gfLy2H7Hjwfi4oB+/YB799g6\nr7zCXr97lz0vANjVwp9/Aj17AocPA/PmATU17CogKYlfHkoIQxCEtmixK4C6jldlZa14Ha/4nL6e\nPZM6fYWFsR7BkjAPADtJnzghnfwBts2FC2wQuNoMHAhcugQsXMhO/q1aAWPGUEIYgiB0T4tVAJL9\ndclkGhjYR+YQVrIPL3H6kiiB4cPZif3119msXi9fsmWlpezBrYTp06W/S5TFuHFAVRWb8jE+HmjT\nBigvZ/MAV1QArVsDq1YBd+6wjmB88tSVW149giAIVWmxCgBQ3vGKz+nrxAkgMVG27OJF9hygNseP\n19+bj41llcGFC7LlCQnAxo2K5SGHMYIgtEGLVgDKOl7xOX394x+Ao6Ns2euvyz75A+z7uge7Eyaw\ne/guLrLlzs7Axx8rloccxgiC0AYtVgHUdbwKDr7P63jF5/TVty/7tF9YCHTsyJa1a8fux0uovRKQ\n+AecP89u/1RVsUqhvJzdBkpNZbd/KiqAzz9nD4kpIQxBELqmxSqAuo5XbdvW8Dpe8Tl9WVhIJ3Vf\nXzaGf7t20r5dXdkVQt++0jILC/aJ/8YNWTlu3QLs7dlQ0q1asQfBKSmUEIYgCN3TYs1A5TleOTiw\nL8l1X1/2iX3IEKnT188/s6agdnasCSjAWgeZmrJx++Pi2LI//gDatgWMjFgTUADo3589O3ByAh48\nYE1AAWDuXPbnzp3SSZzPEYwSwhAEoS1a7AoAYCfL2gen8fFs+AaJDT7A/iwpAb78UvYw9+efpZO/\npK2LC5vwXdJ22jR2m6eiQuoM9uQJ8NZb7O+rVsnKM3du/Sd4vkQvdeWWV48gCEIVWrQCqIsqNvZ8\nbQcOlO75L17M+gsMHsyeHZiaskqFIAhCXzEoBaCKjT1f25s32S2k2v4Cksn/xg02aihBEIS+YlAK\nAFDNxp6v7fr19f0FfvuNJn+CIPQfg1MAqtjY87Vdv76+v4CTE3sWQBAEoc8YlAJQxcaer+2gQWys\noNr+Aqam7PvBg0kJEASh3xiUAlDFxp6v7a1b0tg/ERGsv8CNG1Il8K9/aW9sBEEQjaXF+gHwoUpS\nFr62J0+ypqDz5wOzZrFl1tasEvjXv4CfftLAIAiCINSERhVAcHAwrly5AoFAgMDAQIwYMYK7lpSU\nhG3btsHIyAguLi5YsWKFJkXh4JvklbWx56tz8mT9MmtrmvwJgtB/NLYFlJqaij///BORkZH49NNP\n8emnn8pcDwoKws6dO3H48GEkJibi7t27mhKFIAiC4EFjCiA5ORkTJ04EAPTr1w+FhYUo/jvvYnZ2\nNkxNTdGlSxe0atUK48aNQ3JysqZEIQiCIHjQ2BZQfn4+hg4dyr03NzdHXl4eRCIR8vLyYG5uLnMt\nOztbYZ/pKgbBUbW9PkFj0U9oLPoJjYUfrR0CMwyjch+2trZNbpuenq5Se32CxqKf0Fj0E0MfS0MK\nQ2NbQFZWVsjPz+fe5+bm4pVXXuG99vTpU1hZWWlKFIIgCIIHja0AHB0dsXPnTnh6eiIzMxNWVlYQ\n/R1vuXv37iguLsbDhw9hbW2NuLg4hNZ1seWBtoCk0Fj0ExqLfkJj4UfAqGNvRg6hoaFIS0uDQCDA\nunXrkJWVhQ4dOsDd3R2XLl3iJv1JkyZh0aJFmhKDIAiC4EGjCoAgCILQXwwqFARBEAQhhRQAQRCE\ngUIKgCAIwkAhBUAQBGGgkAIgCIIwUAxCAdy+fRsTJ07EoUOHdC2KymzZsgUeHh545513cObMGV2L\n02TKysqwatUqzJs3D7Nnz0ZcXJyuRVKZ8vJyTJw4ET/++KOuRWkyFy9exJgxY+Dj4wMfHx9s3LhR\n1yKpxMmTJzFt2jTMnDkT8fHxuhanyfzwww/c38THxwejRo1SS78tPh9AaWkpNm7ciLFjx+paFJVJ\nSUnBnTt3EBkZiYKCAsyYMQOTJk3StVhNIi4uDsOGDcOSJUuQk5ODd999F+PHj9e1WCrx5ZdfwtTU\nVNdiqMzo0aOxY8cOXffIQZkAAAiiSURBVIuhMgUFBdi9ezeOHTuG0tJS7Ny5E67KxH3XQ2bPno3Z\ns2cDYCMtnz59Wi39tngFIBQKER4ejvDwcF2LojL29vZcToWOHTuirKwM1dXVMDIy0rFkjWfKlCnc\n748fP0bnzp11KI3q/PHHH7h7926znWBaIsnJyRg7dixEIhFEIlGzX81I2L17t1KRE5ShxW8BGRsb\no02bNroWQy0YGRmhXbt2AICoqCi4uLg0y8m/Np6envD390dgYKCuRVGJzZs3IyAgQNdiqIW7d+9i\n+fLlmDt3LhITE3UtTpN5+PAhysvLsXz5cnh5ebWIkPNXr15Fly5duLhqqtLiVwAtkXPnziEqKgr7\n9+/XtSgqc+TIEdy4cQMffvghTp48CYFAoGuRGs3x48cxcuRI9OjRQ9eiqEzv3r2xcuVKTJ48GdnZ\n2Zg/fz7OnDkDoSQPajPjxYsX2LVrFx49eoT58+cjLi6uWf6PSYiKisKMGTPU1h8pgGZGQkIC9uzZ\ng4iICHTo0EHX4jSZ69evw8LCAl26dMHgwYNRXV2N58+fw8LCQteiNZr4+HhkZ2cjPj4eT548gVAo\nhLW1NRwcHHQtWqPp3Lkztz3Xs2dPWFpa4unTp81SuVlYWGDUqFEwNjZGz5490b59+2b7Pybh4sWL\n+Oijj9TWX4vfAmpJFBUVYcuWLdi7dy/MzMx0LY5KpKWlcSuY/Px8lJaWolOnTjqWqmmEhYXh2LFj\nOHr0KGbPno1///vfzXLyB1irma+++goAkJeXh2fPnjXb8xknJyekpKSgpqYGBQUFzfp/DGDD5rdv\n316tq7EWvwK4fv06Nm/ejJycHBgbGyMmJgY7d+5slhNodHQ0CgoK4Ovry5Vt3rwZXbt21aFUTcPT\n0xNr166Fl5cXysvL8cknn6BVK3oe0TVubm7w9/dHbGwsKisrsX79+ma7/dO5c2e88cYbmDNnDgDg\no48+atb/Y3UzKaoDigZKEARhoDRfdUgQBEGoBCkAgiAIA4UUAEEQhIFCCoAgCMJAIQVAEARhoJAC\nIFoc58+fx4sXLxqs4+Pjg6SkJJmyixcvYu7cuWqX58SJEwDY0AQuLi5Ktdm1axdnj98UXr58CU9P\nTzx9+rTJfRAtH1IARIvj66+/RmFhoa7FAABUV1fjiy++aFSbq1evIjExEYsWLWryfTt27IiVK1di\n7dq1Te6DaPm0eEcwonlz8eJFhIWFoWvXrsjJyUGHDh2wfft2iEQiREdH49ChQ2AYBubm5ggKCsLp\n06eRlpYGf39/hISE4P79+4iIiIBQKER1dTW2bNmC7t27K7zvo0eP8N///hdlZWUoLS3FBx98AAcH\nBwQEBMDKygq3b9/G/fv3MWvWLCxZsgQFBQXw8/NDaWkpevfujUePHmH58uU4ceIEF+56w4YNAIDt\n27fj0qVLKC0txd69e+t52n755Zf45z//CQCoqalBUFAQrl+/DgBYuHAhJk+eDDc3N3h6eiIhIQF5\neXlYvXo1IiMjcffuXaxYsQIzZsyAk5MTPvvsM9y4cQODBw9W7x+GaBkwBKHHpKSkMMOHD2eePHnC\nMAzD+Pv7M9988w3z6NEjZurUqUxFRQXDMAzz9ddfMyEhIQzDMMz48eOZBw8eMAzDMFFRUUxOTg7D\nMAyzZ88eZtOmTQzDMMy8efOYxMTEevfy9PRkGIZhlixZwiQnJzMMwzC5ubnM+PHjmcrKSmb16tWM\nr68vwzAM8/DhQ8bGxoZhGIbZtm0bExwczDAMw9y6dYsZOnQok5iYyGRnZzPOzs4MwzBMdnY2M3jw\nYObWrVsMwzBMYGAg89VXX8nIUFVVxYwcOZIpKipiGIZhfvrpJ+Y///kPwzAMU1hYyCxZsoSpqqpi\nxo8fzxw9epRhGIZZvXo1s2DBAqampoZJSUlhpk2bxvW3adMmZu/evU367ImWD60ACL2nf//+3FOy\njY0Nbty4AUtLS+Tl5XHbJGKxmPfJ3tLSEqtXrwbDMMjLy1M6k9LFixdRUlKC3bt3A2DDij979gwA\nmzAFALp164bi4mJUV1fj5s2bXMiBV199FX369OHtt1OnTnj11VcBANbW1nj58qXM9RcvXsDExAQi\nkQgAux30+uuvA2C3dfbt28fVtbGxAcCGPOjcuTMEAgGsra1RVFTE1enWrRtu376t1JgJw4MUAKH3\nMLWilTAMA4FAAKFQiBEjRmDv3r1y21VWVsLX1xc//fQTevfujUOHDnFbKYoQCoXYuXMnb+wVY2PZ\nrw3DMKipqZGJMyMv5kzd/A2MgkgsAoEANTU1vNdqy1FXJoJQBjoEJvSee/fuITc3FwCQnp6OgQMH\nYvjw4bh69Sry8vIAAKdPn8a5c+cAsJNmVVUVSkpK0KpVK3Tr1g0VFRWIjY2FWCxW6p62trZc2r3n\nz5/j008/bbB+3759kZGRAYBNqHLv3j0ArCKoqqpSeqxmZmaorKxEcXExAGDUqFFISEgAABQXF2P2\n7NlKjwEAcnJylDrzIAwTUgCE3tO/f39s27YNc+fORUlJCaZPn47OnTtj7dq1WLZsGby9vREVFYWR\nI0cCYMMAL1++HPfu3cPbb7+NWbNmwdfXF4sWLUJKSopS+VTXrl2Lc+fOwcvLC0uXLsWYMWMarL9w\n4UKkpKTAy8sL3377LYYOHQojIyNYWVnB0tISM2fORFlZmcL7GhkZYcyYMZyJ6uTJk9G9e3d4enpi\n4cKFWLhwYaOicyYnJ8PZ2Vnp+oRhQdFACb1GYgV0+PBhXYvSIPfu3UN2djbGjRuH8vJyTJw4EVFR\nUbC2tm50X1evXkVISIjKY05MTMSBAwcQERGhUj9Ey4VWAAShBjp06ICvv/4aHh4e8Pb2xtKlS5s0\n+QPAiBEj4OjoqLIj2M6dOxVuXRGGDa0ACIIgDBRaARAEQRgopAAIgiAMFFIABEEQBgopAIIgCAOF\nFABBEISB8v8hOBrNMnuovAAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<matplotlib.figure.Figure at 0x7f8ce9a6ca90>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "metadata": {
        "id": "s2khewKZ33_w",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Based on these two features, it is easy to distinguish iris setosa from the two remaining species. Yet iris versicolor and virginica remain mixed together. \n",
        "\n",
        "Looking closely at the plot, we might estimate the species of the selected unknown irises (gray triangles). For three of them the answer seems obvious – they belong in uniformly-colored areas covered by one species only. Yet unknown iris flower in (5.1, 1.7) is troublesome – it lays on the boundary of versicolor and virginica clusters. We can assume, that its species is the one of the closest one to it, coming from the training set (and so having a label). \n",
        "\n",
        "K-Nearest Neighbors method (http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm) solves the classification problem, i.e. sets class labels (species in case of irises) of a previously unseen sample by choosing the most common class among the top k neighbors of the sample in question (for instance according to the Euclidean distance). Thus, the k-Nearest Neighbors algorithm works as follows. For each unlabeled sample x:\n",
        "1. Find k nearest neighbors among the labeled samples.\n",
        "2. Set the most common label among them as label of x."
      ]
    },
    {
      "metadata": {
        "id": "8-G-sMUw33_x",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Problem 2 [2p]\n",
        "\n",
        "1.  **[1p]** Load the iris data (in Python it’s built-in into machine learning libraries, use sklearn.datasets.load_iris), the data is also available on-line at https://archive.ics.uci.edu/ml/datasets/Iris\n",
        "\n",
        "2.  **[1p]** Irises are described with 4 attributes: petal and sepal widths and lengths. We often plot such data as matrices depicting relationships between pairs of attributes (the diagonal of which holds an ordinary histogram). Write code making a plot like the one below. Please pay attention to the details: make a proper legend and correctly label the axes.\n",
        "\n",
        "<img src=\"https://github.com/janchorowski/nn_assignments/blob/nn18/assignment1/iris4x4.png?raw=1\"/>"
      ]
    },
    {
      "metadata": {
        "id": "F6sG0bxf33_y",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Problem 3 [2p]\n",
        "\n",
        "Implement the k-Nearest Neighbors algorithm. Try to\n",
        "take advantage of matrix calculus rather than using for loops.\n",
        "\n",
        "**Tip:** What is computed by \\begin{equation} \\sqrt{(X - Y)^T (X - Y)} \\end{equation} when both X and Y are vectors?\n",
        "\n",
        "**Tip:** Try to use broadcasting (NumPy: http://docs.scipy.org/doc/numpy/user/basics.broadcasting.html) and built-ins sort, numpy.sort, numpy.argsort (sorting), scipy.stats.mode (choosing the most common element of the set)."
      ]
    },
    {
      "metadata": {
        "id": "1iZtHs5A33_z",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Problem 4 [2p]\n",
        "Consider the following experiment:\n",
        "1. We scramble the data and split it into two parts - training set (66.6% of all samples) and test set (33.4%).\n",
        "2. Based on the training set, we use the k-NN algorithm to predict the labels on the test set.\n",
        "3. We then check the number of errors and write it down.\n",
        "\n",
        "Do this 500 times for k ∈ {1, 3, 5, ..., 19}. Plot a function of the average number of errors\n",
        "as the function of k. It should be similar to the one below.\n",
        "\n",
        "<img src=\"https://github.com/janchorowski/nn_assignments/blob/nn18/assignment1/knn.png?raw=1\"/>"
      ]
    },
    {
      "metadata": {
        "id": "A86GnZpa33_0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Problem 5 [2p] \n",
        "\n",
        "Apply the K-Nearest Neighbors (K-NN) algorithm to the MNIST and CIFAR10 datasets. \n",
        "\n",
        "The MNIST (http://yann.lecun.com/exdb/mnist/) dataset consists of normalized (centered and stretched) scans of hand-written digits. Specifically, each element of the dataset is a 28 × 28 grayscale image, thus having 764 8-bit pixels. \n",
        "\n",
        "The CIFAR10 (http://www.cs.toronto.edu/~kriz/cifar.html) dataset consists of small, 32 by 32 pixels, RGB images belonging to 10 categories.\n",
        "\n",
        "1. **[1p]** Download and load the MNIST and CIFAR10 datasets. For both datasets, display a few objects from each of the classes, paying attention to aesthetics and clarity of your presentation. **Note:** You already downloaded the datasets in \"Setup\" section. Please use the code below to get started.\n",
        "\n",
        "2. **[2p]** Apply a k-NN classifier to the MNIST and CIFAR10 datasets. First, divide the training set into two parts, which we will call training and validation. On MNIST use the first 50000 samples for training and the last 10000 for validation. On CIFAR10, use 40000 to train and 10000 for validation. Then find the optimal number of neighbors by assessing the accuracy on the validation set. You do not need to repeat this experiment multiple times. Finally, compute the accuracy on the test set obtained with the best previously chosen number of neighbors. On MNIST you should get about 3% errors, while on CIFAR10 you should get about 70% errors. Why CIFAR10 is harder than MNIST? Pick a few mislabeled samples from the test dataset and plot them along with the correct ones. **Note:**\n",
        "  * MNIST and CIFAR10 are much larger than the Iris dataset. A good implementation may need a few minutes depending on your runtime type. Please optimize your algorithm:\n",
        "  * Compute the distances only once, then test for different values of k.\n",
        "  * Use vectorized expressions to compute the distance. It is possible to compute all distances between the training and testing points in one expression. Hint: think about the vectorized expression \\begin{equation}(X - Y)^T (X - Y)\\end{equation}.\n",
        "  * You can use single precision numbers in computation.\n",
        "  * If your code is taking a long time to execute, please save its results before the lab session.\n",
        "\n",
        "**Note:** in NumPy, matrices have its own data type (dtype), which is retained during\n",
        "calculations. Please pay attention to it. I particular, do not subtract values of data types not\n",
        "having the sign bit, do not divide integers, etc. Results of such operations will not be\n",
        "automatically casted to types having the required precision."
      ]
    },
    {
      "metadata": {
        "id": "3AvAeiDN33_1",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "with np.load('mnist.npz') as data:\n",
        "    mnist_full_train_data_uint8 = data['train_data']\n",
        "    mnist_full_train_labels_int64 = data['train_labels']\n",
        "    mnist_test_data_uint8 = data['test_data']\n",
        "    mnist_test_labels_int64 = data['test_labels']\n",
        "        \n",
        "# Split train data into train and validation sets\n",
        "mnist_train_data_uint8 = mnist_full_train_data_uint8[:50000]\n",
        "mnist_train_labels_int64 = mnist_full_train_labels_int64[:50000]\n",
        "mnist_valid_data_uint8 = mnist_full_train_data_uint8[50000:]\n",
        "mnist_valid_labels_int64 = mnist_full_train_labels_int64[50000:]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "aenFc3L633_4",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 268
        },
        "outputId": "8da070dc-d6d9-4431-ae08-0aaa66a0a836"
      },
      "cell_type": "code",
      "source": [
        "plot_mat(mnist_train_data_uint8[:20, None], cmap='gray')"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAATYAAAD7CAYAAADgvbh3AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJztnXm8VdP7x9+JSiKlREhpkDI0KCFJ\nA6mkDGWoFEJ+Eok0yFA0UEgi4gpRkaREZcqQKdQXhTJThq4oRSl+f5zXZ697zp3v3Wda93n/c+uc\nPax9zj5rf9Yzlvrvv//+wzAMwyN2SfYADMMwwsYmNsMwvMMmNsMwvMMmNsMwvMMmNsMwvMMmNsMw\nvMMmNsMwvMMmNsMwvGPXZJ68VKlSyTx96GSNdfb52sCv6/P52qBk3ZfCFJthGN5hE5thGN5hE5th\nGN5hE5thGN5hE5thGN5hE5thGN5hE5snNG3alKZNm5KRkUFGRgY7d+5k586dZGRk0KRJE5o0aZLs\nIRpGwrCJzTAM7yiVzAq68QoWLF26NAAVK1bM8f0rrriC8uXLA3DooYcC8H//938A3HHHHQCce+65\nAPz999+MHTsWgJtvvjnP8yYjELJRo0YAvPLKKwDstdde2bb5448/ANhnn32KfJ50CGJt27YtM2bM\nAODEE08E4PPPP893v1S8thEjRgDunttll4gGad26NQBLly4t8LEsQNcwDMMDkppSVRxq1KgBQJky\nZTjuuOMAaNmyJQB77703AGeeeWa+x/nhhx8AmDRpEgDdunUDYPPmzQCsXLmyUE/HRNG8eXMA5syZ\nAzh1qieYxr99+/ZAqbVo0QKADz/8MHgvHrRq1QpwCnHu3LlxOU8szZo14/3330/IueJFnz59ABgy\nZAgA//77b9T71qKkYJhiMwzDO9JOscXalHKzo+WHnoSyZfz5558AgY1m/fr1AGzcuLFAdppEUL58\n+cC7+fjjjwOw//7757jtmjVrABg/fjwzZ84E4K233gLcNY8ZMyYu45QdqG7dukD8FZvsT7Vq1eLg\ngw8G0teWpPGXK1cuySMpHMcccwwAPXv2BJyNs2HDhlHbDR48GIB169YFKyzdy++++25o4zHFZhiG\nd6SdYvvuu+8AyMzMBAqm2PQk+P333wE46aSTAvvSY489Fo9hxoWpU6cG3tr8kLKrUKFCYCOUkjry\nyCPjMj7Ru3dvAN5+++24nkdItfbr1y94+n/22WcJOXeYtGvXjgEDBkS9puvo3LkzAD///HPCx5Uf\nPXr04O677wagSpUqgFPMr732GgBVq1YF4Pbbbw/20zZ675xzzgltTKbYDMPwjrRTbL/99hsA1157\nLRB5kn300UeA82yKFStWANC+fXsAtmzZAkTW/QMHDkzIeMOgadOmAHTq1Cmb7UhqbP78+YCLw1u3\nbh0AH330ERs3bgSgTZs2QPztT7J5JYpp06YF/5ZtMZ2QrSkjIyPbCkQK59tvv034uHJj110j08bR\nRx8NwIMPPhjEhb7++usAjBo1CoA333wTgLJlywIwe/ZsAE4++eTgeMuXLw9/jKEfMUE8++yzQMSJ\noNCGo446CoCLLroIcD9yTWji008/5ZJLLknUUIuMHCVLliwBIsG3cve/8MILgAsklrFWjgH92H/9\n9VdWrlwJOIdJp06dALdcVfhHcdESt1q1aqEcr6BknQz0WaUTF1xwAQDVq1cPXtMS7tFHH03GkPJE\nDoKsDxR97j169ABg06ZNUfvo9awTmkKtpk+fHvoYbSlqGIZ3pK1iE1mfDEodEv369QNg1qxZQPZg\nx1SlXr16gFtuS5Fs2LAhCEPRU05hKs8//3zU37zYfffdAbjmmmsAOP/880MZd8eOHaOOH2+kDGvV\nqhW89uOPPybk3GEgQ/uFF14IRO5PObhGjx6dtHHlhpaXw4YNA1yw8JQpU4KVQqxSE8OHD8/22pVX\nXglEVhVhY4rNMAzvSHvFlpWbbroJcMZ22Z3atWsHwOLFi5MyroIiA6tsg1JAsiH27t07MLSGoYqU\nlhYWKiggPv3001CPH4s+Jym3L774IvisUpmaNWsCLh0uK/fccw8Ar776aiKHlCcjR44EnFJTqNSi\nRYuASPrXX3/9FbWPAoxlU9O9JsfV6NGjmTdvXtzGbIrNMAzv8Eqxyfsp25q8fQ8++CDgnoLLly/n\n3nvvBVIrqbhx48aAU2ri9NNPBwpXqiYVCCshXaWYOnToADivXFYPG0RsQLJRpTK6jthA6ZdffjkI\ndE0FVEzi8ssvB9xvRUqta9eu2fapU6cO4FITtXoSTz/9NBBJ9YsnptgMw/AOrxSb+PLLLwFXAiYj\nIwOAXr16BX/32GMPwMUJyduYTCZOnAg4O4QUWlhKTYGzifIOV65cOdf3FHOoa5Ud9MADDwQi5ajk\nrdW4ZcdRity2bdsAFzD6wQcfhDr+sJHCUeFSoSDWCy64IJtnP5mUKVMGcN5bIW/mvvvuC0Dfvn3p\n0qULAIcffjgQSeUDp/L0VylvsbGlYWOKzTAM7/BSsQmVy1GajRRR27Ztue222wBXJubWW28FkhMH\npQRnZRro6fbcc8+Feh4pNR1fKWdhIUWl499///2A86ZlRfYlKbYdO3YAsHXrVgBWrVrFww8/DLiU\nGylXJYIrcl0e4lRNfM/LCwrw1VdfAamX4C7vp+LMlKz+9ddfAznbp5XKp3g2FSjYsGED4FL/4o0p\nNsMwvMNrxSY++eQTALp37w7AaaedFtjdLr30UsAVRVTCfCKR4pBN45dffgFcxkRxKFu2bBDfJ1Sk\nc+jQocU+flbkPVPCtkq254TKTynnd/Xq1QC88847+Z5Heb5SEFI8qUpuZb5FrM0tVZCHWbbBBQsW\nAM52Klv2vHnzeOSRRwBXpELFTaXY9P9EUSImNqEv6rHHHgsSeGV4Vp1+1SxTEnIykFG8OA4NBfuO\nGDEiSM3S0m3ChAmAS8cKm3HjxsXluKJt27ZR/89tiZdsZFqIDUsRClBNlQrNuSFnjR4keaHfkYLj\nNZkn+uFjS1HDMLyjRCg2GarPOussINLNSEpNrFq1CnD1pJJJcZwGUglSaT169AiUQUG6dqUjieqC\nVViUwlepUqWo17XcVjiST8isEuuoSvRS1BSbYRje4aViUzL2FVdcAcAZZ5wBwH777Zdt2507dwLO\nnpWM0kYKedBfGWsLU+X36quvBuCGG24AXKmjGTNmBD0IjMSivqqx99SUKVOA+Nk4k4nSrZKNKTbD\nMLzDC8UmJaYy2VJqCozMCQV9KjA37GDYwhCbdqLrUQ8HBapmZmYG3dyVHqbUJKUiKYxCT06pAx+R\nwlVhzoKEiiSKjIyMXHs/LFu2LMGjSRynnHJKsocAmGIzDMND0laxqbhggwYNmDx5MgD169fPcx/F\n49x+++2BpzAVy4WXLl0acAGv8mZu2rQpCCSORSpApZlUHNBnpHAT3RUrL+SVbteuXXBvKTVJpbJS\nLXUqTA455JBkDwEwxWYYhoekjWJTGsfUqVMB92TM6wkhFaNIe9mdYssYJxt1TFdhxmbNmkW9L5tb\n1rZ2mZmZgIsPSqc+qWFz7LHHAgRpPclExRmzeuBVWGHw4MFJGVMieeONN4DEl8iKJWUntmOOOQZw\ngabNmzcH4IADDsh1H1WGkNFdFTziXfupuCjVSWEpyl9V55+sqMLqfffdB8DatWsTMcSUJN6Nn43C\no7xsVdSR8KhduzYQn45UOWFLUcMwvCNlFVu3bt2i/saiFKgFCxYEtby05EyHuvc5oSBhVeOIrcph\nRHjhhRcAOPvss5M8kuyoJtyyZcto2bJlkkeTPLRaUrEJhVUNGDAAcL/feGGKzTAM7yj1XxLbNPlm\nI8n6Ufp8beDX9fl8bZCc+1KdxWbPng24nhbPPPMMEOmTEIbtO7fpyxSbYRjeYYotREyxpSc+Xxsk\n976UcpONrX///kCklFgYdjZTbIZhlBhMsYWIKbb0xOdrg5J1XwpTbIZheEdSFZthGEY8MMVmGIZ3\n2MRmGIZ3JDWlymdDps/XBn5dn8/XBiXrvhSm2AzD8A6b2AzD8A6b2AzD8A6b2AzD8A6b2AzD8A6b\n2AzD8A6b2AzD8I6ULQ1u5IyauVx55ZWAa57RuXNnAL799tvkDMwwQuLll18GXMxdmzZtCn0MU2yG\nYXhHiVJse+65JwAVKlSgU6dOAFStWhWAiRMnArBt27bkDK4A1KxZk549ewKuX+Nhhx0GQP369YH0\nVWz16tUDYLfddgOgVatWTJkyBSh4b8p58+ZxzjnnAK77eiqhazvuuOMA1/Dk+OOPT9qYUok777wT\ncJ/Po48+WuRjmWIzDMM7vFZsNWvWBGDIkCGA6xh++OGHZ9t2//33B5ztKhX59ddfef311wHo0qVL\nkkdTPBo2bAhAnz59ANdKTx3Eq1evHii1glbW6tKlC/fffz8AV111FQCbNm0KbczFpWLFigC8+uqr\nAPz000+A6xqv/5c0xo4dC8Bll10GwD///AM4W1tR8Gpi03JMN/X5558PwO677w44Y+T333/P5s2b\nAbeU6969O0Cw/FF/yFRiy5YtabvUjGXMmDEAdOzYMdTj9u7dG4CHHnoIgLfeeivU44eJJrSSPrG1\naNECcEv1N998E3AdroqCLUUNw/COtFdsFStWZNy4cQD06NEDcE6CWNasWQPAKaecEjwdpMyqVKkS\n9TcV2XvvvTnqqKOSPYxQWLJkCZBdsf3yyy9ARHFpWRrrPJBx+cQTT4z3MOOKTyWEWrVqBcDw4cMB\nOPfccwH47bffct1H28g09OWXXwIwePDgYo/HFJthGN6R9oqtW7duXHzxxXluoydB+/btgYiNrU6d\nOnEfW9iUL1+eGjVq5Phes2bNAKdAU90Wd9999wHw7LPPRr0uw3Fe9ib1qlRwcvXq1YP3dLzly5eH\nN9g4IadIuXLlkjyS4vPAAw8AULduXQAaNGgAOHtZTgwbNgyAffbZB4B+/foBsHLlymKPxxSbYRje\nkfaKTWECWfnmm28AeP/99wEX7vH9998H28gbmk6sW7eORx55BICbbrop6j39//fffwdg8uTJCRxZ\n4dmxYwcQ/Z0UlFNOOQWASpUqZXvvhx9+AFI70DqWo48+GoB33nknySMpOlu3bgUKrkIbNWrEwQcf\nDDgbapjK1RSbYRjekfaKrV+/flxyySUALF68GIC1a9cCzsOWE9WqVYv/4OLAqFGjgOyKrSSgdCnZ\nYhSfmJWRI0cmdEyFQSr1jz/+AFzAbu3atZM2pjAYNWoURxxxBACrV68GcreT7bHHHkBkFVW+fHnA\nKdWnn346tDGZYjMMwzvSXrGtW7euSOpF6VXpSm4xXj6hzJHrr78eIPBkKwYxlhUrVgRe1VRE9s83\n3ngDcKWm0pWDDjoIiChoqdErrrgCiKT/5YSKTZx99tmsW7cOiE8RgLSf2PJCeZ+Sv1mRdBbLli0D\n4O23347/wEKgsHmUqYbyeHv16gVAu3btsm3TsmVLIPdrVB6oJr6FCxfy119/hT1UIwYF1M6dOxeI\nBLXfc889ACxdujTHfRR0q9xggFtvvTVuY7SlqGEY3uGFYpMRUkGBN954I5A9XSen5ZvkcN++fQHY\nuXNnfAdbwtHT/rnnngPINeC4IGhJp+DQdEUBqqnKrrtGpgnVAlSBgay/J5l2hg4dCrglZ+XKlQEX\nlqU0skcffZSpU6fGbcym2AzD8I60VWwyIDdu3Jg5c+YArqaa7CxSY7KbdejQAXAKD9zT6IwzzgBc\nT4FUrMDqE3py55UInp+DRMb3U089FYAXXnghzCEmjFSvracwm2nTpgHO5qnvZe3atUGQsf6efvrp\nABxwwAGA+23KqXDhhRfGdcym2AzD8I60U2xlypQBnPp65plngvduvvlmAF555RXAFRnUOl+vZ62g\nq54HKnz43XffAS6ZOlVTc3JTMyofk6opVUpcb926NeDsNosWLQLg77//znXfiy66CIABAwbEcYTx\nRxV0Uz3cQ2XAMjIyAFegQGEr5513HgAbN25kwoQJgCslJeUmRS6Vp7Jg33//fXAPqEhFmJhiMwzD\nO0r9l8RAqMIU2pNN7ZZbbgHg2muvDd6TbUUxUXqiSI0tXLgQgCZNmgAR+9n48eMBp95kExAvvfQS\nAOPGjWPjxo1R761YsSLHMWb9KONdRFDe29y+viOPPBKAVatWhXK+2PMko0iiUpAyMzOjXj/ttNOA\notvYEn1tZ555JgBPPfUU4GzCDRo0iEu5qaLel1rhKFl99OjRgFNwWVFEgjyd8pLGKjbxxBNPBGXc\ni0Nu978pNsMwvCPlbWylS5cGXPK3Ipi3bNkCRKLOZ86cCTilpvW97EyNGzcGXGnw/v37B3YOFS1U\nuWml8chTpRLW4Ers1KpVK8QrLBrqxnTppZfm+L4KA6ixjQ+oXFG6o/QjIVVTtmzZZAwnV+bNmwc4\nO3ZeJaZkO4vtAKfy37KtCpWXihem2AzD8I6UV2xSHlJqKmgnpbJ48eKgfZeyBxTXpLI2ssvJNpD1\nyaN8wxdffDHqr5408vwAXH311eFdWDFJxfaAuSH76MknnxzYbQqT06nvVTGG6Y6UkL7DrG0jL7/8\n8qSNK5aCft4VK1YMMgu0ApKnszgt9IpDyjsP1q9fDzhHgMIvdFPsscceufYvUNUPhXLEO10qkc4D\n8cUXXwDZa3opHKROnTqhuNOLYmBXErs6F7Vv3z5YxudXObdy5cpBSpwSrGO7j2lylNlA5oXCkizH\nyF133QW4ibtatWp5hrsUlXjfl0OHDg1MRQrAVQ+OeC85zXlgGEaJIeWXoupWJMUmA2vW/poK53j9\n9dcBF1yr3gc+J7Z/+umnABxyyCFRr6dCnTY5b7IalK+77joANm/enOe+7du3D8JzYp/Kr732GuA6\nXRVVqaUKur50S+NTGMjFF18cXIMKEsRbqeWHKTbDMLwj5RWbUoS6du0KuCBb9TN4+OGHgwDadHvi\nhYGekApSTXX69+9f6H30Xc+fPx+AgQMHAnmnX6UTMriffvrpQfHGdEChUAcffDCPP/444EqGJRtT\nbIZheEfKe0XTiWR4RWXnWLBgAeD6per89erVS5pXtFGjRoBLWr/gggvy3Udj3bp1a7ZCkrFBnmGR\nLK+oymqpP2rjxo3jEsYTr/tSRSVHjRoVhHskWnGaV9QwjBKDKbYQSYZiSxTFUTXyZPfp0ydIpJZK\nkQdb9hoFr8obngiSpdiUCiiV3aVLl5RKgk8HTLEZhlFiMMUWIiXpyejT9fl8bVCy7kthis0wDO+w\nic0wDO+wic0wDO+wic0wDO9IqvPAMAwjHphiMwzDO2xiMwzDO2xiMwzDO5JatsjnYEGfrw38uj6f\nrw1K1n0pTLEZhuEdNrEZhuEdNrEZhuEdKV8a3DBKCvXq1Qv62pYuXRpwhUSNwmETm2EkGfVN7dGj\nB5UrVwZcRWSjaNhS1DAM7/CqHluDBg0A6Ny5MwCXXHIJAO+//z4AH330UbCtunCH2dmqJLnVfbq+\nRF9btWrVAHjmmWcAaNGiRTAO9XVo27YtAJmZmcU+X0m6L4UpNsMwvMMLxXbppZcCcMcddwBQoUKF\nfPdp06YNEG4X8ZL0ZMzp+vS59+jRA3B9P5s2bQrAnnvuyfnnnw+4bu4//vhjrudU3wP1QVi+fHlR\nh58niVJs9erVA9x92rFjx6jzXX/99cE1ptN9WapUKZ588knAXZNWT/HuCG+KzTCMEoMXik2epNWr\nVwOw77775rvP77//Djh1sXjx4mKPo6QrtvHjxwMwePDgUM/977//ArBq1SqAQB3o7zfffFOs4ydK\nscmW9uabb+Z4vp49ewbXFCbxvi/Lly/P559/DsABBxwAOPv2tGnTQj9fVkyxGYZRYvAiju23334D\n4MYbbwRgwoQJQORJAvDdd98BUKNGjWCfvffeG4AOHToA4Si2VEfBnrvvvjsA5557LgD9+/cPtnn+\n+ecB6Nu3b6GPf8YZZ+T5fmZmJv/73//y3EZP/kMPPTT4jho3bgzA4YcfDsCtt94KEByruIot3si2\n9sQTTwDZVZM+N9kS042tW7eyZs0awCm2qlWrJnNIptgMw/APLxSbuP/++wG47LLLADjqqKMA2LRp\nU677TJ48Of4DSyLt2rULFIEUWsWKFYGc7ROyAxWFU045BXAK5Ysvvoh6f+vWraxfv77Ax9tzzz0B\n+Pjjj4FoxQ2RzungVGaq0qtXL8CNf+HChYC7T/PyDKcL9957LwCtW7cGXHf7ZOGF8yCWs846C4Dh\nw4cD0KhRo1y31Rfw2WefFfu8qeA8kLH2iCOOAKBZs2bZttm8eTMAM2bMAFwA85NPPhmEaMSSjABd\nTcQap9i2bRsAJ5xwAlD8MJB4XduyZcsAd/+tW7cOcOaPtWvXhnKe/EjEfXnQQQcB8O233wIu8L1W\nrVoAhXqgFQZzHhiGUWLwaikqnn76acC51eUYkIrJyujRowGn8tKNffbZB4AxY8YAcOGFFwLOofLB\nBx8wduxYgCBd56+//gKcUyWVKFOmDACTJk2id+/eOW5z7LHHArBixYqEjauwnH766RxzzDGAUxVP\nPfUUQK6q2AekCPU9ylwwderUhI7DFJthGN7hpWJT2o6cBwoTyInYYMl044YbbgDgoosuAlwJHNkX\n//zzz+QMrJCcdNJJgDO09+nTJ3jvn3/+AeDKK68EwrGHxguFqMj+l5WNGzcCeacZDRw4EHA2KxF2\n0HO8iLV5SbklGlNshmF4hxeKrX79+gDMnTsXgDp16gCw6675X95zzz0Xv4GFTPny5RkyZAjglM1V\nV10FuKTpRYsWAeljx2nevDng7KCqHJsVqQDZBHfu3Jmg0RUeja1p06bssktENygl7PXXX89xn6uv\nvjr494ABA4DslXOvueYaAA488EDAjxCReGKKzTAM7/BCsSkWTTEzBVFqQk9LPSlTmREjRgSKbfbs\n2YBTOumi0GLp3r07kLNSE7LTKBBXcWvz588HnFKX1zeZnHjiiUDExialJqW5YcOGqG0V3yZ7nDyI\nAFu2bAGcPe7QQw8FnMf/nHPOCWLGjOyYYjMMwzu8UGx6Yl933XUAjBs3DoBy5crlu+/+++8fv4GF\nzNChQwN7k8rbpKtSEyqPLdWtTIkqVarkus/RRx8d9VfFD+66666gdNIvv/wSnwHngtK/tGoAl2nw\n2GOPAS7TQCln1157LRCJeYOIopMCVyEHpb+98sorUf9PVRTHlsSEJsAUm2EYHuKFYhOTJk0CCEqo\nKKZIyPY2efJk9tprr8QOLgTee++9QKUoeV9ZBEuWLEnauIqD8ik7deoEuETxKlWqBE1PlMSvrIrY\nfEd5HwcNGhSUIVczFNm54k3Lli0BuPPOO4PXHnzwQQBuueUWwDVxiS0Nrtzd2bNnB/FqdevWBVxh\nB23z8ssvA6SsfS3ZSk14mQSf3/luuukmRo4cCcCXX34JuB9CcW6YsJKNlYqjrlpKKK5cuXIQpKrA\nXAXgap94Ba+mQpcqBV7L0aNQkZy4/vrrAVfVNy/CuDY5dVQrDrI7sd566y3AfVdC997SpUtzrbKr\nrmpFCdRNRhK8UOD10qVL43JeS4I3DKPE4NVSND8UNiC1Bi5dJ5lBn3JgqPu3lmMKRXn88ceBSGK7\nlqBSbOoMpb4PPqPyRbNmzQLgpZdeAqBVq1bZtlWQdqKQ2UOKKGs1XIV11KxZM2obBd1KzdSrVy9b\nlV1tI8WWbmhFlGhMsRmG4R0lSrGpRFFWHnroISD+/Q/z4sMPPwQIHBqy10ipZUVJ0kKqJRWCUxPF\njh07gEhJJshZscVW700UsvnkZPuRI0PvHXnkkYAL4C1Xrhxff/014IJ2//jjj/gO2FNMsRmG4R1p\n4xVVQcWMjAwge2/JvJANSx7DrKEetWvXBuCrr74q8Fhyo6jep6FDhwKRlClwXaRiWbNmTRAGIO/T\nmWeeCTjVFy/C8orqu+jXrx/gvhOliBUEpV8p4b9NmzbBe1Jzeq0gZanCuLacvJkKAZGNTQU/ZReN\nPd+GDRuCck0vvPBCoceQG8n0iup+jZetzbyihmGUGNLGxqbg29NOOw1waSnr1q0LSrgoZUVBmtpG\nqVZZlZpSVpT2kkxU1lseWvXRbNeuXdR2lSpVChLBFc+UqIYgYbDffvvx4osvAq5Me6VKlQq8vwJc\nBw0aBEQrNbF69Wog8QVE9d1t3boViJSYUtxafouirAG6YSq1VEBByCqAmihMsRmG4R1pY2OTDWPi\nxImAa+gBrhP4qlWrAOdRUmKy0KV+9tlnQbK1ysOEQSq034sXYdihZs6cGZQpEk2aNAFcB3iliIGz\nNUpxS6nFfq8ay+bNmwNFX5hI9zCzKpQaNmjQoKDHZuzxp0+fDrh+qcowSUR0frzuS8WIylPdsGFD\nwHnx46XYcpu+0mZiE1pCagk2ZcqUAu+rzk1yRISNTWx5069fv1y7FenHnTW8QZUstDTPDaWVdevW\nLcilLAypkC4WTxJ5X6pHrcxBCjrPWmsuTMx5YBhGiSFtnAdCKSZly5YFol3nerKrg7iQCmjfvn0i\nhmjkwpIlS5g5cyYQqQCblfxUWVYU0qE0ozlz5gDw7rvvhjFMoxio16sUW2xoS6IwxWYYhneknY0t\nlTEbW/5IaXfr1g1wIRtKgcpqi4ktwaQqsno9rE7wZmMLDyX6K3BejhLVlQsbs7EZhlFiMMUWIqbY\n0hOfrw1K1n0pTLEZhuEdNrEZhuEdNrEZhuEdNrEZhuEdNrEZhuEdSfWKGoZhxANTbIZheIdNbIZh\neEdSk+B9Dhb0+drAr+vz+dqgZN2XwhSbYRjeYRObYRjeYRObYRjeYRObYRjeYRObYRjeYRObYaQI\nhxxyCLNmzWLWrFls376d7du3U79+ferXr5/soaUdNrEZhuEdadfMxTB847jjjgPgxRdf5NdffwXg\n3nvvBeDnn39O2rjSGVNshmF4hym2NKJXr16cfPLJADRq1AiAQw89NGqbd955ByDoiJ61AbGv7LHH\nHgC89tprVK9eHYDjjz8egG+++SZZw8oXdY1/+umngUjDk+HDhwOwdevWpI3LB6znQYiEnbpSpUoV\nAKZNmwZEJqvff/8dgGXLlkXVgfhnAAAKnElEQVRt27p1a8D9yNXJqUGDBsUeByQ37UiTVdWqVaNe\n37hxIwAnnXQSABkZGXz++ecANG/eHIDNmzfne/xEX1udOnUAWLlyJQBvvPEGAB07duTff/8N/XyW\nUmUYhuEBJWopqi7yZcqU4bDDDgPg/PPPj9pGSqdhw4aJHVwOvPjii4Dr1Th+/Hhuv/12AH777beo\nbRUS8N577wFQr149AEaOHMktt9ySiOEWi8MPPxyAK6+8EoCDDz44eE/XUqNGjah9xo4dCzhVWqpU\nKX788Ucg8h2nGuXKlQOcAv/4448B6N69O0Bc1FqiqVy5MgA9evQAYNiwYYBT3WLEiBGMGTMmbuMw\nxWYYhnd4aWM78cQTAacC9H91H8/rvHpqrl27FiicjSosW0b79u0Bp9hmz54NwLnnnpvvvlJnI0aM\nAODbb7+lVq1aRR6LiLcdSkrtzjvvzPbetm3bAHjqqacA1z0+VgWUKlWK3r17A/D4448X+NyJsrFJ\nbV9xxRUA1K1bF4AffvghLucTibCxtWjRAnDfn2yceU0vjz32GAB9+/Yt8nnNxmYYRokhbW1s+++/\nPwBPPvkkhxxySNR7FStWBJyHUE+pDz74AIAmTZrketxddtklat9ksOuuka9FqnHmzJkF3lehA1Js\n5cqVY6+99gJg06ZNYQ4zFG666SYArr322qjXp0+fHgSr3nHHHQDB/xXqsmjRIsB5j3/99dfg+lOJ\nsmXLAtCzZ08gEpYC8VdqiaJKlSo8+OCDAIHtWt/Vs88+C8C8efMAAkV99tlnBypP9tDt27eHNiZT\nbIZheEfaKbZ27doBBE+Igw46KN99ZCfbsGEDEHnCyD6TkZEBwIEHHhi1z6pVq8IZcBF49dVXAWjc\nuDFQuGBN2aNEtWrVOO+884BIAGiqIWW8++67AxGbIMDw4cNZv3591LaK/5KnTXFtW7ZsASLq7++/\n/47/oAvJddddB0CFChUAgiBcX5g3b16g1BYvXgxEYvJyYs2aNUDkd6zfnPZVXF8YmGIzDMM70k6x\n6emXk1KTWhkyZAjg0osUjS4yMzMZOHAgkF2pKQWnV69e4Q26kBRHdXz11VcAfPrpp0AkHk/et1RE\nNrEOHToATl2PHTuWyy+/HHA204kTJwIuFUmxfLfeeisA9913X4JGXTiUBvfWW28B8OGHHyZzOKHz\n119/Bf+WLa0gyOarlVSYpM3EpptDBsesfPfdd4CbjHQD5UXshCb0xcTjw04E//zzDwA7duxI8kgK\nxooVKwD3ENLE1qZNmyDsRSEEsQG6N998MwD33HNPQsZaWFq2bAm4e/aII47Ic/vWrVsHRnc9mNKB\nUqVKBQ46pbkpGLl27doA9OnTB4CmTZsC8NNPPwXhSwqqDhNbihqG4R1po9iUDlW+fPmo15ctWxY8\nufNTapUqVQIiy55WrVplOw7AwoULQxlvslBogZ6YULBE8GQh80FsKEr16tWZM2cO4MJ1FIz50EMP\nAS6UIFVReMfq1asB+Prrr6Pel4qZMGECELk/9XkMHjwYcHXZUpmGDRsG382gQYMA93uVQhPnnHMO\nQNzDckyxGYbhHWmj2B544AHABWOqzth5553HTz/9VKBjXHbZZQCMGjUqeE22DCUiF/RYqYoS5rPW\naVNqViz6LI866igAjj322CBtKdbhEm8U5pEXUtMK2P3+++/jOqbicuGFFwIE4TZSYwpIvfHGGwG4\n9NJLgUjAscIkFIb05ZdfArl/h6lAZmYme+65JwBHH300kF1lK2QpUWFUptgMw/COtFFssrfob2FQ\nNdmRI0cGr8lrqKDVdFVqsqnJy6v6+VnRNcamlKnEjEJnNm/eHATByv4Tb0qXLg3ACSecAOScpP38\n888D7ntMBxo2bBikxsV6qPX5S4VltTfNmjULcB7VoUOHRm2bijRs2DDw/Oo+1HWIZ555BjDFZhiG\nUWS8LFsUy86dO4HoEicK/pTtLgzCKg+j9KJ9990XcE/4Fi1aBCV7hLyfeRXG1PXHJl0/8sgjgFNE\nGzZsyLVHQLxK+8imd8YZZ+S6jcbXpUuXUM4ZSzyurW3btixZsgRwsXkqYip7lGxtmZmZ2fbXPipG\nKWVbFBJZGlylwpQepXPrer744otQz2dliwzDKDGkjY2tKNx2222AK0WUtfTy0qVLkzKmnJBCUwkf\n2ZLy6gCuuC/FqMmOI7uOmDZtWmBjS4VUHhUfUHHBM888E3BPXo1x5cqVwTZSrulKbGR9QeIK07Wk\nkbIrcvrNJRJTbIZheIeXik22C5X90VNDqmDgwIFB+ZRUQBH0yo1UvJNsS4pYnzdvXvCebGF6sst+\no8YnSoYfNGgQf/75Z7wvocC0bdsWIFuDGRXGnDx5MgBdu3YNFFsyS0gVlaz5k0VB5exTOWskJ5QQ\nr9+cimqGWUSyIHg1sSndSqksmijEk08+CcCMGTNSqiOQEvw1gcmQrgTxnNCSc9y4cQAccMABAPzy\nyy+ACzhOpUmtdevWTJo0Keo1OQReeuklAPbbbz8gOjQnlZse58Z///2XZ73/3Nhtt90AF0yuvgCp\njswmF110EeAq6KriSqK/Q1uKGobhHV4oNrnPVVX3rLPOinr/6quvBtwyJ5XUGrglsrq8f/LJJ7lu\nq/AOhUmoNpmWqEoyTgVHQSzt27cPaqvJebNgwQLAKZXOnTsDkRpsWsrp6Z9OrFq1KqgArBVEfvXi\ndtttt2AbpcZdcMEF8RtkSFSsWDHoP6GVg2oiJqsHhSk2wzC8wwvFpqdErFJTAnGsXSfVUNCiui8p\naHifffYBXLDjV199FXRzUpL7u+++C0D//v2BvO1yyebff/8N1Kn+Sql17doVgLvvvhuIFCxUx/RU\nrYybF+vXrw/CjVSWSMyYMQMg6K6mIgTDhg0LqifL7poOBU/Hjx8f/AZlx4695kRjis0wDO9Ie8VW\nv379oKidkAI69dRTkzGkQiOPksopqcigghzVDwDgueeeA1whv1ROjo4la6Ct7GZKO1ISvOjbty/z\n589P3ODiQGyRSKkY2XqFQjomTZrE6NGjgcSHRxQFdYzr2bNnEOaRKn1dTbEZhuEdaZ8EP2PGDHr0\n6BH12oABA4DE22YSmWycaMJIFL/qqquy2V50HHWcksoZO3ZsVPejeBKvBP9UIez7Uh5blcEqV65c\n4PmdO3dusY9fGCwJ3jCMEkPa2thUpmevvfYKXpM38ZVXXknKmIy8mT59epDudsMNNwCwfPlywNkO\n1WrPSD1UrEH2XcUkzpkzJ+FKLT/SdimqVKJrrrkmqJevevGJrtcvbCmanvh8bRDefamQIjk/1Nmt\nXbt2QYB4orGlqGEYJYa0VWyqErFo0aKgppe6uCcLU2zpic/XBsW/L5s3bw64fiMPP/ww4FIYk1k7\nzhSbYRglhrRVbKmIKbb0xOdrg5J1XwpTbIZheEdSFZthGEY8MMVmGIZ32MRmGIZ32MRmGIZ32MRm\nGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ3\n2MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRmGIZ32MRm\nGIZ3/D/Gnh1wexiL8wAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<matplotlib.figure.Figure at 0x7f8ce74e0f90>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "metadata": {
        "id": "Wwii9AQN33_8",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "with np.load('cifar.npz') as data:\n",
        "    cifar_full_train_data_uint8 = data['train_data']\n",
        "    cifar_full_train_labels_int64 = data['train_labels']\n",
        "    cifar_test_data_uint8 = data['test_data']\n",
        "    cifar_test_labels_int64 = data['test_labels']"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "Jut2P5Rj34AD",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "#\n",
        "# TODO: plot an example of each class on MNIST and on CIFAR-10\n",
        "#"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "-cREkeVz34AH",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from scipy.stats import mode\n",
        "\n",
        "\n",
        "def KNN(train_X, train_Y, test_X, test_Y, ks, batch_size=200):\n",
        "    \"\"\"\n",
        "    Compute error rate for various \n",
        "    \"\"\"\n",
        "    errs = np.zeros((len(ks),))\n",
        "    for i in xrange(0, test_Y.shape[0], batch_size):\n",
        "        batch_X = test_X[i:i + batch_size]\n",
        "        batch_Y = test_Y[i:i + batch_size]\n",
        "        print(\"Examples %d:%d Computing distances... \" %\n",
        "              (i, i + batch_size), end='')\n",
        "\n",
        "        #\n",
        "        # TODO: fill in an efficient distance matrix computation\n",
        "        #\n",
        "        dists = TODO\n",
        "\n",
        "        print(\"Sorting... \", end='')\n",
        "        closest = np.argsort(dists, 0)\n",
        "\n",
        "        print(\"Computing errors...\")\n",
        "        targets = train_Y[closest]\n",
        "\n",
        "        for ki, k in enumerate(ks):\n",
        "            predictions, unused_counts = mode(targets[:k, :], axis=0)\n",
        "            predictions = predictions.ravel()\n",
        "            #\n",
        "            # TODO: fill in error count computation\n",
        "            #\n",
        "            errs[ki] += TODO\n",
        "\n",
        "    errs /= test_Y.shape\n",
        "    return np.vstack((ks, errs))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "FTuX5ql334AO",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Now find the best k on the validation set\n",
        "\n",
        "mnist_validation_errs = KNN(\n",
        "    mnist_train_data_uint8, mnist_train_labels_int64,\n",
        "    mnist_valid_data_uint8, mnist_valid_labels_int64,\n",
        "    [1, 3, 5, 7, 9])\n",
        "\n",
        "plot(mnist_validation_errs[0, :], mnist_validation_errs[1, :])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "l5j4eGVN34AR",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Now use the best k to compute the test error\n",
        "\n",
        "best_K = TODO\n",
        "\n",
        "mnist_full_train_data_uint8 = mnist_train_dataset.train_data.numpy()\n",
        "mnist_full_train_labels_int64 = mnist_train_dataset.train_labels.numpy()\n",
        "\n",
        "mnist_test_errs = KNN(mnist_full_train_data_uint8, \n",
        "                      mnist_full_train_labels_int64,\n",
        "                      mnist_test_data_uint8, \n",
        "                      mnist_test_labels_int64, [best_K])\n",
        "print(\"When k=%d the test error rate is %.1f%%\" %\n",
        "      (mnist_test_errs[0, 0], mnist_test_errs[1, 0] * 100.0))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "g88neUhM34AU",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "#\n",
        "# Now repeat the k-NN training for CIFAR10\n",
        "#"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "1qq8XLOt34AX",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Locality sensitive hashing\n",
        "\n",
        "Problem 5 was about speeding up the inference using loops implicitly present in matrix multiplication instead of explicit loops in Python. In this problem, we will explore a strategy to truly reduce the total number of computations required to find nearest neighbors without sacrificing too much accuracy.\n",
        "\n",
        "To speed up nearest neighbor search we will employ *Locality Sensitive Hashing (LSH)* functions. For a given distance metric, the locality sensitive hash should put items that are similar into the same bucket. Notice that this is essentially a design choice opposite to traditional cryptographic hash functions that should amplify the difference of similar inputs (typically we want that small perturbations of data result in large changes to the hash value).\n",
        "\n",
        "One of the simplest implementations of LSH approximates the cosine distance. Let $x\\in \\mathbb{R}^N$ and $y\\in \\mathbb{R}^N$ be two vectors. Their cosine distance is defined as:\n",
        "\n",
        "\\begin{equation}\n",
        "    d_\\text{cos}(x,y) = \\frac{x \\cdot y}{\\|x\\| \\|y\\|} = \\cos\\left(\\theta(x,y)\\right),\n",
        "\\end{equation}\n",
        "where $\\theta(x,y)$ is the unsigned angle between $x$ and $y$.\n",
        "\n",
        "We will construct a family $H$ of hash functions that are an LSH for angle distances (an approximation to cosine distance). Assume $p\\in \\mathbb{R}^N$ is a random vector (components are sampled from the normal distribution) of length 1. Then define the hash function $h(x) = \\text{sgn}(x\\cdot p)$, where $\\text{sgn()}$ is the sign function. It can be proven that:\n",
        "\n",
        "\\begin{equation}\n",
        "    p_{h\\in H}[h(x)=h(y)] = 1 - \\frac{\\theta(x,y)}{\\pi}.\n",
        "\\end{equation}\n",
        "\n",
        "The equation means that the probability of a hash collision grows as the the angle between two vectors gets smaller. Therefore, vectors that are close according to the cosine distance will be put with high probability into the same bin (we use the fact that for small $\\theta$ we can approximate $\\cos(\\theta) = 1 - \\theta/\\pi$.\n",
        "\n",
        "We will say that a family of randomly chosen hash functions $H$ is $(d_1, d_2, p_1, p_2)$-sensitive with respect to a distance metric $d$ if for any $x$ and $y$:\n",
        "1. If $d(x,y) \\leq d_1$ then $p_{h\\in H}[h(x)=h(y)] \\geq p_1$.\n",
        "2. If $d(x,y) \\geq d_2$ then $p_{h\\in H}[h(x)=h(y)] \\leq p_2$.\n",
        "\n",
        "For example, our family of randomly chosen hyperplanes is $(d_1, d_2, (1-d_1)/\\pi, (1-d_2)/\\pi)$-sensitive.\n",
        "\n",
        "Ideally, vectors should be placed into the same bin with a high probability if their distance is smaller than a threshold, and with a low probability if their distance is larger that the threshold. By combining hashing functions we can get closer to this ideal sensitivity.\n",
        "\n",
        "Given a family of hash functions $H$ with sensitivity $(d_1, d_3, p_1, p_2)$ we can construct a new family $H'$ by combining $r$ functions from $H$:\n",
        "1. AND: let $h=[h_1, h_2, \\ldots, h_r] \\in H'$ and $h(x)=h(y)$ if and only if $\\forall_i h_i(x)=h_i(y)$. Then $H'$ is $(d_1, d_2, (p_1)^r, (p_2)^r)$-sensitive.\n",
        "2. OR: let $h=[h_1, h_2, \\ldots, h_r] \\in H'$ and $h(x)=h(y)$ if and only if $\\exists_i h_i(x)=h_i(y)$. Then $H'$ is $(d_1, d_2, 1-(1-p_1)^r, 1-(1-p_2)^r)$-sensitive.\n",
        "\n",
        "AND makes all probabilities shrink, but properly choosing $r$ we can make the lower probability approach 0 while the higher does not. Conversely, OR makes all probabilities grow, we can make the upper probability approach 1 while the lower does not."
      ]
    },
    {
      "metadata": {
        "id": "OutHmcfp8zLo",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "#### Problem 6 [2-4p bonus] \n",
        "\n",
        "1. **[1bp]** **Note:** you can show sketches of proofs for this assignment.\n",
        "    1. Show that angle between vectors is a metric (https://en.wikipedia.org/wiki/Metric_(mathematics)).\n",
        "    \n",
        "    2. Show that $p_{h\\in H}[h(x)=h(y)] = 1 - \\frac{\\theta(x,y)}{\\pi}$ for $h$ computed using a randomly chosen hyperplane.\n",
        "\n",
        "    3. Show the properties of either AND or OR boosting of LSH.\n",
        "\n",
        "3. **[1-3bp]** Reimplement k-Nearest Neighbors for MNIST classification using the cosine distance instead of the Euclidean distance. Choose a sensible value of $k$. Use Locality Sensitive Hashing to achieve an error rate no greater than $150\\%$ of the original error rate with at least a $90\\%$ speedup (i.e., by considering on average at most 5000 training samples per query image). For a few settings plot the speedup-vs-accuracy relation.\n",
        "\n",
        "  **Note:** points will be awarded based on ingenuity of your solution. Feel free to explore your own ideas!\n"
      ]
    }
  ]
}