cs110_pcw_6_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Evan\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "499babfdbdc05aec285e42abdf82edd4",
     "grade": false,
     "grade_id": "cell-f534ec91df9dff5f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 6.2\n",
    "\n",
    "## Part A. Median-of-3 partitioning quicksort \n",
    "\n",
    "## Question 1.\n",
    "\n",
    "Read through the following Python code. What does each function (i.e., median, qsort, randomized_qsort, test_qsort) do? Comment in details each function. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.06063951100000009\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "import random\n",
    "\n",
    "eps = 1e-16\n",
    "N = 10000\n",
    "locations = [0.0, 0.5, 1.0 - eps]\n",
    "\n",
    "\n",
    "def median(x1, x2, x3):\n",
    "    if (x1 < x2 < x3) or (x3 < x2 < x1):\n",
    "        return x2\n",
    "    elif (x1 < x3 < x2) or (x2 < x3 < x1):\n",
    "        return x3\n",
    "    else:\n",
    "        return x1\n",
    "\n",
    "def qsort(lst):\n",
    "    indices = [(0, len(lst))]\n",
    "\n",
    "    while indices:\n",
    "        (frm, to) = indices.pop()\n",
    "        if frm == to:\n",
    "            continue\n",
    "\n",
    "        # Find the partition:\n",
    "        N = to - frm\n",
    "        inds = [frm + int(N * n) for n in locations]\n",
    "        values = [lst[ind] for ind in inds]\n",
    "        partition = median(*values)\n",
    "\n",
    "        # Split into lists:\n",
    "        lower = [a for a in lst[frm:to] if a < partition]\n",
    "        upper = [a for a in lst[frm:to] if a > partition]\n",
    "        counts = sum([1 for a in lst[frm:to] if a == partition])\n",
    "\n",
    "        ind1 = frm + len(lower)\n",
    "        ind2 = ind1 + counts\n",
    "\n",
    "        # Push back into correct place:\n",
    "        lst[frm:ind1] = lower\n",
    "        lst[ind1:ind2] = [partition] * counts\n",
    "        lst[ind2:to] = upper\n",
    "\n",
    "        # Enqueue other locations\n",
    "        indices.append((frm, ind1))\n",
    "        indices.append((ind2, to))\n",
    "    return lst\n",
    "\n",
    "\n",
    "def randomized_quicksort():\n",
    "    lst = [i for i in range(N)]\n",
    "    random.shuffle(lst)\n",
    "    return qsort(lst)\n",
    "\n",
    "\n",
    "def test_quicksort():\n",
    "    lst = randomized_quicksort()\n",
    "    assert (lst == [i for i in range(N)])\n",
    "\n",
    "\n",
    "# Is our algorithm correct\n",
    "test_quicksort()\n",
    "\n",
    "# How fast is our algorithm\n",
    "print(timeit.timeit(randomized_quicksort, number=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "61fb11bff1434e4b7276c7443b0267c6",
     "grade": false,
     "grade_id": "cell-a2b2429aa4e81403",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "\n",
    "What are the main differences between the `randomized_quicksort` in the code and $RANDOMIZED-QUICKSORT$ in Cormen et al., besides that the partition of `randomized_quicksort` uses a median of 3 as a pivot?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "8915b75d94bc194ba0f4e52e475063b4",
     "grade": true,
     "grade_id": "cell-4a3cd727ccac7404",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The main difference is that the version in this code randomizes the order of the elements in the array whereas the version in Cormen randomizes the partition element. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "5853f10cab01212736d0e92ce408fa97",
     "grade": false,
     "grade_id": "cell-49bff57d4018e133",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "What is the time complexity of this `randomized_qsort`? Time the algorithm on lists of various lengths, each list being a list of the first $n$ consecutive positive integers. Produce a graph with list lengths on the x axis and running time on the y axis. As always, don’t forget to time the algorithm several times for each list’s length and then average the results. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "a321a7fcecb9c9cce252ea2c6030d4ce",
     "grade": true,
     "grade_id": "cell-e0e1dac71ac7feb6",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "import matplotlib.pyplot as plt\n",
    "def randomized_qsort():\n",
    "    \n",
    "    random.shuffle(lst)\n",
    "    return qsort(lst)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD4CAYAAADiry33AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXhU5fn/8fdtgLDvi2xhkV02cQCx7hZ3xV20rVRpsYtd3KqCKKK1StVq1VapWiv9VUEUjYiigrWuSFAgC1sICAFZA2ENZLl/f8zx25gmMphllnxe15WLmXOemdxPTvhwODNzP+buiIhI4joi2gWIiEj1UtCLiCQ4Bb2ISIJT0IuIJDgFvYhIgqsT7QLKat26tXft2jXaZYiIxJVFixZtc/c25e2LuaDv2rUraWlp0S5DRCSumNmXFe3TpRsRkQSnoBcRSXAKehGRBKegFxFJcAp6EZEEp6AXEUlwCnoRkQSnoBcRiTJ358XP1vFu1uZqeX4FvYhIFG3ZXcDYf6Rx2yvpvLp4Q7V8j5j7ZKyISG0xJ/0rJsxKZ9/BYu46vx9jRnStlu+joBcRqWH5+wq5KzWDVxdvZGCnZjx8+SB6tG1Sbd9PQS8iUoM+WLWVW15aytY9B/jt93vyy1N7UDepeq+iK+hFRGrAvoNF3P/mcp7/5EuOatOIqVcfz8BOzWvkeyvoRUSq2efrdnDTjCWs2baXa7/Xjd+d1Zv6dZNq7Psr6EVEqsnBohIem7+KJ97Lpn2zBvzrp8M5/qjWNV6Hgl5EpBqs3LybG6YvJnPjLi49thN3nt+PpvXrRqUWBb2ISBUqLnGe/XANf3x7BU2S6/DUj47lzKOPjGpNEQW9mZ0FPAokAU+7+/1l9icDzwPHAtuBK9x9bbBvIPAU0BQoAYa6e0FVTUBEJFasz9vHTS8t4bM1eYzs144/XDyA1o2To13WoYPezJKAJ4CRQC6w0MxS3T2r1LCxwA5372Fmo4EHgCvMrA7wT+BH7r7EzFoBhVU+CxGRKHJ3ZqStZ/LrWZgZD142iEuGdMTMol0aENkZ/TAg291zAMzsRWAUUDroRwGTgtszgcctPMMzgKXuvgTA3bdXUd0iIjFhy+4Cbn85nXnLtzCieyv+eNlAOrVoGO2yviGSoO8IrC91PxcYXtEYdy8ys3ygFdALcDObC7QBXnT3KWW/gZmNA8YBpKSkHO4cRESi4s30rxg/K529B4uZeF4/rjm+K0ccERtn8aVFEvTlVe0RjqkDnAAMBfYB88xskbvP+8ZA96nAVIBQKFT2uUVEYkr+/kLuTs3klS82MKBjuIVBz3bV18KgsiIJ+lygc6n7nYCNFYzJDa7LNwPygu3vu/s2ADObAwwB5iEiEoc+XLWNW2YuYcvuA/zm9J5cf1r1tzCorEiqWwj0NLNuZlYPGA2klhmTCowJbl8KzHd3B+YCA82sYfAPwMl889q+iEhc2H+wmEmpmfzwmQU0qJfEKz8/nhtG9or5kIcIzuiDa+7XEw7tJOBZd880s8lAmrunAs8A08wsm/CZ/OjgsTvM7GHC/1g4MMfd36imuYiIVIvF63dy4/TF5GzbyzXf68qtZ/Wp0RYGlWXhE+/YEQqFPC0tLdpliIhQWFzCY/NW8cS/V9OuSTIPXjaI43vUfAuDSASvf4bK26dPxoqIlGPV5t3cMGMxGRt2cfGQjky64OiotTCoLAW9iEgpJSXOsx+tYcrcFTROrsOTPzyWs/pHt4VBZSnoRUQC6/P2cfNLS1iwJo/v9w23MGjTJPotDCpLQS8itZ6781JaLpNnh98UOOXSgVx2bKeYaWFQWQp6EanVtu4+wO2vpPPuss0M79aSBy8bROeWsdXCoLIU9CJSa72VsYnxs9LZc6CIO87ty7Xf6xaTLQwqS0EvIrXOroJCJqVm8srnG+jfsSl/unxwTLcwqCwFvYjUKh9lb+OWl5awefcBfn16T34VBy0MKktBLyK1wv6DxTzw1nKe+3gt3Vs34uWfH8/gzs2jXVaNUNCLSMJbsn4nN8xYTM7Wvfz4+HALgwb14qeFQWUp6EUkYRUWl/DY/GyeeC+btk2S+efY4ZzQMzZbGFQnBb2IJKTsLbu5YfoS0jfkc/ExHbnrgqNp1iA+WxhUloJeRBJK6RYGjeol8dcfDOHsAe2jXVZUKehFJGHk7gi3MPg0J4/v923LfRcPoG2T+tEuK+oU9CIS99ydmYtyufv1LNydKZcM5LJQ4rQwqCwFvYjEtW17wi0M3snazLBuLXkoAVsYVJaCXkTi1tzMTYx/JZ3dBUVMOKcvY09IzBYGlaWgF5G4s6ugkLtTs3j581yO7tCUF8YNplcCtzCoLAW9iMSVj7O3cfPXLQxO68H1p/WkXp3EbmFQWQp6EYkLBYXhFgZ//2gt3Vo3YubPRnBMSotolxUXFPQiEvOW5u7khumLWb11L2NGdOG2s/vWqhYGlaWgF5GYVVhcwhPvZfPY/GzaNE5m2thhnNizTbTLijsRXdgys7PMbIWZZZvZbeXsTzaz6cH+BWbWNdje1cz2m9ni4OvJqi1fRBJV9pbdXPLXj3nk3VVcMKgDc397kkL+OzrkGb2ZJQFPACOBXGChmaW6e1apYWOBHe7ew8xGAw8AVwT7Vrv74CquW0QSVEmJ89zHa3ngreU0rJfEX34whHNqeQuDyork0s0wINvdcwDM7EVgFFA66EcBk4LbM4HHTR9JE5HDtGHnfm6esYRPcrZzep+2/OEStTCoCpEEfUdgfan7ucDwisa4e5GZ5QOtgn3dzOwLYBdwh7t/UPYbmNk4YBxASkrKYU1AROKfu/Py5xu4OzWTEnceuGQAl4c6q4VBFYkk6Mv7SXuEY74CUtx9u5kdC7xqZke7+65vDHSfCkwFCIVCZZ9bRBLYtj0HGP9KOm9nbWZY15Y8eNkgUlqphUFViiToc4HOpe53AjZWMCbXzOoAzYA8d3fgAIC7LzKz1UAvIK2yhYtI/Hs7cxO3By0Mxp/Th7EndCdJLQyqXCRBvxDoaWbdgA3AaOCqMmNSgTHAJ8ClwHx3dzNrQzjwi82sO9ATyKmy6kUkLu0qKGTy61nMXJRLv/ZN+ddPB9P7SLUwqC6HDPrgmvv1wFwgCXjW3TPNbDKQ5u6pwDPANDPLBvII/2MAcBIw2cyKgGLgZ+6eVx0TEZH48PHqbdzy0lK+yt/P9af24Nenq4VBdbPw1ZXYEQqFPC1NV3ZEEk1BYTF/nLuCZz5cQ7fWjXjo8kEMUQuDKmNmi9w9VN4+fTJWRKpdem4+N8xYTPaWPVw9ogu3nd2HhvUUPzVFP2kRqTaFxSX85b3VPDZ/Fa0bJ/P8tcM4qZc+3VrTFPQiUi2yt+zhphmLWZKbz4WDO3D3Bf1p1rButMuqlRT0IlKlSkqcf3yylvvfXE6Dekk8cdUQzh2oFgbRpKAXkSqzYed+bnlpCR+v3s6pvdvwwCUDadtULQyiTUEvIpXm7sz6YgN3vZZJsTt/uHgAo4eqhUGsUNCLSKVs33OA8bPSmZu5maFdW/DQZYPVwiDGKOhF5Dt7J2szt7+ylF37i7j97D785ES1MIhFCnoROWy7Cwq5Z3YWM9Jy6du+Kf/8ySD6HNk02mVJBRT0InJYPs3Zzk0zlvBV/n5+eepR/Ob0XmphEOMU9CISkYLCYh6cu4JnPlpDl5YNeelnx3NsF7UwiAcKehE5pPTcfG6csZhVW/bwo+O6cPs5amEQT3SkRKRCRcUl/OXfq/nzvFW0alyPf1w7jJPVwiDuKOhFpFyrt+7hxhlLWLJ+J6MGd2CyWhjELQW9iHxDSYnz/Cdruf+t5dSvm8TjVx3DeQM7RLssqQQFvYj8n4079/O7mUv5MHsbpwQtDNqphUHcU9CLyH9bGKRmUlzi3HfRAK4cphYGiUJBL1LLbd9zgAmzMngrcxOhLi146PJBdGnVKNplSRVS0IvUYu9mbea2V9LZtb+Q287uw0/VwiAhKehFaqHdBYXcO3sZ09PW0+fIJkwbO4y+7dXCIFEp6EVqmQU527nppSVs3LmfX5xyFL/5fk+S6yRFuyypRgp6kVqioLCYh95ewdMfriGlZUNmXDeCUNeW0S5LakBEnYjM7CwzW2Fm2WZ2Wzn7k81serB/gZl1LbM/xcz2mNnNVVO2iByOjA35nP/Yh/ztgzVcNSyFOb8+USFfixzyjN7MkoAngJFALrDQzFLdPavUsLHADnfvYWajgQeAK0rt/xPwZtWVLSKRKCou4a//Xs2j81bRslE9nrtmKKf0bhvtsqSGRXLpZhiQ7e45AGb2IjAKKB30o4BJwe2ZwONmZu7uZnYhkAPsrbKqReSQcoIWBovX7+T8QR24Z9TRNG9YL9plSRREEvQdgfWl7ucCwysa4+5FZpYPtDKz/cCthP83UOFlGzMbB4wDSElJibh4EflfJSXOPxd8yX1zlpFcJ4k/X3kMFwxSC4PaLJKgL+9NtR7hmLuBP7n7nm/7hJ27TwWmAoRCobLPLSIR+io/3MLgg1XbOLlXG6ZcqhYGElnQ5wKdS93vBGysYEyumdUBmgF5hM/8LzWzKUBzoMTMCtz98UpXLiL/x915bfFGJr6WQVGx8/uL+nPVsBS1MBAgsqBfCPQ0s27ABmA0cFWZManAGOAT4FJgvrs7cOLXA8xsErBHIS9StfL2HuSOV9OZk76JY7u04KHLBtG1tVoYyH8dMuiDa+7XA3OBJOBZd880s8lAmrunAs8A08wsm/CZ/OjqLFpEwuYt28ytL6eTv/8gt57Vh3EnqYWB/C8Ln3jHjlAo5GlpadEuQySm7TlQxL2zs3hxYbiFwcOXD6ZfB7UwqM3MbJG7h8rbp0/GisSZz9bkcdNLi8ndsZ+fnXwUN4xUCwP5dgp6kThRUFjMw++s5G8f5NC5RbiFwVB9ulUioKAXiQMZG/K5ccZiVm7ew1XDU5hwTl8aJeuvr0RGvykiMayouISn/pPDI++upEXDevz9mqGcqhYGcpgU9CIxas22vdw4YzFfrNvJuQPbc++o/rRopBYGcvgU9CIxxt3556dfct+c5dRNMrUwkEpT0IvEkNItDE7q1YYplwzkyGZqYSCVo6AXiQHuTuqSjUx8NYPCYufeC/vzg+FqYSBVQ0EvEmU79h7kjlczeCP9K4akNOfhywerhYFUKQW9SBTNXx5uYbBz30FuObM3153UnTpJES38JhIxBb1IFOw9UMS9byzjhc/W0btdE567ZihHd2gW7bIkQSnoRWrYwrV53DRjCet37OO6k7tz48heamEg1UpBL1JDDhQV8/DbK5n6QQ6dWjRQCwOpMQp6kRqQuTGfG6cvYcXm3Vw5LIUJ5/alsVoYSA3Rb5pINSrdwqB5w3r8/cdDObWPWhhIzVLQi1STtUELg8/X7eTcAe2590K1MJDoUNCLVDF3558L1nHfG8uom2Q8OnowFwzqoA8/SdQo6EWq0Kb8An738lL+s3IrJ/ZszZRLB9K+WYNolyW1nIJepIq8tngDE1/N4GBxCfeMOpofHtdFZ/ESExT0IpW0Y+9BJr6WweylX3FM0MKgm1oYSAxR0ItUwnsrtnDrzKXk7VULA4ldCnqR72DvgSJ+P2cZ/1qwjl7tGvPsj4fSv6NaGEhsiujUw8zOMrMVZpZtZreVsz/ZzKYH+xeYWddg+zAzWxx8LTGzi6q2fJGal7Y2j7Mf/YAXPlvHdSd1J/X6ExTyEtMOeUZvZknAE8BIIBdYaGap7p5VathYYIe79zCz0cADwBVABhBy9yIzaw8sMbPX3b2oymciUs0OFBXzp3dW8dR/VtOpRQOmjxvBsG5qYSCxL5JLN8OAbHfPATCzF4FRQOmgHwVMCm7PBB43M3P3faXG1Ae80hWLRMHn63Yw/pV0lm/azZXDOjPh3H5qYSBxI5Lf1I7A+lL3c4HhFY0Jzt7zgVbANjMbDjwLdAF+VN7ZvJmNA8YBpKSkHO4cRKpN/v5Cpry1nH99to52TerzzJgQp/dtF+2yRA5LJEFf3huBy56ZVzjG3RcAR5tZX+AfZvamuxd8Y6D7VGAqQCgU0lm/RN3XS/vdM3sZeXsP8OPju3LTGb11Fi9xKZLf2lygc6n7nYCNFYzJNbM6QDMgr/QAd19mZnuB/kDad65YpJqt3baXia9l8MGqbQzs1IznrtE7aiS+RRL0C4GeZtYN2ACMBq4qMyYVGAN8AlwKzHd3Dx6zPric0wXoDaytquJFqtKBomKmvp/DY+9lUy/pCO6+IPzp1qQj9OlWiW+HDPogpK8H5gJJwLPunmlmk4E0d08FngGmmVk24TP50cHDTwBuM7NCoAT4hbtvq46JiFTGpznbmTArndVb93LugPbceX4/2jWtH+2yRKqEucfWJfFQKORpabqyIzUjb+9B7puzjJmLcunUogH3jOqvfvESl8xskbuHytunV5akVnJ3XlqUyx/mLGN3QRE/P+Uofn1aTxrU09qtkngU9FLrZG/ZzfhZGXy2Jo9Qlxb8/qIB9D6ySbTLEqk2CnqpNQoKi3l8fjZP/Wc1DevV4f6LB3B5qDNH6MVWSXAKeqkV/rNyKxNfy+DL7fu4+JiOjD+3L60bJ0e7LJEaoaCXhLZldwH3zF7G60s20r11I/71k+Ec36N1tMsSqVEKeklIJSXO//tsHVPeWs6BwhJ++/2e/PyUo0iuoxdbpfZR0EvCydq4i/Gz0lm8fifHH9WKey/sT/c2jaNdlkjUKOglYew9UMQj767k2Y/W0rxBXf50xSAuHNxR67ZKraegl4TwduYmJqVmsjG/gCuHdebWs/rQvGG9aJclEhMU9BLXNu7cz12pmbyTtZne7Zow88pjCHXVYiAipSnoJS4VFZfw3MdrefidlZS4c+tZffjJid2oq4W5Rf6Hgl7izuL1Oxn/SjpZX+3i1N5tmDyqP51bNox2WSIxS0EvcWNXQSEPzl3BtE+/pG2TZP7ygyGc3f9IvdgqcggKeol57s7spV8xeXYW2/ccYMyIrtx0Ri+a1K8b7dJE4oKCXmLauu37mPhaBu+v3Er/jk15ZkyIgZ2aR7sskbiioJeYdLCohL99kMOf562izhHGnef14+oRXaijF1tFDpuCXmLOZ2vymDArnVVb9nB2/yO56/yjObKZVnsS+a4U9BIzduw9yB/eXMaMtFw6Nm/Asz8OcVqfdtEuSyTuKegl6tydlz/fwH1zlpG/v5DrTu7Ob07vScN6+vUUqQr6myRRlb1lD3e8ms6nOXkMSWnOfRcPoM+RTaNdlkhCUdBLVBQUFvOX97J58v0c6tc9gvsuGsDooVrtSaQ6KOilxn24aht3vJrO2u37uHBwByac2482TbTak0h1iei9amZ2lpmtMLNsM7utnP3JZjY92L/AzLoG20ea2SIzSw/+PK1qy5d4snX3AX7z4hf88JkFAPxz7HAeGX2MQl6kmh3yjN7MkoAngJFALrDQzFLdPavUsLHADnfvYWajgQeAK4BtwPnuvtHM+gNzgY5VPQmJbSUlzgsL1/HAm8spKCzh16f35BenHEX9ulrtSaQmRHLpZhiQ7e45AGb2IjAKKB30o4BJwe2ZwONmZu7+RakxmUB9M0t29wOVrlziwvJNuxj/Sjqfr9vJcd1bcu+FA+jRVqs9idSkSIK+I7C+1P1cYHhFY9y9yMzygVaEz+i/dgnwRXkhb2bjgHEAKSkpERcvsWvfwSIefXcVT3+4hmYN6vLQZYO4eIhWexKJhkiCvry/mX44Y8zsaMKXc84o7xu4+1RgKkAoFCr73BJn5i3bzJ2vZbJh536uCHXmtrP70KKRVnsSiZZIgj4X6FzqfidgYwVjcs2sDtAMyAMws07ALOBqd19d6YolZn2Vv5+7U7N4K3MTPds2ZsZ1IxjWTas9iURbJEG/EOhpZt2ADcBo4KoyY1KBMcAnwKXAfHd3M2sOvAHc7u4fVV3ZEkuKS5x/fLyWh95eQVGJc8uZvfnpid2pV0cNyERiwSGDPrjmfj3hd8wkAc+6e6aZTQbS3D0VeAaYZmbZhM/kRwcPvx7oAUw0s4nBtjPcfUtVT0SiY2nuTsbPSidjwy5O7tWGe0b1J6WVVnsSiSXmHluXxEOhkKelpUW7DDmE3QWFPPT2Sp7/ZC2tGidz1/n9OHdAe73YKhIlZrbI3UPl7dMnY+WwuDtvZmzi7tcz2bL7AD86rgs3n9mbplrtSSRmKeglYuvz9nHnaxm8t2Ir/do35akfhRjcWas9icQ6Bb0cUmFxCU9/sIZH563kCDMmntePMVrtSSRuKOjlW6WtzWP8rHRWbt7DGf3aMemCo+nQvEG0yxKRw6Cgl3Lt3HeQB95azgufradDs/r87eoQI/tptSeReKSgl29wd15dvIF7Zy9j5/5Cxp0UXu2pUbJ+VUTilf72yv/J2bqHia9l8FH2dgZ3bs60iwbQr4NWexKJdwp6oaCwmCffX81f3ltNct0juPfC/lw1LEWrPYkkCAV9Lfdx9jbueDWDnG17uWBQB+44ry9tm9SPdlkiUoUU9LXUtj0H+P0by5j1xQa6tGrI89cO46RebaJdlohUAwV9LVNS4sxIW88f3lzOvoNF/Oq0Hvzy1B5a7UkkgSnoa5EVm3YzYVY6aV/uYFi3ltx3UX96tG0S7bJEpJop6GuB/QeLeXTeKp7+IIcm9evwx0sHcumxndSATKSWUNAnuPeWb2Hiaxnk7tjPZcd24vZz+tJSqz2J1CoK+gS1eVcBd7+eyZz0TfRo25jp445jePdW0S5LRKJAQZ9gikucaZ+s5cG3V1JYXMLNZ/Ri3ElHabUnkVpMQZ9AMjbkM35WOktz8zmxZ2vuvbA/XVo1inZZIhJlCvoEsOdAEQ+9vYJ/fLyWlo2S+fOVx3D+QK32JCJhCvo45u7MzdzEpNQsNu8u4AfDU7jlzD40a6DVnkTkvxT0cSp3xz7uei2Tecu30Ld9U/76wyEck9Ii2mWJSAxS0MeZwuISnv1wDY+8uwqACef05ZrvddVqTyJSIQV9HFn05Q4mzEpn+abdfL9vO+4edTQdtdqTiBxCRKeBZnaWma0ws2wzu62c/clmNj3Yv8DMugbbW5nZe2a2x8wer9rSa4/8fYWMn5XOpU9+TP7+Qp760bE8PSakkBeRiBzyjN7MkoAngJFALrDQzFLdPavUsLHADnfvYWajgQeAK4ACYCLQP/iSw+DupC7ZyD2zs8jbe5Brv9eNG0b2orFWexKRwxBJYgwDst09B8DMXgRGAaWDfhQwKbg9E3jczMzd9wIfmlmPqiu5dli7bS8TX8vgg1XbGNSpGc9dM4z+HZtFuywRiUORBH1HYH2p+7nA8IrGuHuRmeUDrYBtkRRhZuOAcQApKSmRPCRhHSgq5qn3c3j8vWySk47gnlFHc9XwLiRptScR+Y4iCfryEsa/w5gKuftUYCpAKBSK+HGJ5pPV25nwajo5W/dy3sD23HleP9o21WpPIlI5kQR9LtC51P1OwMYKxuSaWR2gGZBXJRXWAnl7D/L7N5bx8ue5dG7ZgOeuGcopvdtGuywRSRCRBP1CoKeZdQM2AKOBq8qMSQXGAJ8AlwLz3b3WnplHqqTEmbkol/veXMaegiJ+ccpR/Oq0njSop9WeRKTqHDLog2vu1wNzgSTgWXfPNLPJQJq7pwLPANPMLJvwmfzorx9vZmuBpkA9M7sQOKPMO3ZqpVWbdzNhVgafrc1jWNeW3HtRf3q102pPIlL1InqfnrvPAeaU2XZnqdsFwGUVPLZrJepLOAWFxTw2fxVT/5NDo+Q6TLkkvNrTEXqxVUSqid6QXYPeX7mVia9msC5vH5cM6cT4c/rQqnFytMsSkQSnoK8BW3YVMHl2FrOXfkX3No144afHMeIorfYkIjVDQV+Nikucfy34kilvreBAcQk3juzFdSd3J7mOXmwVkZqjoK8mmRvzGT8rgyXrd3JCj9bcc2F/urXWak8iUvMU9FVs74Ei/vTOSv7+8VpaNKzLo6MHc8GgDlrtSUSiRkFfhd7O3MSk1Ew25hdw1fAUbj2zD80aarUnEYkuBX0V2LBzP5NSM3knazN9jmzCY1cN4dguWu1JRGKDgr4SdhcU8uT7q3n6gzUcYcbtZ/fh2hO6UVerPYlIDFHQfweFxSW8+Nk6Hnl3Fdv3HuTCwR24+czedGrRMNqliYj8DwX9YXB33snazP1vLSdn616Gd2vJ38/ty8BOzaNdmohIhRT0EVqyfie/n7OMz9bkcVSbRjx9dYjT+7bVu2lEJOYp6A9hfd4+/jh3BalLNtK6cT3uvbA/o4d2po6uw4tInFDQVyB/XyFP/Dub5z5ayxFHwK9O68F1Jx+l9VpFJO4otco4WFTCtE+/5LH5q8jfX8glQzpx0xm9aN+sQbRLExH5ThT0AXdnTvompsxdzpfb93FCj9aMP6cv/To0jXZpIiKVoqAHFq/fyeTXM/l83U56t2vCc9cM5eRebfRCq4gkhFod9Ft2FTBl7gpmLsqldeNk7r94AJeFOpOkRUBEJIHUyqA/UFTM3z9ay2PzVnGwuITrTu7O9af2oEl99aURkcRTq4Le3Zm3bAv3vpHF2u37OL1PW+44r5/aB4tIQqs1QZ+9ZTd3v57FB6u2cVSbRjx3zVBO6d022mWJiFS7hA/6/P2FPPLuSp7/5Esa1kti4nn9uHpEFzUeE5FaI2GDvrjEmb5wPQ++vYId+w4yemgKN5/RS4txi0itE1HQm9lZwKNAEvC0u99fZn8y8DxwLLAduMLd1wb7bgfGAsXAr919bpVVX4FFX+5g4qsZZH21i2FdW3Ln+f3o37FZdX9bEZGYdMigN7Mk4AlgJJALLDSzVHfPKjVsLLDD3XuY2WjgAeAKM+sHjAaOBjoA75pZL3cvruqJQHgZv/vfXM60T7/kyKb1eezKYzhvYHu9H15EarVIzuiHAdnungNgZi8Co4DSQT8KmBTcngk8buF0HQW86O4HgDVmlh083ydVU/5/Lc3dyXXTFrFpVwHXfq8bN57RS31pRESILOg7AutL3c8Fhlc0xt2LzCwfaBVs/7TMYzuW/QZmNg4YB5CSkhJp7d+Q0rIhPdo25s9XHsPQri2/03OIiDWgGG8AAAV/SURBVCSiSIK+vOseHuGYSB6Lu08FpgKEQqH/2R+J5g3rMW1s2X9/REQkkvcY5gKdS93vBGysaIyZ1QGaAXkRPlZERKpRJEG/EOhpZt3MrB7hF1dTy4xJBcYEty8F5ru7B9tHm1mymXUDegKfVU3pIiISiUNeugmuuV8PzCX89spn3T3TzCYDae6eCjwDTAtebM0j/I8BwbgZhF+4LQJ+WV3vuBERkfJZ+MQ7doRCIU9LS4t2GSIiccXMFrl7qLx96gMgIpLgFPQiIglOQS8ikuAU9CIiCS7mXow1s63Al5V4itbAtioqJx7UtvmC5lxbaM6Hp4u7tylvR8wFfWWZWVpFrzwnoto2X9CcawvNuero0o2ISIJT0IuIJLhEDPqp0S6ghtW2+YLmXFtozlUk4a7Ri4jINyXiGb2IiJSioBcRSXAJE/RmdpaZrTCzbDO7Ldr1VIaZdTaz98xsmZllmtlvgu0tzewdM1sV/Nki2G5m9udg7kvNbEip5xoTjF9lZmMq+p6xwMySzOwLM5sd3O9mZguC2qcHbbIJ2l5PD+a7wMy6lnqO24PtK8zszOjMJDJm1tzMZprZ8uBYj6gFx/iG4Hc6w8xeMLP6iXaczexZM9tiZhmltlXZcTWzY80sPXjMn80iWBTb3eP+i3D75NVAd6AesAToF+26KjGf9sCQ4HYTYCXQD5gC3BZsvw14ILh9DvAm4RW9jgMWBNtbAjnBny2C2y2iPb9vmfeNwL+A2cH9GcDo4PaTwM+D278AngxujwamB7f7Bcc+GegW/E4kRXte3zLffwA/CW7XA5on8jEmvIzoGqBBqeP740Q7zsBJwBAgo9S2KjuuhNf0GBE85k3g7EPWFO0fShX9YEcAc0vdvx24Pdp1VeH8XgNGAiuA9sG29sCK4PZTwJWlxq8I9l8JPFVq+zfGxdIX4dXH5gGnAbODX+JtQJ2yx5jw2ggjgtt1gnFW9riXHhdrX0DTIPSszPZEPsZfry3dMjhus4EzE/E4A13LBH2VHNdg3/JS278xrqKvRLl0U94C5v+zCHk8Cv67egywAGjn7l8BBH+2DYZVNP94+rk8AvwOKAnutwJ2untRcL907d9YjB4ovRh9vMy3O7AV+HtwueppM2tEAh9jd98APAisA74ifNwWkdjH+WtVdVw7BrfLbv9WiRL0ES1CHm/MrDHwMvBbd9/1bUPL2Rbx4uzRZmbnAVvcfVHpzeUM9UPsi4v5BuoQ/u/9X939GGAv4f/SVyTu5xxclx5F+HJLB6ARcHY5QxPpOB/K4c7xO809UYI+4RYhN7O6hEP+/7n7K8HmzWbWPtjfHtgSbK9o/vHyc/kecIGZrQVeJHz55hGguYUXm4dv1p4Ii9HnArnuviC4P5Nw8CfqMQb4PrDG3be6eyHwCnA8iX2cv1ZVxzU3uF12+7dKlKCPZAHzuBG8iv4MsMzdHy61q/Qi7GMIX7v/evvVwSv4xwH5wX8P5wJnmFmL4GzqjGBbTHH32929k7t3JXzs5rv7D4D3CC82D/8737hejN7dNwHrzax3sOl0wmsrJ+QxDqwDjjOzhsHv+NdzTtjjXEqVHNdg324zOy74GV5d6rkqFu0XLarwxY9zCL87ZTUwIdr1VHIuJxD+79hSYHHwdQ7h65PzgFXBny2D8QY8Ecw9HQiVeq5rgezg65pozy2CuZ/Cf991053wX+Bs4CUgOdheP7ifHezvXurxE4KfwwoieDdClOc6GEgLjvOrhN9dkdDHGLgbWA5kANMIv3MmoY4z8ALh1yAKCZ+Bj63K4wqEgp/fauBxyrygX96XWiCIiCS4RLl0IyIiFVDQi4gkOAW9iEiCU9CLiCQ4Bb2ISIJT0IuIJDgFvYhIgvv/ZN+/EVXLAZEAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "t_list = []\n",
    "n_list = [1,5,10,50,100,500,1000,5000,10000]\n",
    "for n in n_list:\n",
    "    lst = [i for i in range(n)]\n",
    "    total_time = 0\n",
    "    for i in range(10):\n",
    "        total_time += timeit.timeit(randomized_qsort,number=1)\n",
    "    ave_time = total_time/10\n",
    "    t_list.append(ave_time)\n",
    "    \n",
    "plt.plot(n_list,t_list)\n",
    "plt.show()\n",
    "\n",
    "#raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00010558699999974053\n"
     ]
    }
   ],
   "source": [
    "lst = [i for i in range(10)]\n",
    "print(timeit.timeit(randomized_qsort,number=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b8751f930d9dc208113425646ea7fea8",
     "grade": false,
     "grade_id": "cell-1e8309c07c2f2908",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4.\n",
    "\n",
    "### Question 4a.\n",
    "\n",
    "Change the `qsort()` function in a way that you **don’t** separate the items that are equal to the partition. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "797888f53fa36bcf0f9d891c4819d8e9",
     "grade": false,
     "grade_id": "cell-a9d1f063c0340b14",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "eps = 1e-16\n",
    "N = 10000\n",
    "locations = [0.0, 0.5, 1.0 - eps]\n",
    "\n",
    "def qsort(lst):\n",
    "    indices = [(0, len(lst))]\n",
    "\n",
    "    while indices:\n",
    "        (frm, to) = indices.pop()\n",
    "        if frm == to:\n",
    "            continue\n",
    "        isinlst = False\n",
    "        # Find the partition:\n",
    "        N = to - frm\n",
    "        inds = [frm + int(N * n) for n in locations]  \n",
    "        #print(inds,\"inds\")\n",
    "        values = [lst[ind] for ind in inds]\n",
    "        #print(values,\"values\")\n",
    "        partition = median(*values)\n",
    "        #print(partition,\"partition\")\n",
    "        # Split into lists:\n",
    "        lower = [a for a in lst[frm:to] if a < partition] #change to <=\n",
    "        upper = []\n",
    "        for a in lst[frm:to]:\n",
    "            if a > partition:\n",
    "                upper.append(a)\n",
    "            elif a == partition:\n",
    "                if isinlst == True:\n",
    "                    upper.append(a)\n",
    "                else:\n",
    "                    isinlst = True\n",
    "        \n",
    "        #counts = sum([1 for a in lst[frm:to] if a == partition])\n",
    "        #print(lower,upper,\"lower,upper\")\n",
    "        ind1 = frm + len(lower)\n",
    "        ind2 = ind1 + 1\n",
    "        #print(ind1,ind2,\"ind1,ind2\")\n",
    "        # Push back into correct place:\n",
    "        lst[frm:ind1] = lower\n",
    "        lst[ind1:ind2] = [partition] # * counts\n",
    "        lst[ind2:to] = upper\n",
    "        #print(lst,\"lst\")\n",
    "        # Enqueue other locations\n",
    "        #print(\"ewf\",frm,ind1,ind2,to)\n",
    "        indices.append((frm, ind1))\n",
    "        indices.append((ind2, to))\n",
    "    #print(lst)\n",
    "    return lst    \n",
    "\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ce755b787f1b82629d627d2f8bea66a5",
     "grade": true,
     "grade_id": "cell-2c0cbd296d612f85",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(qsort([4,2,1])==[1,2,4])\n",
    "assert(qsort([0])==[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst = [i for i in range(5)]\n",
    "qsort(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 5]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [2,3,5]\n",
    "a.remove(a[1])\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3f5f9ca976fb636978e2bdfda98a5eeb",
     "grade": false,
     "grade_id": "cell-76883a453f020d72",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 4b.\n",
    "\n",
    "Now time the algorithm on the same inputs you have used in question 3, adding one more line in the previous graph you have produced. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "33188fb282e53d117dfe275067ad3567",
     "grade": true,
     "grade_id": "cell-31ee807cec9ce8bf",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function matplotlib.pyplot.show(*args, **kw)>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAD4CAYAAADiry33AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deVxV1frH8c8jKs6zOSM45zygptXNZutm3tKKbLCyLMsys8Ex50wzGxzyWmlmeZ1SQ3OoNCutVCyRwVAEUxxRFEQBGdbvj3X6XeSiHuUcDhye9+vFi3P23ufstdn4dbPO2s8SYwxKKaW8VzFPN0AppZR7adArpZSX06BXSikvp0GvlFJeToNeKaW8XHFPNyCnatWqGX9/f083QymlCpUdO3acMMZUz21dgQt6f39/QkJCPN0MpZQqVETkr4ut064bpZTychr0Sinl5TTolVLKy2nQK6WUl9OgV0opL6dBr5RSXk6DXimlvJwGvVJKeZgxhkXbDvB95DG3vL8GvVJKedDxM6n0mx/C0OVhrNx5yC37KHB3xiqlVFGxJuwII1aEce58JqN7NKdvF3+37EeDXiml8lniuXRGB4ezcudhWtetyLQH29DomvJu258GvVJK5aOf98bz2tJdxCen8fJtjXnh5kaU8HFvL7oGvVJK5YNz5zN4e+2ffP7rXzSsXpY5j3eldd1K+bJvDXqllHKz3w+cYsiSUGJPnOWp6wN4vXtTSpXwybf9a9ArpZSbnM/IYvrGvcz8IZpaFUuz8JnOdG1YLd/boUGvlFJusOfYGQYv3knE4SR6d6jLmz2aU6FUCY+0RYNeKaVcKDPLMHdzLO98G0V53+L8+7EO3Nmipkfb5FTQi0h34APAB/jEGPN2jvW+wOdAB+Ak8JAxZr9jXWvg30AFIAvoaIxJddUBKKVUQXEw4RxDloayLTaB25vXYNL9rahWztfTzbp80IuIDzATuB2IA7aLSLAxJjLbZv2AU8aYRiISBEwGHhKR4sAXwGPGmFARqQqku/wolFLKg4wxLAk5yLhVkYgIUx9oQ6/2dRARTzcNcO6KvhMQbYyJARCRRUBPIHvQ9wTGOB4vA2aIPcI7gF3GmFAAY8xJF7VbKaUKhONnUhn2VRgb/jxOlwZVeeeB1tStXMbTzbqAM0FfBziY7Xkc0Pli2xhjMkQkEagKNAGMiKwHqgOLjDFTcu5ARPoD/QH8/Pyu9BiUUsoj1oYdYbijhMGoe5rzZFd/ihUrGFfx2TkT9Lm12ji5TXHgBqAjcA7YICI7jDEbLtjQmDnAHIDAwMCc762UUgVKYko6Y4IjWPHHIVrVqch7D7m3hEFeORP0cUC9bM/rAocvsk2co1++IpDgWP6jMeYEgIisAdoDG1BKqUJo894TvLYslONn0hh0a2MG3uL+EgZ55UzrtgONRSRAREoCQUBwjm2Cgb6Ox72BjcYYA6wHWotIGcd/ADdxYd++UkoVCinnMxkTHMGjn26ldEkflg/oyuDbmxT4kAcnrugdfe4DsaHtA8w1xkSIyDggxBgTDHwKLBCRaOyVfJDjtadEZBr2PwsDrDHGfOOmY1FKKbfYefA0ryzeScyJszx5vT9vdG+WryUM8krshXfBERgYaEJCQjzdDKWU4nxGFjM27mXmpn3UKO/L1Afa0LVR/pcwcIbj88/A3NbpnbFKKZWLPcfO8MqSnYQfSqJX+7qMvtdzJQzySoNeKaWyycoyzN0Sy5T1UZTzLc7sRzvQvaVnSxjklQa9Uko5HEw4x6tLQ9kam8Bt19oSBtXL51MJg8xMSEuDMq6/2UqDXilV5BljWBoSx7jVdlDgO71b07tD3fwrYfD77/Dss9CpE8yc6fK3L/jjgpRSyo3iz6TxzOchvP7VLlrWqcC6l2/kgcB6+RPySUkwaBB07AgHD8KNN7plN3pFr5QqstaFH2H4inCS0zLyt4SBMbB0Kbz8Mhw9Cs8/DxMmQCX3TC2oQa+UKnISU9IZGxzB8j8O0bJOBd57sC2Na+RTCYN9++CFF2D9emjfHr7+2l7Ru5EGvVKqSNkSfYLXloZy7EwaL93amBfzq4RBWhq88w5MnAglSsCHH9oreR/333ilQa+UKhJSzmcyed2ffPbLfhpUL8tXA7rStp57ukr+xw8/wIABEBUFDz4I770HtWvnz77RoFdKFQE7D57mlSU7iYk/yxNdbQmD0iXzoYTBsWPw6qvwxRfQoAGsXQvdu7t/vzlo0CulvFZ6ZhbTN0Yz84dorinvy5dPd+b6/ChhkJUFH38MQ4fC2bMwahQMGwalS7t/37nQoFdKeaW9x84w2FHC4P72dRjdowUVS+dDCYPQUHjuOfjtN7j5Zpg1C5o1c/9+L0GDXinlVf63hEF7ures5f4dnzkDo0fbD1mrVIEFC+CRR6AAzBurQa+U8hoXljC4hkn3t3Z/CQNjYMUKeOklOHwY+veHSZOgcmX37vcKaNArpQo9YwxLd8QxbpUtYTCld2seyI8SBrGx8OKL8M030KYNLFsG113n3n1eBQ16pVShFn8mjWHLw/h+9zE6B1Rh6gNtqFfF9YXBLnD+PEybBuPGQbFi9vGLL0LxghmpBbNVSinlhHXhRxmxIowzaRmM/Oe1PHV9gPtLGPz0kx0THxkJ998P778P9epd/nUepEGvlCp0klLTGRMcwfLfbQmD/zzYlibuLmEQHw+vvw6ffQb+/rB6Nfzzn+7dp4to0CulCpULShjc0ogXb23s3hIGWVkwb54N+aQkOx5+5Ei31I13Fw16pVShkJpuSxjM27KfBtXKsuy5LrTzc/PIlrAw202zZYstIfzRR9CihXv36QYa9EqpAi/UUcJgX36VMDh7FsaOtTVpKla0V/R9+xaIMfFXQ4NeKVVgpWdmMWNjNDMcJQy+6NeZGxq7uYRBcLAdQXPgADz9NLz9NlSt6t59uplTHVsi0l1EokQkWkSG5rLeV0QWO9ZvFRF/x3J/EUkRkZ2Or9mubb5SyltFHz/D/bN+4YMNe+nZpjbrXv6He0P+wAH417+gZ0+oUAE2b7b1agp5yIMTV/Qi4gPMBG4H4oDtIhJsjInMtlk/4JQxppGIBAGTgYcc6/YZY9q6uN1KKS+VlWWY98t+Jq/7k7Ilffjokfbc1cqNJQzS0+0QyTFj7PMpU+zMTyXyoS5OPnGm66YTEG2MiQEQkUVATyB70PcExjgeLwNmSL7NqquU8hZxp2wJg99iEri12TVM6tWKa8qXct8Ot2yxBcjCw+Hee22dmvr13bc/D3Em6OsAB7M9jwM6X2wbY0yGiCQCf/+9EyAifwBJwEhjzM85dyAi/YH+AH5+fld0AEqpws8Yw7IdcYxdFYkxhsm9WvGgOyfoPnnSlhD+5BN7s9PKlbbLxks5E/S5/aSNk9scAfyMMSdFpAOwUkRaGGOSLtjQmDnAHIDAwMCc762U8mInkm0Jg+8ij9EpoArvurOEgTEwfz689hqcOmW/v/kmlCvnnv0VEM4EfRyQ/f7eusDhi2wTJyLFgYpAgjHGAGkAxpgdIrIPaAKE5LXhSqnCb33EUYYvD+NMagYj7r6Wfje4sYRBZKQdE//TT9C1K8yeDa1auWdfBYwzQb8daCwiAcAhIAjok2ObYKAv8CvQG9hojDEiUh0b+Jki0gBoDMS4rPVKqUIpKTWdscGRfPV7HC1qV2DhM21pWtNNJQzOnYMJE+zE3BUq2O6aJ5+0xciKiMsGvaPPfSCwHvAB5hpjIkRkHBBijAkGPgUWiEg0kID9zwDgH8A4EckAMoHnjDEJ7jgQpVTh8Mu+E7y2dBdHElN48ZZGvHhLY0oWd1PofvMNDBwI+/fDE0/YETXVq7tnXwWY2N6VgiMwMNCEhGjPjlLeJjU9kynropi7JZaAamV598E2tHdXCYO4OBg0CJYvh2uvtaULbrrJPfsqIERkhzEmMLd1emesUsrtdsWdZvBiW8Kgb5f6DL3rWveUMMjIgOnT7QesmZl2pqdXXoGSJV2/r0JEg14p5TbpmVnM/CGa6RujqV7OlwX9OnFjYzd1nfz2mx0THxoKd98NM2ZAQIB79lXIaNArpdwi+ngyryzZya64RO5rV4cxPVpQsYwb7jY9dcqWDp4zB2rXhq++gvvuK7QFyNxBg14p5VJZWYbPHCUMypT0YdYj7bnbHSUMjIEvv4QhQ+wNUIMH2zIG5d08AUkhpEGvlHKZQ6dTeHVJKL/GnHRvCYOoKDsm/ocfoHNnWL8e2mpJrYvRoFdK5Zkxhq9+P8TY4Aiy3FnCICUF3nrLDpMsU8be9PTMM0VqTPzV0KBXSuXJieQ0hi8P49vIY3Tyr8LUB9rgV9UNJQzWr4fnn4eYGHjsMXsDVI0art+PF9KgV0pdtW8jjjJ8RRhJKRkMv7sZ/W5ogI+rSxgcPmz735csgaZNYcMGuOUW1+7Dy2nQK6WuWFJqOuNWRbJsRxzNa1Xgy6fdUMIgMxNmzYIRI+D8eRg/3hYh8/V17X6KAA16pdQVyV7CYODNjXjpVjeUMAgJsWPid+yAO++0Y+IbNXLtPooQDXqllFNS0zN5Z30Un262JQyWDejq+hIGiYn2Cn7WLKhZ03bX9O6tY+LzSINeKXVZYXGJDF6yk+jjyTzepT5D72pGmZIujA9jYPFi2xd//LidnHv8eFttUuWZBr1S6qLSM7OY9cM+pm/cS7Vyvnz+VCf+0cTFJQz27oUXXoDvvoPAQFi9Gjp0cO0+ijgNeqVUrqKPJzNkyU5C4xL5V9vajL23pWtLGKSmwuTJtvCYr6/th3/uOfBxQ7GzIk6DXil1gawsw/xf9/P22j8pXdKHmX3a88/WLi5h8P33dkz83r3w8MPw7rtQyw1lEhSgQa+UyubQ6RReWxrKL/tOcnPT6kzu1ZprKriwhMHRo7Y2zcKFdhTNt9/C7be77v1VrjTolVIYY1jxxyFGfx1BpjFMur8VQR1dWMIgM9NWlxw2zJYxGD0ahg6FUm6og6P+hwa9UkXcyeQ0hq8IY33EMTr6V+bdB9q6toTB77/bvvft2+G222DmTGjSxHXvry5Lg16pIuy7yGMMW76LpJQMht3VjKdvdGEJg6QkO9PT9Ol2ntaFCyEoSMfEe4AGvVJF0JnUdMavjmRJSBzX1qrAF0+3oVlNF41ZN8ZO/jFoEBw5YssJT5wIlSq55v3VFdOgV6qI+S3mJEOWhHIkMYUXbm7IoFubuK6EQUyMHRO/bh20awcrVkCnTq55b3XVNOiVKiJS0zOZuj6KT7fEUr9KGZY+15UO9V1UwiAtDaZOhQkToEQJeP99G/jFNWIKAqf+GxeR7iISJSLRIjI0l/W+IrLYsX6riPjnWO8nIski8qprmq2UuhJhcYn0mL6ZTzbH8mjn+qwZdKPrQn7TJju708iR0KMH7N5tu2005AuMy54JEfEBZgK3A3HAdhEJNsZEZtusH3DKGNNIRIKAycBD2da/B6x1XbOVUs7IyMxi1qZ9fLhhL1XLlWT+U524yVUlDI4fh1dfhQULICAA1qyBu+5yzXsrl3Lmv9xOQLQxJgZARBYBPYHsQd8TGON4vAyYISJijDEi8i8gBjjrslYrpS5rX3wyrywJJfTgaXq2rc04V5UwyMqCTz6x4+CTk221yREjoHTpvL+3cgtngr4OcDDb8zig88W2McZkiEgiUFVEUoA3sH8NXLTbRkT6A/0B/Pz8nG68Uup/ZWUZPv91P2+v+5NSJXyY0acd97Su7Zo3Dw21o2h+/RW6dbPlhK+91jXvrdzGmaDPbdCrcXKbscB7xpjkS91hZ4yZA8wBCAwMzPneSiknHT6dwmvLQtkSfZJujhIGNVxRwiA52d7N+sEHUKUKfP45PPqojokvJJwJ+jigXrbndYHDF9kmTkSKAxWBBOyVf28RmQJUArJEJNUYMyPPLVdK/b//L2EQHEFmlgtLGBgDK1fCSy9BXBz072+rTVap4pqGq3zhTNBvBxqLSABwCAgC+uTYJhjoC/wK9AY2GmMMcOPfG4jIGCBZQ14p1zqZnMaIFeGsizhKYP3KvPtgG+pXLZv3N96/304Asno1tG5tZ3vq0iXv76vy3WWD3tHnPhBYD/gAc40xESIyDggxxgQDnwILRCQaeyUf5M5GK6Ws7yOPMXR5GEkp6Qy9qxnPuKKEwfnz8N57MHYsFCtmSwi/9JIOlyzExF54FxyBgYEmJCTE081QqkA7k5rOhNW7WRxykGY1y/PeQ225tpYLShj8/LMtQBYZCfffb298qlfv8q9THiciO4wxgbmt0/+ilSpkfos5yatLQzl8OoXnuzVk0G2N8S2ex1mZTpyA11+HefOgfn1YtQruucc1DVYep0GvVCGRmp7Ju99G8cnmWPyqlGHpc13oUD+PH4pmZcFnn8Frr9lqk0OH2jtcy7qgj18VGBr0ShUC4YcSGbx4J3uPJ/PodX4Mu+tayvrm8Z9veLgdE795M9x4I3z0EbRo4ZoGqwJFg16pAiwjM4uPNu3jgw17qVK2JJ892ZFuTa/J25uePQvjxsG0aVCxou2u6dtXx8R7MQ16pQqoffHJDFkSys6Dp7m3TW3G9WxBpTIl8/amq1bBwIFw4AD06weTJ0PVqq5psCqwNOiVKmCysgwLfvuLSWt341vch+kPt6NHmzyWMDhwwFaUXLnSds/8/DPccINrGqwKPA16pQqQw6dTeH3ZLjZHn3BNCYP0dFu2YMwYe5frlCnw8su2ZrwqMjTolSoAjDF8vfMwo74OJyPTMPG+lvTp5Je3Ega//GLHxIeF2Trx06fboZOqyNGgV8rDEs6eZ8SKMNaGH6VD/cq8+0Ab/KvlYXhjQoIdJvnxx/Zmp5UroWdP1zVYFToa9Ep50Ibdx3jjqzASU87zRvdm9P9HHkoYGGMnARkyBE6dspOCjB4N5cq5ttGq0NGgV8oDktMymLA6kkXbbQmDBf065a2Ewe7ddkz8jz9C1652THzr1q5rsCrUNOiVymdbY04yxFHCYEC3hryclxIG587BxInwzjv2yv3jj+Gpp2wxMqUcNOiVyiep6ZlM+24PH/8cQ73KZVjybBcC/fNQwmDNGjsmPjbW3vD0zjtQ3UXzwSqvokGvVD4IP5TIK0t2sudYMo909mP43XkoYXDokB0iuWyZncZv0ya46SaXtld5Fw16pdwoIzOL2T/u4/3vbQmDeU925OarLWGQkQEzZsCoUfbxW2/ZD15L5vFuWeX1NOiVcpOY+GRecZQwuKd1LSb8q+XVlzDYutWOid+5E+66ywZ+gwaubbDyWhr0SrmYMbaEwVtrbAmDDx9ux71XW8Lg9GkYPhxmz4ZatWx3zf33awEydUU06JVyoSOJtoTBz3tP8I8m1ZnSqzU1K15FCQNjYOFCeOUVOynIoEG24mT58q5vtPJ6GvRKuUDOEgYT/tWSRzpfZQmDqCh4/nnYuBE6dYJ166BdO9c3WhUZGvRK5VHC2fOMXBnGmrCjtPerxLQH215dCYPUVJg0Cd5+G0qXtjc9PfMM+ORxmkBV5GnQK5UHG/+0JQxOnzvP692b8uw/Gl5dCYNvv7VX8fv2wSOPwLvvQo0arm+wKpI06JW6CslpGUz8JpL/bLMlDOY/2Ynmta+ihMGRIzB4MCxeDE2awPffw623ur7Bqkhz6j5pEekuIlEiEi0iQ3NZ7ysiix3rt4qIv2N5JxHZ6fgKFZH7XNt8pfLfttgE7vrgJxZtP8izNzXg64HXX3nIZ2baIZLNmtnqkuPGwa5dGvLKLS57RS8iPsBM4HYgDtguIsHGmMhsm/UDThljGolIEDAZeAgIBwKNMRkiUgsIFZFVxpgMlx+JUm6Wmp7Je9/tYU62EgYdr6aEQUiIHRO/YwfccQfMnAmNGrm+wUo5ONN10wmINsbEAIjIIqAnkD3oewJjHI+XATNERIwx57JtUwoweW6xUh6w468Ehi0PY8+xZPp09mPE1ZQwSEyEkSNtsNesCYsWwYMP6ph45XbO/KbWAQ5mex4HdL7YNo6r90SgKnBCRDoDc4H6wGO5Xc2LSH+gP4Cfn9+VHoNSbpN4Lp231/3Jf7YdoFbFUsx7oiM3N7vCEgbGwJIltj7N8eO2ENn48VCxonsarVQOzgR9bpcbOa/ML7qNMWYr0EJErgXmi8haY0zqBRsaMweYAxAYGKhX/crj/h4XP+GbSE6dS+fpGwIYfHuTK7+Kj46GF16wo2o6dIBVqyAw0D2NVuoinPmtjQPqZXteFzh8kW3iRKQ4UBFIyL6BMWa3iJwFWgIhV91ipdws9sRZRq0MZ3P0CdrUq8T8p1rSovYVXn2npcHkybbwmK+v/eD1ued0TLzyCGeCfjvQWEQCgENAENAnxzbBQF/gV6A3sNEYYxyvOejozqkPNAX2u6rxSrlSWkYmszfFMHNTNL4+xRjfswV9Ote/8nHxGzbYMfF79kBQEEybZuvUKOUhlw16R0gPBNYDPsBcY0yEiIwDQowxwcCnwAIRicZeyQc5Xn4DMFRE0oEs4HljzAl3HIhSefHLvhOMXBlOTPxZ7mldizfvac41Fa6wRs2xY7Zs8JdfQsOGsH69HVWjlIeJMQWrSzwwMNCEhGjPjsofJ5PTmLhmN8t/P4RflTKM69mCbldaLz4zE+bMgWHDICXFfh86FEpdRTEzpa6SiOwwxuT6AZDeGauKpKwsw9IdB5m09k/OpmXwws0NefGWxpQqcYV96H/8Yfvet22zNzvNmmXvcFWqANGgV0XOnmNnGLEijO37T9HJvwoT72tJ4xpXWP73zBl480348EOoVs121zz8sI6JVwWSBr0qMlLOZ/Lhxr18/FMM5UoVZ0qv1vTuUJdiV/JhqzGwfLmtD3/4MAwYABMnQqVK7mu4UnmkQa+KhE1Rxxn1dTgHE1Lo1b4uw+9uRtVyvlf2JjEx9mantWuhbVsb+J06uafBSrmQBr3yaseSUhm3OpJvdh2hQfWy/OeZ6+jSsOqVvUlCgq0TP306lCgB779vb4Iqrv98VOGgv6nKK2VmGb747S+mro8iLTOLIbc3of9NDfAtfgUftp47Z/vg334bkpKgb19buqBuXfc1XCk30KBXXif8UCIjVoQRGpfIjY2rMb5nyyub8SkjA+bOhbFjbT98jx72DteWLd3XaKXcSINeeY3ktAymfbuHz36JpUrZknwQ1JZ729R2ft7Wvz9oHTHCztvataudEOSGG9zbcKXcTINeFXrGGNZHHGPsqgiOJKbSp7Mfb9zZjIplSjj/Jps2wRtv2PHwzZvD11/bK3kdLqm8gAa9KtTiTp1jTHAE3+8+TrOa5ZnRpz0d6ld2/g1CQ+1drOvWQb16MG8ePPaYFh9TXkWDXhVK6ZlZzNsSy3vf7QVg+N3NePL6AEr4ODU7JsTGwqhRsHChHQM/daodSaNlC5QX0qBXhc7vB04xfHkYfx49w23XXsOYe1tQt3IZ5158/DhMmACzZ9vhkUOHwuuv6w1Pyqtp0KtCIzElnSnr/mThtgPUKF+K2Y924M4WNZz7sPXMGVsueOpUW3isXz8YPRpq13Z/w5XyMA16VeAZYwgOPcz41btJOJvGk10DeOWOJpRzZran8+dtZclx4yA+Hnr1siULmjZ1f8OVKiA06FWBtv/EWUZ9Hc7Pe0/Qum5FPnuyIy3rODHbU1aWHRo5cqQtXdCtm53xSUsWqCJIg14VSGkZmcz5MYbpP0RT0qcYY+9twaPXOTHbkzF2ftZhw2wJ4TZtbG2aO+/UoZKqyNKgVwXObzEnGbEijH3xZ/lnq1q82aM5NZyZ7Wn7dvvh6saNEBAAX3xhSwcXc3IkjlJeSoNeFRgJZ8/z1prdLNsRR93KpZn3ZEdudma2pz17bBfN0qVQvbqtT/Pss1CypPsbrVQhoEGvPM4Yw9IdcUxas5szqRkM6NaQl25pTOmSl7lp6cgRW4/mk0/s+PfRo+2creWvcBIRpbycBr3yqL3HzjBiZTjbYhMIrF+Zife1omnNywR1YiJMmWLLBaen28k/Ro6EGjXyp9FKFTIa9MojUtMzmb5xL3N+iqFMyeJM7tWKBzrUu/RsT6mpdk7WiRNtjfg+fWzZ4AYN8q/hShVCGvQq3/24J55RK8M5kHCO+9vVYfg/r6XapWZ7ysyEBQts18yBA3YEzaRJ0K5d/jVaqULMqeEIItJdRKJEJFpEhuay3ldEFjvWbxURf8fy20Vkh4iEOb7f4trmq8LkeFIqAxf+Tt+52yheTFj4TGemPdT24iFvDKxaZYdIPvmk7ZrZsMEWINOQV8ppl72iFxEfYCZwOxAHbBeRYGNMZLbN+gGnjDGNRCQImAw8BJwAehhjDotIS2A9UMfVB6EKtswsw8KtfzFlnZ3tafBtTXiu22Vme9qyxZYN3rIFmjSxI2p69dKx8EpdBWe6bjoB0caYGAARWQT0BLIHfU9gjOPxMmCGiIgx5o9s20QApUTE1xiTlueWq0Ih4nAiw1eEE3rwNNc3qsqEf7Ui4FKzPUVEwPDhEBwMtWrZ4mNPPWXnalVKXRVngr4OcDDb8zig88W2McZkiEgiUBV7Rf+3XsAfuYW8iPQH+gP4+fk53XhVcJ1Ny+C97/Yw75f9VC5TgvcfakvPtpeY7engQdsHP38+lCtnP3AdNAjKXsEUgEqpXDkT9Ln9yzRXso2ItMB259yR2w6MMXOAOQCBgYE531sVMt9GHGVMcASHE1N5uJMfQ7tfYranhAT7wer06bZPfvBgW76gatX8bbRSXsyZoI8D6mV7Xhc4fJFt4kSkOFARSAAQkbrACuBxY8y+PLdYFViHT6cwOjiC7yKP0bRGeb7q044O9avkvvG5c/YO1rffhqQk6NvX3vykf9Ep5XLOBP12oLGIBACHgCCgT45tgoG+wK9Ab2CjMcaISCXgG2CYMWaL65qtCpKMzCw++2U/077bQ5YxDL2rGf1uuMhsTxkZMHeuDfXDh+28rG+9BS1b5n/DlSoiLhv0jj73gdgRMz7AXGNMhIiMA0KMMcHAp8ACEYnGXskHOV4+EGgEjBKRUY5ldxhjjrv6QJRn7Dx4muHLw4g8ksQtza5h7L0tqFcll9mejIHly2HECIiKgq5dbRnhG27I/7VPj5AAABDNSURBVEYrVcSIMQWrSzwwMNCEhIR4uhnqMpJS03lnXRRfbP2La8r7MqZHC7q3rJn7h62bNtmhktu2QfPmtk++Rw8dKqmUC4nIDmNMYG7r9M5YdUWMMazedYRxqyM5mZxG3y7+DLmjCeVL5fJha2ioLRu8bh3Uq2e7bB5/HHwuU6xMKeVSGvTKaQdOnmPk1+H8tCeeVnUqMrdvR1rVzWW2p9hYGDUKFi60k25PnQovvGArTCql8p0Gvbqs8xlZfPxzDB9u2EsJn2KM7tGcx7v4/+9sT8ePw4QJ9ian4sXt1fzrr9uwV0p5jAa9uqRtsQmMWBHG3uPJ3N2qJm/e04KaFXNcmZ85A9Om2Sv3lBTo18/e/FS7tmcarZS6gAa9ytUpx2xPS3fEUadSaeY+EcgtzXLUez9/HubMgXHjID7e1qKZOBGaNvVMo5VSudKgVxcwxvDV74d4a81uklLSee6mhrx0ayPKlMz2q5KVZYdGjhwJMTHQrRtMngydOnms3Uqpi9OgV/8v+ngyI1aEsTU2gQ71KzPxvpY0q1nhvxsYA99+a0sU/PGHLR+8dq2tD69DJZUqsDToFanpmcz8IZrZP+6jdAkfJt3fiocCc8z2tH27/XB140YICIAvvoCHH4ZiTk1poJTyIA36Iu7nvfGMXBnOXyfPcV+7OozIOdvTnj22i2bpUqhe3danefZZKFnSc41WSl0RDfoi6viZVCas3k1w6GECqpXly6c7c32jav/d4MgRW4/mk0/s+PfRo2HIECh/mYm7lVIFjgZ9EZOVZVi47QCT1/1JWnoWg25tzIBuDSlVwnG3amIiTJkC778P6ekwYIC9oq9R49JvrJQqsDToi5DdR5IYviKMPw6cpkuDqky4ryUNq5ezK1NTYdYsOzwyIcH2v48fDw0berbRSqk806AvAs6dz+D97/fy6eZYKpUuwbQH23Bfuzq2AFlmJixYYLtmDhywI2gmTdLJt5XyIhr0Xu77yGOMDo7g0OkUgjrWY+hdzahUpqQdKrlqlR0qGREBHTvCvHlwyy2ebrJSysU06L3UkcQUxgRHsD7iGE1qlGPpc13o6O+Y7WnLFls2eMsWaNLEjqjp1UvHwivlpTTovUxGZhbzf/2Lad9GkWkMb3S3sz2VLF7MXrkPHw7BwVCrli0+9tRTUOIi87kqpbyCBr0XCT14muErwog4nMTNTaszrmdLO9vTwYO2D37+fChXzn7gOmgQlC3r6SYrpfKBBr0XSEpN5931UXz+219UL+fLrEfac1fLmsipU/DaaJg+3fbJDx5s++SrVvV0k5VS+UiDvhAzxrAm7ChjV0UQn5zG49fVZ8idTamQlW6LjL39NiQlQd++9uYnPz9PN1kp5QEa9IXUwYRzjPo6nE1R8bSsU4FP+gbSumY5O13f2LFw+LCdl/Wtt6BlS083VynlQRr0hUx65n9ne/IR4c17mvP4dX4U/3oljBgBUVHQtastI3zDDZ5urlKqANCgL0S277ezPe05lkz3FjUZfW9zav2xFa4Pgm3boHlz+PpreyWvQyWVUg5O1ZgVke4iEiUi0SIyNJf1viKy2LF+q4j4O5ZXFZEfRCRZRGa4tulFx+lz53lj2S4emP0rZ9My+bRvILNbF6dW0P1w8822m2buXNi1C+69V0NeKXWBy17Ri4gPMBO4HYgDtotIsDEmMttm/YBTxphGIhIETAYeAlKBUUBLx5e6AsYYlv9+iIlrdpOYks6z/2jAyw2LU3r8EFi40E66/c478MILULq0p5urlCqgnOm66QREG2NiAERkEdATyB70PYExjsfLgBkiIsaYs8BmEWnkuiYXDfvikxm1Mpxf9p2knV8lJt9YkyYff2Bvcipe3E4C8vrrNuyVUuoSnAn6OsDBbM/jgM4X28YYkyEiiUBV4IQzjRCR/kB/AL8iPgQwNT2TWZv2MXvTPkqVKMbkO/x54KelFOv6LqSkQL9+9uan2rU93VSlVCHhTNDn1uFrrmKbizLGzAHmAAQGBjr9Om+zJfoEI1eGE3viLPe3rM7Yo79QPugxiI+3tWgmToSmTT3dTKVUIeNM0McB9bI9rwscvsg2cSJSHKgIJLikhUXAieQ0JqyOZOXOwwRULsW6GnE0G/0SxMRAt2725qdOnTzdTKVUIeVM0G8HGotIAHAICAL65NgmGOgL/Ar0BjYaY4rslbmzsrIMi7Yf5O21u0k5n8G7FY5w36JZFNv5B7RpA2vX2vrwOopGKZUHlw16R5/7QGA94APMNcZEiMg4IMQYEwx8CiwQkWjslXzQ368Xkf1ABaCkiPwLuCPHiJ0i6c+jSYxYEc6Ov07Rp9hRRv68gDKbf4SAAPjiCzvDUzGnRr8qpdQlOXXDlDFmDbAmx7I3sz1OBR64yGv989A+r3PufAYfbNjLpz/H0vLsMTZHLqfu96uhenX48EN49lkoWdLTzVRKeRG9MzYfbfzzGKNWRnA+7hBf7Amm88YVSKlSdhTNkCFQvrynm6iU8kIa9PngaGIqY1dFsHnHPoaGrSLol+X4ZKTDgAEwciTUqOHpJiqlvJgGvRtlZhk+/3U/09eE88C2YLZvW0appNO2/338eGjY0NNNVEoVARr0bhIWl8jIr3bS+NuVfPvbIqolHLUjaCZNgnbtPN08pVQRokHvYmccsz3FLVjCtJ8X0PD4fkxgICz9Em65xdPNU0oVQRr0LmKMYV34UZbPWEz/NR/TMS6SzEaNYMYSpHdvHQuvlPIYDXoXOJhwjn9/FMxNn73Px9FbSb+mJsyejc9TT0GJEp5unlKqiNOgz4PElHQWf76O6jM/YGz4D2SWKUPm+AmUGPwylC3r6eYppRSgQX9Vzmdk8d3HX1Hug2n0j/qNNN9SpDw/kHJj34SqVT3dPKWUuoAG/RUwmZn8PusLSk6byj/3h3OmXEWODxnKNcNexVcDXilVQGnQOyM9nf0zPqHYO+/Q4UgsRyvXYM+IiTQe+hLly5XzdOuUUuqSNOgvJTmZhA9mwXvT8D95jOga/vw65j06vjGAmqV8Pd06pZRyigZ9buLjSXn3fZg5gyrJSYT4teSnweO5fcgTNCqlo2iUUoWLBn12sbFkvDMV5s6ldFoq3za+jn1PPk+vFx4gsEIpT7dOKaWuigY9QHw8ZsirmIVfYhBWNO/Gzoee5omn7+aOGlpRUilVuGnQr15N+pP94PQp5re7hx/veYxn+9zEg42rebplSinlEkU36M+c4dzAQZT5fB7R1f2ZMGA89/W9m/nt6lCsmJYrUEp5jyIZ9GkbfyDtkccpe+wws7s+yLmhI5hzR3PK+hbJH4dSyssVqWQzKSnsf34I9efP5mjFGsweMYeglx/Gr2oZTzdNKaXcpsgE/f7vt+DzxOMEHIphdZceVP3oQ15v4+/pZimllNsV83QD3O100jm+f3QQte/shm/iab6fOo/uP6+ki4a8UqqI8Nor+ozMLFYv/4mAIc9z28HdhF1/J/UWzuM2v1qebppSSuUrp67oRaS7iESJSLSIDM1lva+ILHas3yoi/tnWDXMsjxKRO13X9IvbHnOCj4Je5Y5HutPwZByHZn1Kq5/XUklDXilVBF32il5EfICZwO1AHLBdRIKNMZHZNusHnDLGNBKRIGAy8JCINAeCgBZAbeB7EWlijMl09YEAnDl9hlXj/027BTN5MX4/8V1votriLyhXt647dqeUUoWCM1f0nYBoY0yMMeY8sAjomWObnsB8x+NlwK0iIo7li4wxacaYWCDa8X4ut2f1RlL8Augz7TVqFs8k7fMFVN/8A6Ihr5Qq4pwJ+jrAwWzP4xzLct3GGJMBJAJVnXwtItJfREJEJCQ+Pt751mdTo11Ljvk1IvqzxVQ+GIvvY4/qPK1KKYVzH8bmlpbGyW2ceS3GmDnAHIDAwMD/We+MinWuoVX4b1fzUqWU8mrOXNHHAfWyPa8LHL7YNiJSHKgIJDj5WqWUUm7kTNBvBxqLSICIlMR+uBqcY5tgoK/jcW9gozHGOJYHOUblBACNgW2uabpSSilnXLbrxhiTISIDgfWADzDXGBMhIuOAEGNMMPApsEBEorFX8kGO10aIyBIgEsgAXnDXiBullFK5E3vhXXAEBgaakJAQTzdDKaUKFRHZYYwJzG2d15dAUEqpok6DXimlvJwGvVJKeTkNeqWU8nIF7sNYEYkH/srDW1QDTrioOYVBUTte0GMuKvSYr0x9Y0z13FYUuKDPKxEJudgnz96oqB0v6DEXFXrMrqNdN0op5eU06JVSyst5Y9DP8XQD8llRO17QYy4q9JhdxOv66JVSSl3IG6/olVJKZaNBr5RSXs5rgv5yE5gXJiJST0R+EJHdIhIhIoMcy6uIyHcistfxvbJjuYjIh45j3yUi7bO9V1/H9ntFpO/F9lkQiIiPiPwhIqsdzwMck83vdUw+X9KxvEBNRn+1RKSSiCwTkT8d57pLETjHgx2/0+Ei8h8RKeVt51lE5orIcREJz7bMZedVRDqISJjjNR+KODGVnjGm0H9hyyfvAxoAJYFQoLmn25WH46kFtHc8Lg/sAZoDU4ChjuVDgcmOx3cDa7Ezel0HbHUsrwLEOL5Xdjyu7Onju8RxvwIsBFY7ni8BghyPZwMDHI+fB2Y7HgcBix2PmzvOvS8Q4Pid8PH0cV3ieOcDTzselwQqefM5xk4jGguUznZ+n/C28wz8A2gPhGdb5rLzip3To4vjNWuBuy7bJk//UFz0g+0CrM/2fBgwzNPtcuHxfQ3cDkQBtRzLagFRjsf/Bh7Otn2UY/3DwL+zLb9gu4L0hZ19bANwC7Da8Ut8Aiie8xxj50bo4nhc3LGd5Dzv2bcraF9ABUfoSY7l3nyO/55DuorjvK0G7vTG8wz45wh6l5xXx7o/sy2/YLuLfXlL141Tk5AXRo4/V9sBW4EaxpgjAI7v1zg2u9jxF6afy/vA60CW43lV4LSxk83DhW3P02T0BUQDIB6Y5+iu+kREyuLF59gYcwiYChwAjmDP2w68+zz/zVXntY7jcc7ll+QtQe/UJOSFjYiUA74CXjbGJF1q01yWOT05u6eJyD3AcWPMjuyLc9nUXGZdoTheh+LYP+8/Msa0A85i/6S/mEJ/zI5+6Z7Y7pbaQFngrlw29abzfDlXeoxXdezeEvReNwm5iJTAhvyXxpjljsXHRKSWY30t4Lhj+cWOv7D8XK4H7hWR/cAibPfN+0AlsZPNw4Vt94bJ6OOAOGPMVsfzZdjg99ZzDHAbEGuMiTfGpAPLga5493n+m6vOa5zjcc7ll+QtQe/MBOaFhuNT9E+B3caYadlWZZ+EvS+27/7v5Y87PsG/Dkh0/Hm4HrhDRCo7rqbucCwrUIwxw4wxdY0x/thzt9EY8wjwA3ayefjf4y3Uk9EbY44CB0WkqWPRrdi5lb3yHDscAK4TkTKO3/G/j9lrz3M2LjmvjnVnROQ6x8/w8WzvdXGe/tDChR9+3I0dnbIPGOHp9uTxWG7A/jm2C9jp+Lob2z+5Adjr+F7Fsb0AMx3HHgYEZnuvp4Box9eTnj42J469G/8dddMA+w84GlgK+DqWl3I8j3asb5Dt9SMcP4conBiN4OFjbQuEOM7zSuzoCq8+x8BY4E8gHFiAHTnjVecZ+A/2M4h07BV4P1eeVyDQ8fPbB8wgxwf6uX1pCQSllPJy3tJ1o5RS6iI06JVSystp0CullJfToFdKKS+nQa+UUl5Og14ppbycBr1SSnm5/wPT7+BSgA2AnwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "t2_list = []\n",
    "n_list = [1,5,10,50,100,500,1000,5000,10000]\n",
    "for n in n_list:\n",
    "    lst = [i for i in range(n)]\n",
    "    total_time = 0\n",
    "    for i in range(10):\n",
    "        total_time += timeit.timeit(randomized_qsort,number=1)\n",
    "    ave_time = total_time/10\n",
    "    t2_list.append(ave_time)\n",
    "    \n",
    "plt.plot(n_list,t_list)\n",
    "plt.plot(n_list,t2_list,color='r')\n",
    "plt.show\n",
    "\n",
    "#raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "991ee87c525d8fa29bd448aa80dbf243",
     "grade": false,
     "grade_id": "cell-b666e68e84dfce03",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 5.\n",
    "\n",
    "### Question 5a.\n",
    "\n",
    "Remove the median-of-3 partitioning, and just use the first element in the array. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "90dbb100f881a2c9a61720a0753ca401",
     "grade": false,
     "grade_id": "cell-4daf36021c15eaf0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def qsort(lst):\n",
    "\n",
    "    indices = [(0, len(lst))]\n",
    "\n",
    "    while indices:\n",
    "        (frm, to) = indices.pop()\n",
    "        if frm == to:\n",
    "            continue\n",
    "\n",
    "        # Find the partition:\n",
    "        N = to - frm\n",
    "        inds = [frm + int(N * n) for n in locations]\n",
    "        #values = [lst[ind] for ind in inds]\n",
    "        partition = lst[0]\n",
    "\n",
    "        # Split into lists:\n",
    "        lower = [a for a in lst[frm:to] if a < partition]\n",
    "        upper = [a for a in lst[frm:to] if a > partition]\n",
    "        counts = sum([1 for a in lst[frm:to] if a == partition])\n",
    "\n",
    "        ind1 = frm + len(lower)\n",
    "        ind2 = ind1 + counts\n",
    "\n",
    "        # Push back into correct place:\n",
    "        lst[frm:ind1] = lower\n",
    "        lst[ind1:ind2] = [partition] * counts\n",
    "        lst[ind2:to] = upper\n",
    "\n",
    "        # Enqueue other locations\n",
    "        indices.append((frm, ind1))\n",
    "        indices.append((ind2, to))\n",
    "    return lst\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9d457eff304d19e031a8eabb4615ca3b",
     "grade": true,
     "grade_id": "cell-97473a9e0d12e745",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(qsort([4,2,1])==[1,2,4])\n",
    "assert(qsort([0])==[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lst = [i for i in range(5)]\n",
    "qsort(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8f0166e7d0021886bb7176f35011a633",
     "grade": false,
     "grade_id": "cell-2ca71dd53b31262b",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 5b.\n",
    "\n",
    "Does this change the running time of your algorithm? Justify your response with a graph. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "bd863db414089f9ead9906b3c2c34a15",
     "grade": true,
     "grade_id": "cell-1f3a6df29d324853",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "t3_list = []\n",
    "n_list = [1,5,10,50,100,500,1000,5000,10000]\n",
    "for n in n_list:\n",
    "    lst = [i for i in range(n)]\n",
    "    total_time = 0\n",
    "    for i in range(10):\n",
    "        total_time += timeit.timeit(randomized_qsort,number=1)\n",
    "    ave_time = total_time/10\n",
    "    t3_list.append(ave_time)\n",
    "    \n",
    "plt.plot(n_list,t_list)\n",
    "plt.plot(n_list,t2_list,color='r')\n",
    "plt.plot(n_list,t3_list,color='g')\n",
    "\n",
    "plt.show()\n",
    "#raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "51af6d987694ab6231a6f4aa19f39164",
     "grade": false,
     "grade_id": "cell-67512d1d42af415f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Part B. Recursive quicksort. \n",
    "\n",
    "One main difference between the quicksort algorithms in Cormen et al. and the implementation in the code above is that quick sort (in the code in this notebook) is not recursive, while $QUICKSORT$ in Cormen et al. is. Given the limitation of Python so that it can only make 500 recursive calls, estimate the maximum size of the list that can be sorted by Python if a recursive quicksort is to be used. Explicitly state all assumptions you make in getting to an answer.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7be7bc411376ac8090621f3d68630c10",
     "grade": true,
     "grade_id": "cell-4af5aab4ad1a7225",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "We can assume that the most efficient recursive call will be with the best case scenario, that the sub-arrays are evenly divided. In that case we would have a binary tree with depth 500, which would have 1000 leaf nodes. As such, the list should be maximum length 1000 to recursively sort with quicksort in python. "
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}