Last active
October 16, 2019 17:32
-
-
Save steven-tey/e4658ff139a9378eef5700a1738cf2da to your computer and use it in GitHub Desktop.
CS110 Session 6.2 Pre-Class Work
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "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": null, | |
| "metadata": {}, | |
| "outputs": [], | |
| "source": [ | |
| "NAME = \"Steven Tey"\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": 15, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "1.0961731639999925\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "import timeit\n", | |
| "import random\n", | |
| "\n", | |
| "eps = 1e-16 # This is to create a infinitisimally small gap between the last index in the list to the actual \n", | |
| " # length of the list - we are taking 1 minus this eps value in the following line.\n", | |
| "N = 10000\n", | |
| "locations = [0.0, 0.5, 1.0 - eps]\n", | |
| "\n", | |
| "\n", | |
| "def median(x1, x2, x3): \n", | |
| " '''\n", | |
| " This function is to determine the closest approximation to the true median\n", | |
| " by picking the first element, the middle element and the last element and\n", | |
| " choosing the element out of the three that is in the middle in terms of value.\n", | |
| " '''\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", | |
| " '''\n", | |
| " This function is to sort the list according to the quicksort algorithm.\n", | |
| " '''\n", | |
| " indices = [(0, len(lst))] # Create the list containing a tuple of the first and last indices of the list\n", | |
| "\n", | |
| " while indices: # Using a while loop to remove the elements in 'indices' and assigning them to the 'frm'\n", | |
| " # and 'to' variables. This while loop breaks when the 'frm' and 'to' variables are \n", | |
| " # non-identical\n", | |
| " (frm, to) = indices.pop()\n", | |
| " if frm == to:\n", | |
| " continue\n", | |
| "\n", | |
| " # Find the partition - uses the median function from above to find the optimum partition point\n", | |
| " # As we know, the closer the partition point is to the true median of the list, the better the\n", | |
| " # partition balance.\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 the list into two according to the partition\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", | |
| " # Rearrange the numbers to make it in such a way that the numbers larger than the pivot is on the\n", | |
| " # right of the pivot and the nummbers smaller than it are on the left.\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)) # append the indicies with the tuples from the list with the smaller numbers\n", | |
| " indices.append((ind2, to)) # append the indicies with the tuples from the list with the bigger numbers\n", | |
| " return lst\n", | |
| "\n", | |
| "\n", | |
| "def randomized_quicksort():\n", | |
| " '''\n", | |
| " This function is to generate a list of random numbers from 1 to N, which in this case, is 10,000.\n", | |
| " The function then performs quicksort of the list and sorts it.\n", | |
| " '''\n", | |
| " lst = [i for i in range(N)]\n", | |
| " random.shuffle(lst)\n", | |
| " return qsort(lst)\n", | |
| "\n", | |
| "\n", | |
| "def test_quicksort():\n", | |
| " '''\n", | |
| " This function is to test the quicksort and see if it works.\n", | |
| " '''\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 $RANDOMIZED-QUICKSORT$ method in Cormen et al. takes in 3 parameters - $A, p$ and $r$. These parameters stand for the list itself, the first index of the list and the last index of the list. It then partitions it and performs randomized quicksort _recursively_ on the partitioned lists all the way until the entire list is sorted. \n", | |
| "\n", | |
| "In contrast to that, our `randomized_quicksort` function generates a list of random numbers from 1 to N and then performs quicksort on it. No recursion is involved here." | |
| ] | |
| }, | |
| { | |
| "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": 32, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "a321a7fcecb9c9cce252ea2c6030d4ce", | |
| "grade": true, | |
| "grade_id": "cell-e0e1dac71ac7feb6", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [ | |
| { | |
| "data": { | |
| "image/png": "iVBORw0KGgoAAAANSUhEUgAAAyYAAAJhCAYAAAC0HaRSAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAAMTQAADE0B0s6tTgAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nOzdd3hUVfoH8O9kJpOZSe+VBEhIguICUhVcmtjAQhEU1GADFX8qrB1dWNe1g6IgICpNRQQs64IoShFQKdIlvVATUiAhIXWS9/dHMpeZZJJMAskMyffzPDyaue3MvWfu3HfOOe9RiYiAiIiIiIjIjpzsXQAiIiIiIiIGJkREREREZHcMTIiIiIiIyO4YmBARERERkd0xMCEiIiIiIrtjYEJERERERHbHwISIiIiIiOyOgYmDysjIgEqlQkpKyiXd75IlS9ChQwc4OTlh6dKldi0L2d+sWbMwcODAFj1GSkoKrrnmGri4uGDw4MEteiwAUKlU+Pnnn1v8OK3hpZdeavFz1tJ14J577sGkSZNabP/mJk2ahHvuucemdVuj7reUpUuXIiwszCGO01plaQ8GDx6Ml156yd7FAACUlZVh3Lhx8PDwgEqlsndxLBiNRqhUKmzZssXeRXFYrXnfvdQYmDTg2LFjePjhhxEeHg4XFxeEh4fj1ltvxYYNG+xdtGYpLy/HY489hueeew4nT57E+PHj66zz8ccfo2PHjq1arsGDB0Oj0SAjI6NVj9uaTMGdSqWCk5MTPD090adPH/z73/9GUVFRq5Rh4MCBmDVrlsVrTz/9NP773/+26HFfe+01GAwGJCUl4euvv75k+/35559b7QvTdO1UKhV8fHwwfPhw7Nu3r1WO3dJaow405tSpU3jooYcQHBwMFxcXdOnSBa+88grKy8ubtJ+5c+di/vz5LVTKi9PUh6mMjAxoNBoMHTq0ZQvWgPHjx1vUc3s+7FyqID0pKQljxoxBYGAg9Ho9IiMjce+99za5rtVmy7lp7Ee+r7/+Gs8//3yjx0pJSYFKpWrR78xVq1Zhy5Yt+O2335CZmVln+YgRIzBu3Dir2z7zzDPo1q1bi5VNo9EgMzMT1157bYsdw17Bz1133YWHHnqo0fU2bNiAAQMGwNPTEx4eHujevTvefPNNZfn8+fMxd+7clixqi2FgUo/ExERcffXVSEpKwsKFC3HkyBGsXbsWI0eOxPTp0+vdrqysrBVL2TSnTp1CaWkpRowYgeDgYOj1ensXCUePHsWhQ4cQFxeHFStWtPjxLvbL52L9/vvvOHXqFHbv3o0nnngCn3/+Ofr27YuzZ882e58XU+fc3Nzg4+PT7O1tkZaWhoEDByIiIqJZx6qqqoLRaGyBkjXNV199hczMTGzfvh1+fn649dZbHfrzbqvWqAMNycrKQr9+/ZCSkoLVq1cjOTkZb7/9NpYsWYJRo0ZBRGzel6enJzw9PVuwtM3TnHqyfPlyTJo0Cfv378fRo0dboFT1ExFUVFRAr9fD39+/VY/dksrLy3HjjTfCyckJ69evx5EjR7Bw4UIYDAZUVlY2a58VFRVNqqMN8fHxgZub2yXZ18VKS0tD165d0a1bNwQFBdVZHhcXh++//x75+fkWr1dVVeGLL75AXFxcs45r62clKCgIWq22Wce43B04cAC33347br75ZuzatQu7du3Ciy++iPPnzyvrOOq90CZCVg0dOlT69+8vVVVVdZaZv7ZkyRIJDQ2Vzz//XDp37izu7u4iIvLxxx9L9+7dxWAwSHh4uLz00ktSUVGhbBcXFycTJkyQ6dOni4eHhwQEBMjcuXOV5enp6QJAvvnmG+nTp48YDAYZNGiQHD16tMFyL1u2TCIjI0Wr1Uq3bt1k/fr1IiKyefNmAWDxLz093WJba+ts3rzZ5rLMnTtXOnXqJHq9Xnr37i2bN29u9Dy/8sor8sADD8jWrVslKirKYtltt90mjz76qMVru3fvFrVaLVlZWSIikpqaKiNHjhRXV1cJDg6WqVOnyvnz55X1IyIi5I033pDRo0eLXq+Xt99+W7KysmTMmDESGBgobm5uct1118m+ffssjrNx40aJjo4WnU4nI0aMkDfeeEMiIiKa/X5N5zA5Odni9dzcXAkICJBnn3223vVM18VUf2bOnCkDBgyQOXPmSEhIiHTr1k1ERF577TWJjY0VvV4vUVFRFvUpLi7O4rqa3otpXyZFRUXy4IMPipeXl7i6usro0aOVc23az8SJE2XGjBni7e0twcHBMnv27Hrfd0REhMVxZ86cKSIi69evl27duolWq5XIyEhZtmxZnXO1evVq6dOnjzg7O8vu3butnk/zf0uWLBERUf5/2LBhotfr5eqrr5YDBw5YbL9y5Urp2rWr6HQ6ufLKK2X16tX1vgfTPjdu3Kj8ffDgQQEg+/fvV15r6PyLiAwaNEieeeYZmTx5sri5uUlERISsXLnSYp2vvvpKwsPDxWAwyH333Sf/+Mc/ZNCgQcpyW67PhAkT5Pnnnxdvb28JCAiQTz/9VM6ePStjx44VV1dXueqqqyzqu3kdsHYPML9uIo3X+/fff18CAgLEw8NDpk+fLhMmTJC4uLh6z+39998v4eHhUlJSYvH6oUOHxMnJSVasWGFRNvP7qOn+a/7+J06caHG+pk6dKoGBgaLT6aRnz57yxx9/1HnfIiLbt28Xb29vpS7+9NNP0qNHD9HpdOLr6yu33HJLk6/Dc889J76+vjJy5Mg6n4WGzomISGRkpPz6669y//33y7///W+LZbXfd0lJiUyaNEkMBoOEhYXJ8uXLJTQ0VPlMiIjs3LlT+vfvL1qtVsLCwuTNN9+02CcAWbx4sQwdOlRcXFxk9erVFseZOXNmnXphXpbVq1dLx44dxdPTU+6//34pLS1V9h0RESFvvfWWjBo1SvR6vXTt2lV27dolBw8elL59+4qrq6vccsstkpeXZ/VcLFmypN7vr4buJbXt27dPAEhubm6D576+71GRC/Xwhx9+kCuuuELUarVMnTrV6rmprb7vAZNBgwbJjBkzRKT6OeP555+XkJAQcXFxkU6dOsnChQtFROr9fL777rvSsWNH0Wq1EhoaavG5ra2hOlz7+8L8HmRSWloqXl5e8tFHH1m8/uOPP4parZaTJ0+KiMg333wjffv2FTc3NwkJCanzHT1jxgwZNGiQvP322xIcHCw9evSQBx98UO6++26L/SYkJIiTk5McPXpUKioqlOcTkervawCyadMmiY2NFTc3Nxk1apScPXtW2T4nJ0dGjhwpOp1OoqOj5fvvvxcAsm3bNqvnp/YxkpOTBYB899130qtXLzEYDDJkyBA5fvy4ss3EiRPl3nvvlaeeeko8PDwkMDBQ5s2bpyw3ldPc4sWLle/jGTNmWJx3tVpttWxvv/229OjRw+oy87KY7jGLFy+2el833VsrKirkhRdekJCQEHFzc5PBgwfLoUOHlH3t3r1brrnmGjEYDOLl5SWDBw+WgoKCBo9/MRiYWJGTkyMqlUpWrVrV6LpLliwRFxcXuf7662Xv3r3Kxfzoo49k48aNkpaWJuvXr5egoCCZP3++sl1cXJy4ubnJo48+KvHx8bJo0SJxdnZWPgSmG1j37t1l06ZNcvjwYenTp4+MHj263rLs2LFD1Gq1zJ07VxISEuTll18WrVYr6enpUlZWJr///rsAkF27dklmZqYYjUaL7cvKymT27NkSFhYmmZmZkpmZKWVlZTaV5ZNPPpHOnTvLDz/8IKmpqfL++++LXq+vE/zUFhUVJT/99JNUVVVJaGiobN++XVn2xRdfiL+/v0U5n3nmGRk2bJhS3qioKJk2bZokJCTIrl27pG/fvvLII48o60dERIiPj4989NFHkpqaKsePH5f09HSZO3euHDx4UBITE2XKlCnSoUMH5cHozJkz4u7uLk888YQkJCTIokWLxNvb2yIwaer7begL6amnnpLY2Nh617MWmLi6usr48ePl8OHDcuTIERERmT17tmzbtk3S0tJk1apV4urqKuvWrRMRkfz8fOnbt6/84x//kMzMTMnOzlb2Zf5w9vDDD0tUVJRs3bpV/vzzT+nXr58MHz5cWR4XFyfu7u7y7LPPSmJioixatEgA1HnwN8nOzrY4bmFhoaSnp4tWq5WXXnpJEhIS5IMPPhC1Wq1ce9M5iI2NlR9//FGSk5MlPz/fYr9Go1G++uorAaDU1eLiYhGp/tLu1KmTfPvtt5KYmCgjR46Uq6++Wtn2l19+ET8/P/nqq68kNTVVPv/8c9Hr9fL7779bfQ+mfZoCk5KSEnn66acFgHLuGzv/ItUPHR4eHjJnzhxJTk6WmTNnik6nk9OnT4uISEpKimg0GnnllVckISFBXnnlFXFzc7N4KLD1+jz//POSmJgor776qjg7O8vNN98sn332mSQlJcmoUaMszod5HSgrK1POZ2Zmpnz33Xfi7OwsP/74o4g0Xu+3bNkiGo1GFixYIPHx8fLoo4+Km5tbvQ/hlZWV4uHhIa+//rrV5TfccIPceuutItK8wGTChAkSExMjP/74o6SkpMiaNWvkt99+q/O+N23aJF5eXvLll1+KSPUXtYeHh7z33nuSkZEhBw4ckHfffbdJ18HV1VW5hyQlJUlmZqYAkLVr10pmZmadOm1u27ZtEhYWJlVVVfLjjz9Kly5dLJbXft8zZsyQ0NBQ2bhxo+zfv1+GDBkiOp1OCUzOnTsnvr6+8uCDD8qRI0fkiy++EIPBIJ9//rmyDwBKgJGamipZWVkWxyksLJQxY8bIuHHjlPphKotOp5ORI0fKwYMHZdOmTeLj4yPvv/++su+IiAgJCAiQFStWSGJiotxxxx0SExMjQ4YMkS1btsi+ffskKipKpk+fbvV8FBcXy1NPPSXXXHONcmyj0djovaS248ePi5OTk3z00UdWf3QUafh7VORCPezfv7/s2LFDjhw5IgUFBVbPTW1NCUxWrVol4eHhsn37dsnIyJBNmzbJN998IyJS57u8sLBQdu3aJR4eHrJhwwY5evSo7NixQ3nwtKahOpyfn29xvusLGKdMmSIDBw60eG3ixIly0003KX+vXLlS/ve//0lqaqps2bJFoqOj5YUXXlCWz5gxQ1xdXeXuu++Wv/76S+Lj42Xbtm2i1+vl3LlzFusNGTJEROoGDaYH/qFDh8quXbtk165dEhERofzgJyIyfvx4ueqqq2Tnzp3y22+/Se/evZsVmPTs2VM2b94shw4dkquvvlrGjRtn8d7d3Nzk8ccfl4SEBFmwYIFoNBrlGI0FJoWFhXL77bfLhAkTJDMz0+LHDnPLly8XDw8P2bt3r9XlprKY7rvFxcUW9/V58+aJwWCQv/76S0REXnjhBendu7ds27ZNkpOT5bnnnpPg4GApLCwUEZEuXbrICy+8IGlpaXLo0CFZsGABA5PW9scffwgAi18VDx48KK6ursq/X3/9VUQu/JLT2AP466+/rnyoRKq/uEJDQy2+ZCdOnChjxowRkQs3MPPg6IsvvhBfX996jzF+/Hi58847LV7r16+fPP300yJy4YPVUFnNPyQmtpSlU6dO8v3331tsN3z48Dq/9Jnbvn27BAQEKIHHtGnT5OGHH1aWFxUVicFgsPilumPHjrJ48WIRqf5Vq1evXhb73LFjh2i1WmWfERERMmnSpHrLIFL9kOvq6ipbt24VEZF58+ZJeHi4VFZWKuvcfffdFuelqe+3oS+khQsXik6nq3c9a4GJm5ubctOoz5QpU+T+++9X/h4wYECdX9DMH87OnTsnGo3G4mE6Pj5eAMjhw4dFpLreXnHFFRb7iI6Olg8++KDectQ+7nPPPSd9+vSxWGf8+PEyduxYi3OwdOnSBt+ftZu8SPUDlvmvwb/99psAUM7XkCFD6pT34YcflgcffLDeYwEQnU4nrq6uolKpBIDcfPPNDZav9vkfNGiQxTYVFRViMBiUevTss89Kv379LPbRr18/JTBpzvUx1e2pU6cqr5keakxf+rWDU5PTp09LWFiYvPrqq8prjdX7cePGyfjx4y3eY2hoaL2BSVZWltIaa80TTzwhXbt2FZGmByapqakCoE5rm4npfW/YsEE8PT0typCbmysA5NixY3W2s/U6dO7c2eIeUvtBpyEPPfSQ8pBuNBrF399fduzYUe/79vPzU+6LIiKJiYkWrYgLFiyQkJAQi3P33HPPSe/evZW/AcisWbMsylH7OOYPO+brqFQqi4eoyZMnK99lItX3YfPWb1MdNG+pfP311y0C5tpMv6yba+xeYs3s2bNFq9WKt7e33HzzzTJnzhw5c+aMxfYNfY+a6uGWLVss1rF2bmprSmDyzjvvyLBhw6wGUNa+y9esWSPR0dEW17g+ttRha+e7th07dohKpZK0tDQRqX6wdnV1rdMSbG7FihUWgfaMGTPEw8PDohVFpPpHy08//VREqluPIiIilPpcX2Dy559/Ktu/8soryv00Ly9P1Gq1xWdv3bp1zQpM1q5dq6yzfPlyCQwMVP6eOHGihIeHW/yYOn78eOWe2FhgYlq/oe8iU9nGjh2r9H6YMGGCfP755xb3m/rq4+HDh8XNzU25RufPnxedTifx8fEW63Xq1ElZR6fTKT/otAaOMbFCrPQXjYmJwf79+/Hnn3/i/PnzFv1Rvb296wwY/+2333DDDTcgNDQUbm5umDVrFo4fP26xztVXXw2NRqP83bdvXyQmJlqsc9VVVyn/HxQUhLy8vHr7wiYmJqJ///4Wr11zzTV19tlc9ZWlqKgI6enpGD9+PNzc3JR/mzdvRlpaWr37W7ZsGcaOHQu1Wg2getDXV199hdLSUgCAq6srRowYgVWrVgEAdu3ahZMnT2L06NEAgEOHDuHAgQMWxxw+fDjKy8tx8uRJ5Tg9e/a0OG5FRQVefPFFdO3aFV5eXvD09ERxcbFyfZKTk9GjRw84OV34ePTu3Vv5/+a+3/qISJMHcXfp0qVOX+R169Zh4MCBCAwMhJubGz799NM6da4haWlpMBqNFnUoNjYWXl5eFnWo9qDGoKAgZGdn23wcW+tp7evWFLXrKgCljIcOHcIzzzxjce2WLl3a6LVbtGgR9u3bh9WrVyMmJgaLFi2yWG7L+Tcvl0ajgZ+fn1KuxMRE9O3b12J987+bc33UajV8fX1x5ZVXKq8FBgYCAHJycup9r0ajEXfeeSf69OmDF198EYBt9b72e9BoNLj66qvrPY61e21tzs7Oja5jzV9//QVXV1eLz25tiYmJuO2227BkyRLccccdyuu+vr6466670K1bN9x1111YsmSJkqTC1uvQvXt3i3uIrUpLS7F69WrcddddAKqv4dixY7F8+XKr6+fn5yM3Nxe9evVSXouOjoa7u7vF++zVq5fF982l/Mz5+/sr9Qqwfk8wr/umdWvXy4bqpDXN+c6bPn06MjMzsXDhQkRHR2P27Nno1q0bTp061aR9Xsz9yRZjxozBkSNH0LVrV0ybNg1bt25tcP3rr78eKpUKkZGReOSRR7Bu3bp6P1+21uHGXHvttYiKilLGh65duxZqtRq33367ss5ff/2F22+/HeHh4XB3d8fDDz9c574YExMDg8Fg8Zr5uNNff/0VOTk5GDt2bIPlqX3fN9XBtLQ0VFZWWnxGGrovNOcYJr169VKeaQDrz3UXS6PRYPXq1UhNTcWLL74IjUaDhx56CDfddBOqqqrq3a6goACjRo3Co48+qtxfkpOTUVpait69e1vc148eParc1x9//HEMGzYMo0aNwoIFC5CXl3dJ309tDEysiIqKgkqlsqhMWq0WUVFRiIyMrLN+7Q9UYWEhRowYgU6dOmHt2rXYu3cvnn/+eVRUVFisZ8vDqPmXsmn9+m42tnzJX4z6ymIacPXFF19g//79yr/4+Hi8/vrrVvdl+vJduHAhNBoNNBoNrr32WhQUFOC7775T1hs/fjy+/vprVFRUYNWqVRg+fLgyULeoqAh///vfLY554MABJCcnIzg4WNlH7evz5ptvYtmyZXj11Vexfft27N+/H15eXsr1aSxQaM77bUhCQoIS2JoeZMyvZe16Y+09paWlYfTo0Rg6dCjWrVuHffv24b777rO6bX1srT+1HxRVKlWDN8PmHqf2e2wKa3XVVMaioiK88847FtfuyJEjjSZfCAkJQZcuXTBmzBg888wzGD9+vPJebD3/DZ27xurdxVyfhs6HNdOmTUNubi6WL1+urG9LvW9qkB0QEAAPDw/Ex8dbXZ6QkIDOnTsDsP2zYWJLWUJCQvC3v/0NS5curZNgYeXKlfjpp58QExODd955B926dUNeXl6L199vv/0WBQUFuOaaa5R746JFi7Bq1SrlRxtzpvJcirrT3DLbck+wVgdrv9aU+wjQ/O88Hx8fjBs3Du+99x7++usvVFRUYOHChU3a58Xcn2zRsWNHJCcn49VXX0VRURFuvfVW/N///V+963t6euLgwYNYsGABtFotHnjgAYsAwdylfFa47777lHvnihUrMG7cOIvEOiNHjoRWq8Xnn3+OPXv24N13363zubV2LuPi4rBt2zYcO3YMy5cvx+jRoxtNDFBffbqU77f2MWrvu6HPYVPvYY3p3LkzJk+ejGXLlmHDhg3YuHEjtm/fbnVdEcHEiRPRsWNHi+cU0w8upmch07/ExEQ88sgjAIC3334bO3fuRN++fbFkyRLExMQ060dYWzEwscLPzw+DBw/G7Nmzm3yjBKp/ccnPz8ebb76J/v37Izo62uov13v37rVo/di9ezdiYmKaXe7Y2Fj88ccfFq/9/vvviI2NtXkfzs7OTc5OEhAQgKCgIBw7dgxRUVEW/8x/RTP33XffwdXVFQcOHLD4MPzf//0fli1bpqw3YsQIVFRUYOPGjVizZo1FiuPu3bsjISEBYWFhdY7b0K+sf/zxB+68806MGTMG3bp1g4uLi0VWrOjoaOzbt8/i2v/5558X9X7rk5eXh5UrVypfIKYMOFlZWco6hw4danQ/e/fuhV6vxyuvvILevXujS5cuSE9Pt1insWsbGRkJjUZjUYcSEhKQn5/fpDrUmEtRT4ELXxBNra/du3dHWlpanWsXGhpq8z7uu+8+ZGRkYO3atQBsO/+NiYmJwa5duyxe2717t/L/rXV9li9fjs8++wzfffedxYOALfW+9nuorKxsMK2yk5MTxowZgwULFtR56D58+DB+/vln5Ze9pn42unXrhqKiIuzZs6feddzd3bFhwwakpqbivvvuq3O/79evH/71r39h3759yM/Pxy+//NLs66BWq+Hk5NRofV22bBmmTp1a5wcXDw8Pq2mdvb294efnZ3GPSk5ORmFhofJ3bGws/vzzT4vgq7mfueZmr7pY1o59Ke4lnp6eCAoKUgLv5u6zJc6Nq6srxo4di8WLF+Pjjz/GJ598ohwLqHvv02q1uOWWW/D+++/j+++/x/fff2+1NftS3kvuvfdepKamYvXq1di8ebNFNq6srCxkZGRg5syZuO666xATE2M19bA1HTp0wODBg/Hxxx9jzZo1uO+++5pULnORkZFQq9XYu3ev8pr55+VS+vPPPy3uI+bPdbbcw5pbj0zXzTwzl7mZM2ciPj4eX375pUWLzhVXXKGkX659XzfP1njVVVfhhRdewM6dO+Hr64tvv/22yWW0FQOTesyfPx8pKSkYNGgQ1q9fj9TUVBw6dAjvvPMOAFhc2NrCw8Ph7OyMDz/8EGlpaVi4cKHVi5ifn48nn3wSiYmJ+Pjjj7Fq1SpMnTq12WV+4okn8PXXX2PevHlISkrCP//5T+zbtw+PPfaYzfuIiIjA6dOnsWfPHuTm5toUzatUKrz44ot4+eWXsWTJEqSmpmLPnj144403sGnTJqvbLFu2DHfccQe6detm8S8uLg4//fSTcvPS6XS47bbb8Nxzz+H06dMW3S0mTpwIrVaL8ePHY/fu3UhJScH333+Pp59+usHyRkZGYsOGDdi7dy/27t2LuLg46HQ6ZfmECRNw9uxZ/OMf/0BSUhI++eQTbNiwQfklpDnv1yQ3NxdZWVlISkrCZ599hgEDBsDf31/JXa/X69G7d2+8/vrrSExMxPfff48PP/yw0WsQGRmJc+fOYenSpUhJScGrr75q8VALVF/bP/74AydPnrSantjd3R0PPPAAnnrqKWzbtg179+7FpEmTMHz4cFxxxRWNlsFWjz76KA4cOIB//vOfSEpKwrx587BmzRo89dRTTdpPREQEAGD9+vXIzc21Oc3kiy++iPnz5+Pdd99FUlISDhw4gHnz5ildBm3h7OyMKVOm4NVXXwVg2/lvzOTJk7F792785z//QVJSEv7zn//g8OHDyvLWuD6HDh3CI488gjlz5sDNzQ1ZWVnIyspCUVGRTfX+0UcfxZo1a/DRRx8hMTERTz75ZJ10orW99tprEBHcfPPN2L59O44dO4Zvv/0Wt956K2699VZlroSoqCiEhIRg1qxZSElJwWeffYavvvqq3v127twZEyZMwD333IONGzciLS0N3377bZ2HTl9fX/z888/YvXu38gtheno6ZsyYgZ07d+Lo0aNYvXo1ioqK0KVLl2ZfB5VKhQ4dOmDTpk3Izs62On9RZmYmNm7ciEmTJtW5N952220WP9qYmzJlCmbNmoVNmzbh4MGDeOyxx6DT6ZR71sSJE1FWVoZHH30UCQkJWLlyJT744INmfeb27duHjIwM5ObmNmnbixUREYHExEQkJCQgNzcXVVVVTb6X7NmzB2PGjMF3332HpKQkxMfHY8aMGTh8+DBGjBgBoPnfo005N/Hx8XVabGtbtmwZli5divj4eCQlJeHbb79VHnBNqXJ/+ukn5OTkoLi4GP/73/8wf/58HDp0CGlpaVi1ahX8/Pzg6+tbZ9+X8l4SERGBwYMHY/LkyejUqZPFpKV+fn7w9PTE4sWLkZaWhpUrV+Ljjz+2ed+TJk3CG2+8AXd3dwwbNqxJ5TLn4+ODsWPH4sknn8Tu3bvxxx9/KHN6Xeq5sPLy8jBt2jQkJibio48+wpo1a5TnuujoaAQGBmLmzJlISUnB8uXLlR+3TCIiIrB3714cPXq03i5Tps/u5s2bkZGRgV27duGBBx6Av6mE/MwAACAASURBVL8/+vXrV2f9H374AW+++SYWLFiA8vJy5b5eWloKb29vPPbYY5gyZQq++eYbpKen4/fff8fzzz+PhIQEFBUV4amnnsL27dtx9OhRrFu3DidPnryoH9Eb1TpDWS5P6enp8sADD0hoaKhoNBrx8fGRm266Sb7++mtlndqDA2u/bjAYZNSoUfLWW29ZDHAypZN88sknxcPDQ/z9/S2yvtgyCNoaU5pDZ2fnOmkObRn8XllZKffee694enoqA79sLcuiRYskNjZWnJ2dJSgoSEaNGiUJCQl1jpGZmSlqtdpiULu5Dh06yNtvv638bUrrd8cdd9RZNyMjQ8aOHSuenp5iMBjkb3/7m7zzzjvK8oiICItBoSLVmaJuuukm0ev10rFjR1m5cmWd1Jo//fSTdOnSRUkXPGvWLImJibHYj63vV8Qyva1KpRJ3d3fp1auX/Pvf/64ziP3AgQPSq1cv0ev1MmjQIFm2bFmdwe/WBiu/9tpr4u/vL+7u7vLggw/K008/bTF48dChQ9KzZ0/RarX1pgsuLCyUBx54QDw9PRtMF2zOfMCmNdYG3ZtSfDo7O0tkZKTFQPfGBoiaM6VjBSzTBZvXLWv7+/rrr5Vz4efnJzfeeKPNWblMMjMzxdnZWf773/+KSOPn39p5ql0/V65cKR06dBCDwaCkEzffR3OuT+1j1D4f5nXAWlpWwDJdcGP1/r333lPOw5NPPtloumARkZMnT8oDDzwggYGBSnKBRx55pM69btOmTdK1a1fR6/Vyxx13yJw5cxpNF/zII4+Ir6+vkjp6586ddd63SPW9pEOHDjJt2jTJysqS2267TQIDA8XFxUW6du1qkYa2OddBpDrTUkREhDg5OVk9J2+99ZaEhYVZPUcbN24UtVotmZmZVtMFx8XFicFgkNDQUFmxYoX4+PhYDELeuXOn9OvXT0klay1dcO06Xvs4J06ckOuuu070er0yiNfad2Dtc9tYHaxvP+YKCwtlxIgR4ubmZvE91tC9pLbs7Gx5/PHHpWvXrkrq0/79+8uaNWss1mvoe7S+72Fr56Y2a2nOgQvp283vEab0/G5ubuLp6Sk33nijxeds7ty5EhQUJCqVSmbOnCnbtm2T6667TqmTAwcOVFJj13c+G6rDtgx+N1m6dKnV5Aki1d/fkZGRotPpZNiwYbJ48WKLNLgNHae4uFjc3NwssmuJ1D/43VztQeU5OTkyYsQIcXFxkS5dusjq1asbTI5R3+B38+en2sc1pQt+/PHHxd3dXQICAiyy05m2iYmJEb1eL6NHj5Z33nnHopzHjh2TAQMGiE6nqzdd8K5du+Suu+6S8PBw0Wq1EhQUJLfffrtF+nrzwe+10xCb/pmythmNRnnllVckIiJCnJ2dpUOHDnLvvffK6dOnpaSkRMaNGyehoaHi4uIinTt3bnCKgEtBJdLCAxPIqkmTJsFoNOKzzz6zd1HIBg899BAyMzOxbt06exeFqM2bOnUqvv76a2zfvt3quD5q2PHjxxEeHo5du3ahT58+9i4OUbNkZmaiQ4cOOHjw4CVttQeALVu2YOjQocjJybHaqtQc99xzDzQaDZYuXXpJ9tdeaRpfhaj9Wbp0KWJjY+Hv74+NGzdixYoVvNkQtZJ58+YhNjYWO3bsYGBig9TUVGzfvh0DBgzAmTNn8OyzzyI2NrbZmYeI7KmqqgqZmZl4+eWXce21116SoGTnzp04efIkevbsiYyMDDz++OO4+eabL1lQQpcOAxMiK44dO4aXXnoJubm56NSpE+bOnYu7777b3sUiahdUKlWDGYjIkkqlwocffoipU6dCp9Nh4MCBWLFixSXvP0/UGtLS0tClSxdERUVhzZo1l2SflZWVyvg0Ly8v3HDDDXjvvfcuyb7p0mJXLiIiIiIisjtm5SIiIiIiIrtjYEJERERERHbXpseYuLi4KBPaEBERERGRfeXk5NQ791ibDkz8/f1x4sQJexeDiIiIiIgAhIWF1buMXbmIiIiIiMjuGJgQEREREZHdMTAhIiIiIiK7Y2BCRERERER2x8CEiIiIiIjsjoEJERERERHZHQMTIiIiIiKyOwYmRERERERkdwxMiIiIiIjI7hiYEBERERGR3TEwISIiIiIiu2NgQkREREREdsfAhIiIiIiI7I6BCRERERER2R0DEyIiIiIisjsGJkREREREZHcMTIiIiIiIyO4YmBARERERkd0xMCEiIiIiIrtjYEJERERERHbHwISIiIiIiOyOgQkREREREdkdAxMiIiIiIgdRWlGJMQt+w3f7T9q7KK2OgQkRERERkYP469Q5/Hn0LH6Jz7Z3UVodAxMiIiIiIgeRkHUOAJBZUGLnkrQ+BiZERERERA4iIbMQAHAqv9TOJWl9DEyIiIiIiByEqcUk61wpKqvEzqVpXQxMiIiIiIgcgIgoLSaVVYLswvbVasLAhIiIiIjIAZzML0FhmRHOahWA9tedi4EJEREREZEDMLWW9O3kAwA4ld++BsAzMCEiIiIicgCm8SVDYgIAtL/MXAxMiIiIiIgcQHxWIVQqYHBNYMKuXERERERE1OoSMs8hwseATn6uUDup2JWLiIiIiIhaV2lFJdJzzyM2yANqJxWCPHQ4xa5cRERERETUmpJPF6FKgNhgdwBAsKcOmezKRURERERErSm+ZuB7bJAHACDES4+88+Uorai0Z7FaFQMTIiIiIiI7M6UKviK4OjAJ9tIBADIL2k+rCQMTIiIiIiI7S8g6B1etGmHeegBAqFf1f9vTAHgGJkREREREdiQiiM88h5ggdzg5Vc/6HuzJwISIiIiIiFpRTmEZzhZXILamGxcAhNR05WpPc5kwMCEiIiIisqP4rOrxJV2D3JXXQmpaTNrT7O8MTIiIiIiI7Cg+syYjl1mLiZfBGXpnNU6yKxcREREREbWGhJrAJMasxUSlUiHYS8esXERERERE1DoSsgoR6qWHh87Z4vVQLz1O5ZdAROxUstbFwISIiIiIyE7KjVVIyS5C12D3OsuCPXUoLq/EuRKjHUrW+hiYEBERERHZSWpOEYxVosz4bi6kZi6T9jLOhIEJEREREZGdJGSZBr7XbTFpb5m5GJgQEREREdlJQmZ1quCGWkzayySLDEyIiIiIiOwkPqsQLhondPQ11FkWbJpksZ1k5mJgQkRERERkJwmZ5xAd6A6Nuu5juakrF1tMiIiIiIioxeQVlSG7sAyxQXXHlwCAXquGt8EZmflsMSEiIiIiohaSmFU9vqRrcN3xJSYhXnpm5SIiIiIiopYTXxOYWMvIZRLsqcfpc6WorGr7kywyMCEiIiIisoOEzJpUwVYycpmEeulgrBLkFJa1VrHshoEJEREREZEdJGQVItDDBT6u2nrXCTalDG4Hc5kwMCEiIiIiamXGyioknS5ssLUEaF9zmTAwISIiIiJqZRl5xSgzVjU4vgQAQjyr5zJpD5m5GJgQEREREbWyhKzq8SVdbWwxaQ+ZuRiYEBERERG1soTMxjNyAUCAuwucVEAmx5gQEREREdGllpB1Ds5qFTr7uTW4nkbthCAPHU6xKxcRERERUduRkXsev6Xk2rUMIoKDJwoQFeAOrabxx/FgLz1bTIiIiIiI2pI3NyRg0tLdMFZW2a0MiacLkV1YhmsjfW1aP9hTh9yicpRWVLZwyeyLgQkRERERtRsn80tQbqxCQUmF3cqwNTEHADAo2t+m9UNrBsBnFbTt7lwMTIiIiIio3TDNoH7mfLndyrA1KQcuGif07eRj0/rBNSmD2/pcJgxMiIiIiKhdqKoS5BbZNzA5X2bE7owz6N/ZFzpntU3bKJMsssWEiIiIiOjyl19SgYpKAQCcLbZPYPJHWh4qKsXmblxA+5n9nYEJEREREbULpm5cAJDXxBaTMmMlROSiy7A1qWZ8SUzTA5O2npmLgQkRERERtQvZhRe6Qp1tQmBy5nw5er6yEUt2ZFx0GbYm5SDUS4/Ofq42b+NtcIaLxgkn2/hcJgxMiIiIiKhdMG8xOXPe9qxc6bnnUVxeiaW/ZVxUq0lG7nkczSvGoBh/qFQqm7dTqVQI9dIjk125iIiIiIguf5aBSVkDa1rKqxkwf+xMMXZnnG328X9NblqaYHPBXjqcyi+5JN3JHBUDEyIiIiJqF7LNA5Ni21tMzMejrP3zRLOPvzUxBxonlc0TK5oL8dTjfHklzpUam318R8fAhIiIiIjaBVOLiZ+bS5PGmJhaTNxdNFh3KBMl5U2fgb3MWInfUvPQK8Ib7jrnJm8f3A4yczEwISIiIqJ2IbuwFJ56ZwR76po0j0luUfW6E/qFo6jMiJ+OZDX52HsyzqKkohJ/b0Y3LgAI9aqeZLEtZ+ZiYEJERERE7UJOYRn83V3g46ptUmBi6sp1/4BO0DipsKYZ3bl+TWr++BIACPasbjFpy5m5GJgQERERUbuQXVgGf7fqwKSkotLmLll5RWXw0GkQ5KnD4JgA7EjJRVYTZ2HfmpQDPzcXXBHs0ZyiX5jLhF25iIiIiIguX6UVlSgsNSLAwwXeBi0A4IyNs7/nFZXDz80FADC2VyiqBPhm30mbj51VUIqErEL8PdoPTk62pwk2F1LTlYtjTIiIiIiILmOmge/+bi7wdasOTGwdAJ93vkzZZkhsALwMzli794TNqXsvthsXABi0GngZnHGqiS01lxMGJkRERETU5plSBVu0mNgQmFRWCc6cL4eva3WLiYtGjdu6hyAluwgHTxTYdOytyTlQqYCBUX7NLH21YE89W0yIiIiIiC5nSouJuwt8XKvT9doSmOQXl6NKAJ+aFhMAGHN1GABg7d7GB8EbK6uwPTkXfwv1hG9Nd7DmCvXS4fS5UlRWtc1JFhmYEBEREVGbl1NY3QUqwF0Hn5rWD1sCE1NGLj/XC4HJ38I8ERXghv8eOIUyY8MD6A+cKEBBScVFdeMyCfbUo6JSkFtk+6z1lxMGJkRERETU5llrMTlrw+B3UxBg3tqhUqkwtlcY8osrsDkhu8Htt5rGl8RcfGAS0sYnWWzxwCQ5ORnXXnstoqOj0bdvXxw5cqTOOqtWrULPnj3RrVs3XHXVVfjggw8sln/yySfo0qULIiMjMXnyZBiNxpYuNhERERG1ITlFFwa/N2WMSV7N5Iq+Zl25AGBUz1A4qYA1fzacnWtrUg7cdRp0D/NqTrEtmDJzHT/LwKRZpkyZgsmTJyMpKQnPPvssHnzwwTrrhIWF4YcffsDhw4exfft2zJ07Fzt27AAApKen4+WXX8b27duRkpKCrKwsfPLJJy1dbCIiIiJqQ7LPlcFZrYKXwRleBi1UKlsDk5oWE1fL8SGBHjoM7OKPLYnZ9XatOnu+HAdP5OO6Ln7QqC/+sTsqwA0AkHy68KL35YhaNDDJzs7G3r17cc899wAAxowZg/T0dGRkZFisN2DAAAQFBQEAPD09ERsbi/T0dADAmjVrMGrUKAQGBkKlUuGRRx7BypUrW7LYRERERNTG5BRVT66oUqmgdlLBS+/ctDEmtVpMAGDM1aEwVgm+23/K6ra/JGRD5OLSBJuLCnCD2kmFhKy2GZhoWnLnx48fR0hICDSa6sOoVCqEh4fj2LFj6Nixo9Vtjhw5gt9//x0fffQRAODYsWOIiIhQlnfs2BHHjh1ryWITERERURuTfa4MgZ465W9vV62NY0xMXbnqZtS68coguLtosPbPE7jhikD8daoAh0+eq/7vqXPKuJa/X6LAxEWjRic/VyQyMGkelcpydsuGJqI5ceIEbr/9dixcuBAhISFW99HQ9nPmzMGcOXOUv4uKippTZCIiIiJqQ6qqqjNZdQv1VF7zMWiRkXe+0W3zisrgpAK89M51lumc1Rjxt2B8ufs4rntrs/K6Vu2EmCB3DIsNwN+j/RHsqb80bwRATJA71h3MxPkyI1xdWvxRvlW16Lvp0KEDTpw4AaPRCI1GAxHB8ePHER4eXmfdU6dO4frrr8dLL72EO++8U3k9PDzcouvX0aNHrW4PANOnT8f06dOVv8PCwi7dmyEiIiKiy9LZ4nIYqwQBHhdaPXxctdh3PB9VVQInJ1W92+adL4ePq0u960z+e2dkF5Yh3MeAK0I80C2kOpWwVtMyIya61gQmSacL0TPcu0WOYS8tOsYkICAAPXv2xGeffQYAWLt2LTp27FinG1dmZiaGDRuG5557DnFxcRbLxowZg2+++QanT5+GiGDhwoW46667WrLYRERERNSGmGfkMvFx1aKySlBY2nC217yiMqvjS0w6+7vh00l9MOu2KzGudwdcEeLRYkEJAMQEeQBAm+zO1eJZuRYtWoRFixYhOjoab7zxhpJR65ZbbsGePXsAAP/85z9x7NgxzJ07Fz169ECPHj2wZMkSAEDnzp3xr3/9CwMGDEBkZCQCAgKsZvYiIiIiIrLGfA4TE++aCRPzzjc8WWFeUXmdVMH2FBvkDgBtcgB8i3dMi4mJwe+//17n9fXr1yv/v3jxYixevLjefTz88MN4+OGHW6R8RERERNS2ZZ+rDj4CzAIT35rApKEB8GXGShSWGeukCranUC89XLVqtpgQEREREV1ulK5c5i0myiSLFfVuZ0on7EgtJk5OKkQHuSMh61yDSaEuRwxMiIiIiKhNU1pMPC6kC/ZxNQUm9XflMs367mclVbA9xQa542xxhdJFra1gYEJEREREbZqpxcR8EPuFwKT+FpNcZdZ3x2kxAYCYwLY5zoSBCRERERG1aTmFpfDUO8NFo1Ze87FhjEleA5Mr2lNbzczFwISIiIiI2rTswjKLge+AWVauogYCk5puXo40xgRou5m5GJgQERERUZuWU1hmMfAdAFy1amg1Tja1mPg5UFYuoDqoCvRwQeLpc/YuyiXFwISIiIiI2qzSikoUlhrrtJioVCr4GLRK5i1rcoscLyuXSUyQB5JPF6Gyqu1k5mJgQkRERERtlrXJFU28XRsOTPLOl0Hn7ASDVl3vOvYSG+SOMmMVMvLO27solwwDEyIiIiJqs7ILSwEAAe66Ost8XbU421BgUlQOX1cXqFSqFitfcymZuTLbzjgTBiZERERE1GY11mJSWGZEubHK6rZ5RWUWKYYdSUzNAPjErLYzzoSBCRERERG1WQ0FJj4GZwDWUwaLCHLPlztcqmCTqAA3qJ1UbSozFwMTIiIiImqzsmsCk9qD3wHApybblrVxJkU1LSmONrmiic5ZjU5+rkg8zcCEiIiIiMjhNdhi4lrTYmIlMHHUyRXNxQS549iZYhSXG+1dlEuCgQkRERERtVnZhWXQqp3gqXeus0yZZNFaYFIzuaKjjjEBgNhAd4gASaeL7F2US4KBCRERERE5rJP5JSgqa36LgGlyRWuZtXxqAhNrY0wceQ4Tk7Y2AJ6BCRERERE5rNvnbcf4Rb+jotJ65qzGWJv13cQUmFgbY6J05XKwWd/NxQZ5AECbGQDPwISIiIiIHFJpRSVyi8rx16lzmL85pcnbV1UJcosaCEwMDQUm1V25HLnFJMxbD4NWjUQGJkRERERELce8i9W8TSk4fLKgydsbq6TewMS7oRaTmtf8HHjwu5OTCtGB7kjIKoSI2Ls4F42BCRERERE5pPziCgDADVcEAgCeXn2g3skQrWkoVTAAOKud4K7T1DPGpHpbb4PjtpgAQGyQO86cL0dOTXkvZwxMiIiIiMghmQKTAVF+eHxoFBKyCvHBpmSbt28oVbCJj6tWGU9iLq+oHB46DbQax35cjlUGwF/+3bkc+0wTERERUbtVUFIdMHgZnDF1SBSuCPbAh1tScfBEvk3bX2gx0dW7jo+r1mqLSd75MofuxmUSUzMAnoEJEREREVELMbWYeOqd4ax2wuxx3eGkAv7x1QGUGSsb3d6mFhODFmfPV9QZo5FXVO7QA99NTC0mbSEzFwMTIiIiInJI+SXVgYlXzTiPrsEeeHJYFyRnF+G9nxvv0mVLYOLtqkV5ZZXFXCmVVYIzxeUOnSrYxNtViwB3F7aYEBERERG1FFOLiZfZrO2PDIrEVaGeWLQ1FfuOnW1w++zCUgANz97ua5pk8XyF2XHLIeLYqYLNxQS5I+l0ISqrLu/MXAxMiIiIiMghmY8xMdHUdOnSODnh6dUHUFpRf5eunMIyeBmc4aJR17uOkjLYbJyJKVWw72UwxgSo7s5VZqzC0bzz9i7KRWFgQkREREQOKb+4AioV4K5ztng9OtAd04ZHIzXnPD7dkV7v9jmFZfWmCja5MMnihXS7plTBDbW0OJK2MgCegQkREREROaT84gp46JyhdlLVWfbQdZ3g7+6Cz/84Vm8XppzC+md9N/FRJlm80JXLlD74chhjAlwYAB/PwISIiIiI6NLLL6mAt8HZ6jJntRPu6tMBJ/NL8GtSTp3lJeWVKCwzNpgqGLjQleus2ezveTUtJpfLGJOoADeonVRIzDpn76JcFAYmREREROSQ8ovL4dnAzOt39Q2Hkwr4fOfROstsycgFXGgxyTtfd4zJ5dKVS+esRkdfA7tyERERERG1hPziCouMXLWFeukxJCYAmxKycTK/xGJZTlF1Ri7/Rgaw+1hpMcm9zLpyAUBskAeOninGmfN1J4u8XDAwISIiIiKHU1pRiZKKSouMXNZM7B+OKgFW7Tpm8Xr2uZpZ3z0aDi48dBqonVSWWbmKyqB2UsGzgaDI0dxwZSBEgH9+d9jeRWk2BiZERERE5HDOldSdw8SaQdEBCPXS48vdx1FRWaW8nlMzTqSxFhOVSgVvg9aipSHvfDl8XLVwsjLo3lHd1j0EN1wRiP8dzMR3+0/auzjNwsCEiIiIiByOadb3hsaYAIDaSYW7+3ZAdmEZfok/rbxua4sJAPi4OtcZ/G6aePFyoVKp8Proq+DnpsXL3x5GZkFJ4xs5GAYmRERERORwrM36Xp9xvTtA46TC5zsvdOdSBr+7NZyVC6geZ2LZlascfpfJ5IrmfN1c8Mbov+FcqRHPrjmIqstsJngGJkRERETkcPKL6876Xp8ADx1uuDIQ25JzkZFbPft5TlEZtBoneOg1jW7v46pFfnEFjJVVKK2oTjN8uaQKru36KwIxvncHbEvOxYo/6mYrc2QMTIiIiIjI4Zi6ctkSmADAxH4RAICVNYPgswtL4e/mApWq8XEi3jXdxfJLKpSxJpdTRq7aXr71CnTw0eP1H+KRmlNk7+LYjIEJERERETmcgpquXJ5621ourunsi05+rvhqz3GUGSttmvXdxNcsZbAy6/tl2mICAG4uGsy+swfKjFWYvmq/RVIAR8bAhIiIiIgcTn6J7V25AMDJSYUJfcNxtrgC6w5mIreoHAE2BibeZpMs5p6vHptyuUyuWJ++nXww+e+dceBEAeZvTrF3cWzCwISIiIiIHI5p8Lt3I1m5zI3pFQatxgkfbklFZZXY3GLiY63F5DLuymUyfXg0YoPc8cGmFBw4nm/v4jSKgQkRERERORxTYOKha3zwuomPqxYjrgpGSnb1uIoA98Yzcpm2A4AzxeXIq5n/5HLuymXiolHj3fE9oFapMO2r/SitqLR3kRpk+5UmIiIiImol+SXlcNdpoFE37Xf0if3C8c2+6gkGbW0xMbXKnCkqR2GZEQAuy3TB1nQN9sDzN8dCo1bBRePYbRIMTIiIiIjI4eQXV9g8vsRcrwhvxAa5IyGrsMlduc4Ul6OgJhtYW2gxMXlgYCd7F8Emjh02EREREVG7lF9cAS8bM3KZU6lUmDKoM7RqJ8QGudu0Te0xJnpnNQxa/n7f2njGiYiIiMjhFJRUoLO/a7O2HdUzDCOuCoHWxq5LOmc1DFo18s6X42xxeZtqLbmcsMWEiIiIiBxKRWUVisqM8NQ3vSuXia1BiYm3QYuzxdUtJr5tZHzJ5YaBCRERERE5lIImzvp+Kfi6aXGmqDow8XNli4k9MDAhIiIiIodiShXcnDEmzeVt0CLrXCnKK6vYlctOGJgQERERkUMpaOKs75eCj6sWVWL6f3blsgcGJkRERETkUEwtJhczxqSpfMy6b/mxxcQuGJgQERERkUMxBSamiQ9bg3lgwq5c9sHAhIiIiIgcytni1u/KZR4E+bIrl10wMCEiIiIih2KPrFxsMbE/BiZERERE5FAujDGxT1cuP85jYhcMTIiIiIjIoeSX2GPw+4VjtebYFrqAgQkREREROZT84nK4atVNnr39YphSBHvqnVv1uHQBzzoREREROZSCkgp4tXKrhafeGSoVx5fYEwMTIiIiInIo+cUVrdqNCwDUTiqEeOrRwdvQqselCzT2LgARERERkbn84nKEeetb/bjLH+wLg1bd6selagxMiIiIiMhhVFYJzpUaWzVVsEmkv1urH5MuYFcuIiIiInIY50paP1UwOQYGJkRERETkMEypgr3t0GJC9sXAhIiIiIgcxtnicgCtO+s7OQYGJkRERETkMApqZn33YleudoeBCRERERE5jPyS6hYTT7aYtDsMTIiIiIjIYeQrLSYMTNobBiZERERE5DCUwKSVZ34n+2NgQkREREQOo6DEFJiwxaS9YWBCRERERA4jvyYrlye7crU7DEyIiIiIyGHkl1RA5+wEnbPa3kWhVsbAhIiIiIgcRn5xBVMFt1MMTIiIiIjIYRSUVHB8STvFwISIiIiIHEZ+cTkDk3aKgQkREREROYSqKqluMWFXrnaJgQkREREROYTCUiOqhKmC2ysGJkRERETkEPJLalIFMzBplxiYEBEREZFDUGZ9Z1eudomBCRERERE5hHzO+t6uMTAhIiIiIodgmvXdi7O+t0sMTIiIiIjIIRTUtJhwjEn7xMCEiIiIiBwCx5i0bwxMiIiIiMghKIEJW0zaJQYmREREROQQTOmCGZi0TwxMiIiIiMgh5BdXQKtxgt5Zbe+ikB0wMCEiIiIih5BfXA4vvTNUKpW9i0J2wMCEiIiIiBxCfkkFu3G1YwxMiIiIiMghFBRXMCNX2wkF2gAAIABJREFUO8bAhIiIiIjsTkSQX1LBOUzaMQYmRERERGR3RWVGVFYJZ31vxxiYEBEREZHdcQ4TYmBCRERERHZXUGIKTDjGpL1iYEJEREREdmdqMfFkV652i4EJEREREdkdZ30nBiZEREREZHfKGBOmC263GJgQERERkd3lF7PFpL1jYEJEREREdsesXMTAhIiIiIjsLp9Zudo9BiZEREREZHf5xRXQOKngqlXbuyhkJwxMiIiIiMjuCkrK4WVwhkqlsndRyE4YmBARERGR3eUXV3AOk3auxQOT5ORkXHvttYiOjkbfvn1x5MiROuvs3r0b1157LQwGA8aOHWuxbOnSpfDy8kKPHj3Qo0cPDBkypKWLTEREREStLL+kguNL2rkWD0ymTJmCyZMnIykpCc8++ywefPDBOusEBwfjvffew7vvvmt1H9dffz3279+P/fv3Y/PmzS1dZCIiIiJqRSKCguIKeLHFpF1r0cAkOzsbe/fuxT333AMAGDNmDNLT05GRkWGxXlhYGPr27QsXF5eWLA4REREROaCSikqUV1bBk6mC27UWDUyOHz+OkJAQaDQaAIBKpUJ4eDiOHTvWpP1s3boVPXr0wIABA7BmzZqWKCoRERER2QlnfScA0LT0AWpnVhCRJm0/cuRIjBs3DgaDAfHx8bjhhhsQFhaG/v3711l3zpw5mDNnjvJ3UVFR8wpNRERERK2GkysS0MItJh06dMCJEydgNBoBVAclx48fR3h4uM378PPzg8FgAAB07doVt9xyC3bs2GF13enTp+PEiRPKPzc3t4t/E0RERETUovKLywEA3gxM2rUWDUwCAgLQs2dPfPbZZwCAtWvXomPHjujYsaPN+zh58qTy/6dPn8amTZvQs2fPS11UIiIiIrIT06zvnszK1a61eFauRYsWYdGiRYiOjsYbb7yBTz75BABwyy23YM+ePQCA1NRUhIWFYfr06Vi/fj3CwsLw4YcfAgDmz5+PK6+8Ej169MDw4cMxbdo0DB06tKWLTURERESt5MIYE7aYtGcqaeqgj8tIWFgYTpw4Ye9iEBEREVEDPtySgrc2JOK/jw/A38K87F0cakENPZ9z5nciIiIisqsCZuUiMDAhIiIiIjszdeXiPCbtGwMTIiIiIrKr/JJyOKkAd5cWn8mCHBgDEyIiIiKyq4KSCnjoneHkpGp8ZWqzGJgQERERkV0VlRnhrmNrSXvHwISIiIiI7Kqo1Ag3F44vae8YmBARERGRXRWVGTm+hBiYEBEREZF9FZYa4cauXO0eAxMiIiIisptyYxXKjFVwY4tJu8fAhIiIiIjs5nyZEQDYYkIMTIiIiIjIfgpLqwMTjjEhBiZEREREZDeFZdWzvrMrFzEwISIiIiK7KSplVy6qxsCEiIiIiOymyDTGhC0m7Z5NNeCXX37BL7/8ghMnTkCv16N79+64/fbbERoa2tLlIyIiIqI2zBSYcOZ3arDF5Msvv0RsbCxmz54NvV6P6667Dt26dcPhw4cxdOhQxMXFISsrq7XKSkRERERtjGnwO2d+pwZD0z179mDbtm3w9/e3uvzHH3/Etm3bcOedd7ZI4YiIiIiobStiumCq0WANeOeddxrc+MYbb7ykhSEiIiKi9kUZ/M4xJu2ezTUgKSlJGWPSrVs3uLu7t2S5iIiIiKgd4BgTMmmwBhQWFmLOnDn4+OOP4eLigsDAQJSWliItLQ39+/fHM888g6FDh7ZWWYmIiIiojSlkiwnVaLAGDBkyBPfccw92796NoKAg5fWqqips27YNCxcuREpKCiZPntziBSUiIiKitqeorAJOKsCgVdu7KGRnDQYmO3bsgIuLS53XnZycMGjQIAwaNAhlZWUtVjgiIiIiatuKyoxwc9FApVLZuyhkZw2mCzYFJeXl5cpraWlp+N///ofKykqLdYiIiIiImqqo1Ah3HVMFk40zvw8YMACFhYXIy8vDddddh9dffx1Tp05t6bIRERERURtXWNNiQmRTYGI0GuHu7o5169YhLi4OO3bswG+//dbSZSMiIiKiNq6o1Mg5TAiAjYGJaRzJli1blCxc/8/efcfXWdb/H3+flb1X0zRJs7o3HUAHZRQKFQGBlooiZQjItyr0KzhwQkUBrX5F+VELBRQpYFFQKEtESrF0793s1WaPk3nG/fsjTWg6kpOSk5OcvJ6PRx7JOfd9n3wO3JTz7nV9rsts9uhSAAAA4KzsjJjgBI/ugksvvVRjx46V0+nUypUrVV1dLauVGwgAAADnzuU21NjqYsQEkjwMJk8++aR27dqljIwM2Ww2uVwurVq1ytu1AQAAwI91bK7IiAnUTTBpaGhQaGioTCaTJk+e3PF8XFyc4uLiOp0DAAAA9ER9s0MSmyuiTZeNInPmzNHy5cuVm5vb6fnW1la9/fbbuuaaa/TKK694tUAAAAD4p/YRE6ZyQfJgg8Xf//73uuKKK1RfX6+hQ4eqqalJx48f17x58/TDH/5QM2bM6KtaAQAA4EfszSeCCSMmUDfBJDg4WA888IAeeOABFRUVqaioSCEhIRo1ahQbKwIAAOBzqW/vMWHEBPKw+V2SkpOTlZyc7M1aAAAAMIh8NmLCzu/wcB8TAAAAoLfRY4KTEUwAAADgE/SY4GQEEwAAAPgEPSY4mcd3QWlpqXJzc+V0Ojueu+iii7xSFAAAAPwfIyY4mUd3wc9//nM98cQTysjIkMVikSSZTCZt3rzZq8UBAADAf9lbTmywyIgJ5GEwWb16tY4ePdqx2zsAAADweXU0vwcQTOBhj0liYiKhBAAAAL2qvtmpsECrzGaTr0tBP+BRPJ0/f77+93//V1/5ylcUFBTU8fzYsWO9VhgAAAD8m73FSX8JOnh0Jzz33HOSpL/97W8dz5lMJuXk5HinKgAAAPg9e7OT/hJ08OhOyM3N9XYdAAAAGGTsLU4NiQjq/kQMCh5H1K1bt+qDDz6QyWTSZZddpqlTp3qzLgAAAPg5e7NTWQmMmKCNR83vq1at0vXXX6/S0lKVlJTo+uuv1zPPPOPt2gAAAOCn3G5D9lZ6TPAZj+6EJ598Utu2bVN8fLwk6aGHHtJll12mO++806vFAQAAwD81tDplGGyuiM94NGIiqSOUtP9sMrGsGwAAAM5Nxx4mNL/jBI+CSVZWlh566CGVlJSotLRUP/vZz5SZment2gAAAOCn7M1twSScEROc4FEwefrpp5Wdna2JEydq4sSJOnjwoJ5++mlv1wYAAAA/Vc+ICU7h0Z2QkJCgl19+2du1AAAAYJBoHzEJC7T5uBL0F10Gk08++USzZs3SunXrznh8wYIFXikKAAAA/o0eE5yqyzvh+eef16xZs/TEE0+cdsxkMhFMAAAAcE7oMcGpurwTVq1aJUn68MMP+6QYAAAADA70mOBUHjW/z5gxw6PnAAAAAE981mNCMEEbj4KJ0+ns9Njlcslut3ulIAAAAPg/e4tDEsEEn+kymDzxxBOKj4/X3r17lZCQ0PEVGRmpOXPm9FWNAAAA8DPtze/hTOXCCV3eCXfddZcWLlyob3zjG532LYmIiFB0dLTXiwMAAIB/qj8xlSuUEROc0OWdEBkZqcjISL399tt9VQ8AAAAGAXuLU8E2i2wWjzoLMAh4dCdkZ2fri1/8olJTUztN6QIAAADOhb3ZyYpc6MSju+HOO+/UPffco5ycHL311lt68sknlZaW5uXSAAAA4K/sLU72MEEnHo2Y1NbW6qabbpLZbNaECRO0cuVKvf/++96uDQAAAH6qnhETnMKjYGKz2SRJ4eHhys/PV0tLi/Lz871aGAAAAPyXvcXJUsHoxKO7Ye7cuaqqqtLSpUs1bdo0BQYGauHChd6uDQAAAH7IMAyCCU7T7d1gGIbuv/9+xcTE6Oabb9acOXNUW1ur8ePH90V9AAAA8DNNDpdcboOpXOjEo6lcV111VcfPKSkphBIAAACcM/uJPUxofsfJug0mJpNJmZmZqqys7It6AAAA4OfqT+z6zogJTubR3RAaGqopU6bo6quvVlhYWMfzjz/+uNcKAwAAgH9qHzEJC7T5uBL0Jx4Fk8zMTGVmZnq7FgAAAAwCdkZMcAYe3Q0/+clPvF0HAAAABol6ekxwBh7dDQ8//PAZn//xj3/cq8UAAADA/3WMmBBMcBKP7ob6+vqOn5ubm7Vu3TpdcMEFXisKAAAA/sve7JDEVC505tHd8MQTT3R6/NOf/lRf//rXvVIQAAAA/BsjJjgTj/YxOVVsbKyys7N7uxYAAAAMAu3LBYczYoKTeHQ3PPXUUx0/u1wubdq0SXFxcV4rCgAAAP7rs+WCCSb4jEd3w5YtWz67wGrV+PHj9eSTT3qtKAAAAPgvlgvGmXh0Nzz33HPergMAAACDhL3ZqQCrWYFWi69LQT/SbTDJz8/XU089pX379kmSxo8fr3vvvVepqaleLw4AAAD+p77FyR4mOE2Xze8HDhzQeeedp6KiIs2bN0+XXXaZCgoKNGXKFB08eLCvagQAAIAfsTc7mcaF03R5RyxfvlyPPfaY7rzzzk7PP/PMM3r44Yf10ksvebU4AAAA+B97i5MVuXCaLkdMtm3bdlookaQ77rhD27dv91pRAAAA8F/1zQ5W5MJpugwmQUFBZ3zeZDIpMDDQKwUBAADAfxmGwYgJzqjbO6KpqUmGYZz2vMlk8kpBAAAA8F8tTrccLoMRE5ymyzti9+7dCgsL6xRMTCaTDMMgmAAAAKDH2MMEZ9PlHeF2u/uqDgAAAAwCn+36bvNxJehvuuwxAQAAAHpT+4gJPSY4FcEEAAAAfaa+Y8SEYILOCCYAAADoMx09JgQTnIJgAgAAgD5jb3FIovkdp/MomNTV1em+++7TtddeK0nav3+/1qxZ49XCAAAA4H/am9/DGTHBKTwKJvfcc4/i4uKUnZ0tSUpPT9djjz3m1cIAAADgf+pZLhhn4VEwOXjwoH74wx/KZmtb1i04OPiMmy4CAAAAXbHT/I6z8CiYBAQEdHp8tt3gAQAAgK6wwSLOxqNgcskll+jRRx9VS0uL/vOf/+imm27Sdddd5+3aAAAA4Gc+6zFhg0V05lEweeSRR2QymRQeHq4HH3xQM2bM0I9//GNv1wYAAAA/U9/ilMVsUpCNxWHRmUdjaFarVd///vf1/e9/39v1AAAAwI/Zm50KD7LKZDL5uhT0Mx4FkwcffPC05yIjI3XhhRfq0ksv7fWiAAAA4J/sLU4a33FGHo2hHTt2TGvXrpXT6ZTT6dRrr72mw4cP6/7779fPf/5zb9cIAAAAP0Ewwdl4FExKSkq0fft2rVixQitWrNC2bdtUWVmpDRs26MUXX/R2jQAAAPAT9c0OhbMiF87A42ASFRXV8TgqKkp5eXkKDw9XUFCQ14oDAACAf6lvZsQEZ+ZRMBk7dqzuuusubdy4UZ9++qnuuecejRo1Si0tLbJYLF1ee+TIEc2cOVMjR47UjBkztH///tPO2bJli2bOnKmQkBDdeOONpx1fvny5MjMzlZmZqR/96EcevjUAAAD0J61Ot1qcboUFsVQwTudRMFm9erUiIiK0dOlS3XvvvQoNDdXq1atlsVj09ttvd3nt3XffrbvuukuHDx/Wgw8+qDvuuOO0c4YOHarf/va3+s1vfnPasfXr12vNmjXavXu39u/fr7ffflvvvvuuh28PAAAA/UVDC7u+4+w8uisiIiL0q1/96ozH4uPjz3pdWVmZtm/frvfee0+SdMMNN2jp0qXKy8tTWlpax3nJyclKTk4+42jKK6+8oiVLlig0NFSSdPvtt2vNmjWaP3++J6UDAACgn2jf9Z0eE5yJx3fF3/72N+3cuVPNzc0dzz3++ONdXlNYWKikpCRZrW2/xmQyKTU1VQUFBZ2CSVcKCgo0d+7cjsdpaWlau3atp2UDAACgn6hvZsQEZ+fRVK777rtPzz33nJ555hm5XC69/PLLqqys9OgXnLp5jmEYPS7y5Nfo6voVK1Z0jL4kJyfLbrf3+HcBAADAO+xM5UIXPAomH3zwgd544w3Fx8fr17/+tbZs2aKysrJur0tJSVFRUZGczrab0DAMFRYWKjU11eMCU1NTlZeX1/E4Pz//rNcvW7ZMRUVFHV9hYWEe/x4AAAB4l73FIUkKYyoXzsCjYBIUFCSz2SyTySSHw6EhQ4aouLi42+sSEhI0ZcqUjr1OXnvtNaWlpXk8jUuSFi5cqBdeeEENDQ1qaWnR6tWrtXjxYo+vBwAAQP/QPpUrnBETnIFHd0V4eLgaGxs1e/Zs3XrrrUpMTJTN5tkybytXrtSSJUv06KOPKiIiQi+88IIkacGCBXr44Yc1bdo0ZWdna+7cuWpsbFRzc7OSk5P1gx/8QPfee68uvvhiLVq0SBMmTJAkLV68WFdeeeU5vl0AAAD4SsdULkZMcAYmw4Omj+PHjys6Oloul0srVqxQdXW1vvWtb/VoSpYvJCcnq6ioyNdlAAAAQNLKj7L1i7cP6u/3ztSU1GhflwMf6Orzebdx1eVy6Tvf+Y7+/Oc/S5Ieeuih3q0OAAAAgwLLBaMr3faYWCwWj/pJAAAAgK58tlwwO7/jdB7F1Xnz5ukb3/iGbrvttk4rXY0dO9ZrhQEAAMC/0GOCrnh0V6xatUqS9M4773Q8ZzKZlJOT452qAAAA4HfszU6ZTFKIzeLrUtAPeRRMcnNzvV0HAAAA/Jy9xamwAKvMZlP3J2PQ8WgfE0l644039Nhjj0mSSkpKtGfPHq8VBQAAAP9T3+Kk8R1n5VEw+elPf6qnn35azz77rKS2aVz33HOPVwsDAACAf6lvdtBfgrPyKJi8/vrrevPNNxUaGipJGjp0qOrr671aGAAAAPyLvdmpMHZ9x1l4FEyCgoJksdCkBAAAgHNnb3EqLIilgnFmHkXW4cOHa8OGDTKZTHK73Xr00Uc1YcIEb9cGAAAAP+FyG2psdSmcEROchUd3xu9+9zvdeuut2rt3r0JCQjRnzhz95S9/8XZtAAAA8BMde5gQTHAWHt0ZQ4YM0TvvvKPGxka53e5OmywCAAAA3WFzRXTHox6TG2+8UevWrVNQUBChBAAAAD1mb2bEBF3zKJhcffXVevzxx5WSkqLvfe97OnjwoLfrAgAAgB+xtzgkiX1McFYeBZMlS5boP//5j9avX6+AgABdddVVmjVrlrdrAwAAgJ+oZ8QE3fB453epbXWuSZMmaezYsTp06JC3agIAAICfoccE3fEomOzYsUPf/OY3NWzYMD377LO67bbbVFJS4u3aAAAA4CfoMUF3PLozFi9erNtuu007duxQUlKSt2sCAACAn2kfMaHHBGfj0Z1x6rQtl8ulf/7zn7ruuuu8UhQAAAD8S1VDqyQpgp3fcRY96jE5dOiQvvvd72rYsGF65JFHvFUTAAAA/ExuRYPMJiklJsTXpaCf6nbEpLGxUa+++qqeeeYZ5eTkqKmpSRs2bNC4ceP6oj4AAAD4gexyu1JiQhRks/i6FPRTXY6Y3HXXXUpJSdHrr7+uBx98UAUFBYqKiiKUAAAAwGNOl1t5FY3KjGejbpxdlyMma9as0dSpU3X33XfryiuvlMlkkslk6qvaAAAA4AcKq5vU6nIrK4FggrPrcsSktLRUX/3qV/Xwww8rNTVVDz30kBwOR1/VBgAAAD+QXWaXJGXGh/q4EvRnXQaTsLAw3Xnnndq4caPeeecdNTc3q7W1VTNnztRTTz3VVzUCAABgAMsubw8mjJjg7DxelWvcuHH69a9/reLiYi1btkxvvvmmN+sCAACAnzhaRjBB93q0XLAkWa1W3XjjjVq3bp036gEAAICfyS63KzY0QNGhAb4uBf1Yj4MJAAAA4CnDMJRd3sBoCbpFMAEAAIDXVNhbVdvkUGYCje/oGsEEAAAAXkPjOzxFMAEAAIDXdAQT9jBBNwgmAAAA8JrssgZJUhYjJugGwQQAAABec7TcrkCrWcOign1dCvo5ggkAAAC8JrvMroz4MJnNJl+Xgn6OYAIAAACvaGp1qbimSZnxrMiF7hFMAAAA4BXtje9ZNL7DAwQTAAAAeAVLBaMnCCYAAADwiuzythW5CCbwBMEEAAAAXpFdZpfJJGXQYwIPEEwAAADgFdnldiVHByvIZvF1KRgACCYAAADodS63oZyKBqZxwWMEEwAAAPS64uomtTrdBBN4jGACAACAXne0vF4SSwXDcwQTAAAA9LrsMlbkQs8QTAAAANDrPtvDhBW54BmCCQAAADzmdhv69ss79Nq2oi7PO1pmV3SITbFhgX1UGQY6ggkAAAA8tquoRm/sLNGj6w6o2eE663nZ5XamcaFHCCYAAADw2Pv7j0uSKhta9Y9dJWc8p6qhVdWNDoIJeoRgAgAAAI+9v/+4YkMDFBpg0eoNuTIM47Rzjpa19ZewIhd6gmACAAAAj+RVNOhImV2Xjx2ihdNSdPBYvTbmVJ52XkfjewKN7/AcwQQAAAAe+deBtmlc88YM0W2z0mQySas35J52XnZZ+4pcjJjAcwQTAAAAeOT9/ccVZDNr9og4DY8N1bwxQ/TBwTLlVjR0Oi+73K4Aq1nJ0SE+qhQDEcEEAAAA3apuaNWWvCrNGRGvIJtFknT7rHQZhvTCf/M6nXu03K6MuFBZzCYfVIqBimACAACAbn14qExuQ7p87JCO5y7IiNHYoRF6dWuhapsckqRmh0tF1U1M40KPEUwAAADQrff3H5fJJF06OqHjOZPJpNtnp6ux1aVXtxRKknIrGmQY7PiOniOYAAAA+DGHy63XdxSrqfXsmyF2p9nh0keHyzU1NVpxp+zk/sVJQxUXFqjn/5snp8vdsVRwJksFo4cIJgAAAH7srd2luu+Vnfrua7vPuOeIJzbmVKqx1dVpGle7QKtFt1wwXMU1TXpv//HPlgpmKhd6iGACAADgxzbltu0z8o9dJXppc8E5vUb7bu/zzhBMJOkrF6QqwGLW6g25yi5vW6Erg6lc6CGCCQAAgB/bnFulxIggpcQE62f/3K+9xbU9ut7tNvTBgePKiA896yhIXFigrp2cpK351froUJmGRQUrJMDaG+VjECGYAAAA+KlKe4uyyxt0YWasfv/l82QYhpa+tF31zQ6PX2NPca2O17Xo8jFnHi1pd/vsdElSXbOT/hKcE4IJAACAn9qSVy1Jmp4Wo0kpUXpowRjlVTbqe6/t8bjfpH239zP1l5xszNAIzcyMlcSKXDg3BBMAAAA/tSWvSpI0Iz1aknTrzDQtmJCot/aU6s+f5nv0Gu/vP67Y0ABNSY3u9ty7LsqQJE1KjjrHijGYEUwAAAD81Ja8KkWH2Dp6Q0wmk355w0QNjw3R8jcPaE9R1/0mhVWNOnisXpeOTvBoF/eLRyXoP9+5WNdMSuqV+jG4EEwAAAD8UEOLU/tK6jQtLUYm02ehIiLIpj/cfJ4k6d6XtnXs2H4m3a3GdSZpcaEyexBigFMRTAAAAPzQjoIaudyGZqTFnHZs/LBI/eiLY1VY1aRlr+xUhb3ljK/x/v7jCrSaNWdEnLfLBQgmAAAA/mjzif6S6emnBxNJ+ur5qbpmUpI+OFimC3/xgf7nL9u14UiF3O62pvjaRoc251VpdlYcS/+iT3CXAQAA+KEtuVUKtlk0LinijMdNJpNWLJqky8cO0ZrNBXprT6ne2lOq1JgQ3TQ9RYFWs1xuo9vVuIDeQjABAADwM61Ot3YUVmvq8GjZLGefIGO1mPXFSUn64qQk5VU06OUthVq7rVBPvHtIkmQySZd1s38J0FsIJgAAAH5mb0mtmh1uTRt+5mlcZ5IWF6rvXTVayy4fqQ8OHNerWwuVGhOi+PBAL1YKfIZgAgAA4Ge2duxf4nkwaRdgNeuqCUN11YShvV0W0CWa3wEA8JLGVqeO1Tb7ugwMQptzq2U1mzQllY0OMXAQTAAA8JLlbx3Q5b/5SM0Ol69LwSDidhvaml+lccMiWU0LAwrBBAAAL/k0p1L1zU4dOW73dSkYRI6W21XT6NCMtGhflwL0CMEEAAAvqG92KLeiQZJ08Fidj6vBYLI5t62/ZNoZNlYE+jOCCQAAXrCvpE5G2z51OnSs3rfFYFBpb3yfTjDBAEMwAQDAC/YW13b8fOg4wQR9Z0tetbISwhQTGuDrUoAeIZgAAOAFe04Ek7TYEEZM0GeKa5pUXNPEaAkGJIIJAABesKe4VsNjQzQ9LUZl9S2qbmj1dUkYBLbktu9fQuM7Bh6CCQAAvcze4lRuRYPGD4vUqMRwSdJBRk3QBzaf6C/pyY7vQH9BMAEAoJftK66VYUgThkVqdGKEJOkQK3OhD2zJrdLQyCAlRwf7uhSgxwgmAAD0svb+kgknjZjQAA9vq25o1ZEyu6anxchkMvm6HKDH2A4UAIBe1r4i1/ikSEUEWxUTGsBULnjd1vxqSdL0dKZxYWBixAQAgF62u7hWqTEhigyxyWQyadSQcB0+Vi+32/B1afBjW070l8xgRS4MUAQTAAB6UXvj+4RhkR3PjUoMV0OrS8U1TT6sDP5uc26VIoNtGpEQ5utSgHNCMAEAoBe1N76PPymYjGZlLnjZrsIa7S2u1bTh0TKb6S/BwEQwAQCgF7U3vk9M7jxiIrEyF7zjnb2luumPG2Uxm3T77HRflwOcM5rfAQDoRSc3vrcbOYQRE/Q+wzD0x/U5+sXbBxUXFqBVX5umKalsrIiBi2ACAEAv2nNS43u70ECrUmNCdIhggl7icLn14zf2as3mQo0cEqZnb52ulJgQX5cFfC5M5QIAoJfYW5zKOaXxvd2oxHDlVDSoxenyQWXwJ7VNDt323Bat2VyoOSPitPYbMwkl8AsEEwAAesn+krrTGt/bjU4Ml8ttKKe8wQeVwR84XW7tL6nTDf/vv9pwtEJfOT9Vzy2ZroggW/cXAwMAU7kAAOglu4tqJOmsIyaSdOhYvcYMjejTujCwNLY6tbOwRrkVDcotb1BeZYNyKhrKNXa8AAAgAElEQVRUWNUoh8uQyST98AtjdMfsdHZ4h18hmAAA0Es6Gt+HnR48WDJ48DEMQ8fqmhUTGqBAq6Xbc/cU1+rlLYX6x84S2VucHcesZpNSY0M0d2S80mJDddmYIbowM9bb5QN9jmACAEAvaW98jwoJOO3Y8NhQBVjMLBnsx2qbHNpVWKOdJ31VNbQqwGrW5OQoTU+P1rS0GE0dHt0x/aq20aHXdxbr5S2FOlDadm+MGRqh6yYnaWRiuDLiQjUsKlhWC7Pv4f8IJgAA9IL2xvcF44ee8bjNYlZmQhgrc/kZl9vQ//3rsN7cU9qpf8hmMWnM0AjNH5eooupGbc+v1ua8KknZMpmk0YkRSo4O1vrD5WpxuhUeaNVXzk/V4umpGj8sgilaGJQIJgAA9IKuGt/bjU4M1993FKu2yaHIYBqWB7oWp0v3v7JT6/YcU1JkkL44KUmTU6I0OSVK45IiFGT7bPqW0+XWwWP12pJXpa15bSHlQGmdZqTF6KbpKVowYaiCA7qe7gX4O4IJAAC9oH3H9zM1vrdrb4A/fLxe09Ni+qQueEdDi1N3/3mbNhyt0BcmDtWKRZO67COxWswaPyxS44dF6rZZ6TIMQw2tLoUF8lEMaMeERQAAekFXje/tRtEA7xeqGlp18zObtOFohW4+P1W/Wzyl2+b2U5lMJkIJcAr+iwAAoBfsKa5VSkzwGRvf243uWDKYBviBqqSmSbc8u0nZ5Q365qVZWnb5SPpBgF5CMAEA4HOytziVXW7XVeMTuzwvMSJIEUFWGuD7GcMwtL2gRn/emKeNOZUakRCu81KjNCU1WpNTohQd2hY2s8vtuuWZTSqpbdaPrh6rO2an+7ZwwM8QTAAA+Jw8aXyX2qbvjE6M0IFjdTIMg79p97Fmh0v/2FmiP32ap73FbaNYWQlh2ppfpQ1HKzrOS4sN0eSUKK0/UqHaJodWLJqk689L9lXZgN/yejA5cuSIbr31VlVUVCgqKkrPP/+8xo4de9p5y5cv13PPPSdJuvnmm/XII49Ikp5//nndd999SktLkyRFR0frww8/9HbZAAB4rL3xfeKwqG7PHZUYrs15VSqtbVZSVLC3S8Mp3G5DuZUNenlzgV7dWqTaJodCAiz6yvmp+tqFaRqVGC6Hy62DpfXaUVitHQU12lFQrdd3lijQatYfb5mqy8YM8fXbAPyS14PJ3XffrbvuuktLlizR2rVrdccdd2jjxo2dzlm/fr3WrFmj3bt3y2q1atasWZo9e7bmz58vSZo3b57Wrl3r7VIBADgnnjS+txvV0WdSTzDxksZWpw4eq1d+ZYOKqppUVN2koppGFVc3qaSmWa0utyQpIz5U988boeunJndseCi17TkzITlSE5Ij9bUL256ramiVxWximWfAi7waTMrKyrR9+3a99957kqQbbrhBS5cuVV5eXscIiCS98sorWrJkiUJDQyVJt99+u9asWdMRTAAA6M88aXxvd/LKXJeMTvD4dxiGob3Fdfo0p1KLZ6QoPIgPyJJU09iqfSV12ltcq30lddpXUqvciga5jc7nhQZYlBwdojkj4pQcHazLxyZqVlasx9PpYkK7/3cL4PPxajApLCxUUlKSrNa2X2MymZSamqqCgoJOwaSgoEBz587teJyWltZphOSjjz7S5MmTFRoaqvvvv1833njjGX/fihUrtGLFio7Hdru9l98RAACdNXjY+N5u5JCercxV2+jQG7uK9fLmQu0vbbvmk+wKPXvrdFnMg6tHpdLeoj3FtdpbXHvie52Ka5o6nZMaE6L54xI1LilCmfFhSokJUXJ0sCKDbfT0AP2c16dynfqHgGEY3Z538jlXX321Fi1apJCQEB04cEBXXHGFkpOTdcEFF5z2GsuWLdOyZcs6Hicn05gGAPCu/aWeNb63iwy2KSkySIeOn/0vzwzD0ObcKr28pVDr9pSqxelWeKBVXzk/VTVNDr21u1SPv3NQ318wprfeRr/kdht6b/9x/X1HkfYU1aqktrnjmNkkjUgI1/XnDdO4pEiNS4rQ2KSITlOyAAwsXg0mKSkpKioqktPplNVqlWEYKiwsVGpqaqfzUlNTlZeX1/E4Pz+/45y4uLiO58eMGaMFCxbok08+OWMwAQCgr63ZXCBJmpzSfeN7u1GJ4frkaKUcLrdsls57Ha8/XK6H39yvo2VtwWV6WrRump6qBRMSFRJgVYvTpdKaJq1cn6NRieF+uTqUy23orT2l+sO/j+rQ8XpZzCaNSAjTzKw4TTixe/rYoREKDujZpoYA+jevBpOEhARNmTJFL774opYsWaLXXntNaWlpnaZxSdLChQu1dOlS3XvvvbJarVq9erWWL18uSSouLtawYcMkScePH9e///1v3XTTTd4sGwAAj7yz95j+tr1YF4+K14UZsR5fNyoxQh8eKldeRYNGnJjaVVbXrEfeOqB/7ipRsM2iO2ena/GMFGUlhHe6NtBq0dO3TNW1v/9E3/vbHqXHhWpKanSvvi9fcbrcen1niZ768KhyKhoUEmDR3Rdl6M45GYoPD/R1eQC8zOtTuVauXKklS5bo0UcfVUREhF544QVJ0oIFC/Twww9r2rRpuvjii7Vo0SJNmDBBkrR48WJdeeWVkqQ//OEPeuONN2Sz2eR2u3X//ffr0ksv9XbZAAB0qay+WT/4+x5Fhdj0+A0Te9S/MPqkBviM+DC9tClfj79zSPUtTs0bM0Q/u3achnWxYldCeJD+eMs0LVz5X9395236x9LZSowM+tzv6VQ92WvleF2zPs2p1Kc5lapvdiojPkxZCWHKjA9VZnyYgmynj240O1wqq2vR8fpmHSit06qPc1RY1aTwQKuWXpKl22en03QODCIm42xNH34gOTlZRUVFvi4DAOBnDMPQnS9s1QcHy/SHm8/TFyYO7dH1B0rrdNX/fawvTBiqoupG7SqqVVJkkH56zThdMc6zJnpJ+ueuEn1zzQ5NTI7Uq3dfeMYP/+eivL5FT/77iF7dWqjokABlxIcqPS5U6XFhyohr+znIZtHmvKq2MJJdqZyKhrO+nskkDYsKVmZ8mNyG0RFGahodnc6LDLbpjtnpunVmGsvyAn6qq8/n7PwOAEAPvbKlUB8cLNN1k5N6HEokKTM+TFazSW/tKZXFbNJdF2Xo25eNUGhgz/63/MVJSTp0rF6///Covvvabv32psmfa+Wp+maHVn2cq2c+zlFjq0ujE8NltZi0s6BGnxytPOt1ydHBunFqsi7MiNUFmbGKCQlQToVd2eUNOlpmV3aZXdnldm3MqZTFZFJiZJBGDQlXYmSQhkQEKSE8UEMjgzV3VLzCevjPAID/4L9+AAB6oKCyUY+8uV9DI4P0s2vHn9NrBFjNumZSkkprm/Wjq8dqbFL3GzOezbLLR+rQ8Xq9sbNEoxLDde/FWT1+jRanS3/5tEC///CoqhpalRkfqgfmj9b8cUNkMplkGIbK61uUU9Gg3BNf9c0OnZcarQsyYpUSE3Laa7atlNV5pTK325DJdPqKnQAgMZULAACPudyGblq5UVvzq/WXO8/XrKy47i/qA/YWp2546r86dLxeP756rG6fne7RdYZh6B+7SvTEu4dUVN2kxIgg3X/5CN1wXrKsp6wWBgC9galcAAD0gj+uz9HW/GrdNiut34QSSQoLtOr526frq89s0sNv7ldNY6vuv3xklyMTzQ6Xfvj6Xq3dVqTIYJu+f9Vo3Tozrdf6VACgpwgmAAB4YF9JrVa8f0hZCWH67pWjfV3OaYZGBuuv98zUbc9t1u/+fVRVja362TXjz7g7fFF1o77x4nbtKa7VxaPi9ZtFkxXN6lcAfIxxWgAAutHU6tKyV3bJMKTfLJrcb0cVYkID9JevX6BZWbF68dMCffvlHWp1ujud88nRCl3z+0+0p7hW37o0S6tvnU4oAdAvEEwAAOhCi9Olu/68VYeO1+u+eSM0ITmy+4t8KCzQqtVLpuuq8Yl6c3ep7vzTVjW2OmUYhlZ+lK1bnt0kh9OtVV+bpmVXjJL5DCMqAOALNL8DAHAWTpdbS1/aoXf2HdOXZ6To0S9NGDArSrnchh76+x69vKVQ56VGaWhksN7aU6qshDCtvGWqMuPDfF0igEGI5ncAAHrI7Tb04Gu79c6+Y7pmUpKWXzdwQokkWcwm/eL6CYoKCdDTH2VLqtFV4xP1xMJJ7BUCoF/iTyYAAE5hGIZ++s99+tv2Ys0bk6BfL5p0xiby/s5kMul7V41WRnyoHC63bp6ROqDCFYDBhWACAMApnnj3kP60MV8zM2P1+5vPk22A7+mxaFqKr0sAgG4N7D9pAQDoZX/48Kie+k+2pqRGadXXpvXbFbgAwN8wYgIAGFRanC7tLa5Ts8OlZodLTQ6Xmh1uNTtcyq1o0LMbcjVmaISeXzJDofRiAECf4U9cAMCg0dDi1E1/3Ki9xXVnPScjPlR/vmOGIkNsfVgZAIBgAgAYFFxuQ99+eaf2FtfppmkpGp8cqWCbRUE2s4KsFgUHtP08dmikggOYvgUAfY1gAgAYFH6x7oD+deC4vjRlmH55w8Ba+hcABgOa3wEAfu8vm/L1zIZcTU+LJpQAQD9FMAEA+LWPj5Trx2/s0/DYEK28ZZoCrUzTAoD+iGACAPBbR47X694Xtys0wKJnb52umNAAX5cEADgLekwAAH6pwt6i257foiaHS3+6fYayEsJ8XRIAoAsEEwCAXzAMQ00Ol6obHapuaNWP39irouomPXbDBM3MivN1eQCAbhBMAAADSlOrSzsKqrUpt0o7CmtUVtesmkaHqhpb1ep0dzr37rkZuml6qo8qBQD0BMEEANCv1Tc7tCWvSptyq7Q5t0p7imrldBuSpCCbWYkRQUqMDNKYoeGKDglQVEiAokNsSosL1RcmDPVx9QAATxFMAMDPbc6t0vde261rJifprosyFBIwMP7ot7c4tWp9jlZ9nKPGVpckKSLIqotHxWtGeoxmpMdqXFKEbBbWcQEAf2AyDMPwdRHekpycrKKiIl+XAQA+U93Qqqv+72Mdq2uWJCVGBOmB+aP0pSnDZDb3zl4ehmGoxelWXZNDdc0O1TY5VdfkUE1Tq2oaHappdKi2qe3LJOni0Qm6bHSCQgPPHJAcLrfWbC7Q7z44ogp7qzLiQnXLhcN1fnqsRiWGy9JLdQMA+l5Xn88JJgDgpwzD0D0vbtO7+47rF9dPUKvTrd/867BqGh2amBypH35hrGakx/T4dfeV1GrFe4eVW9GgumaH6pqcanW5u7/wJIFWs+aOjNcXJg7VpaMTFB5kk2EYemtPqX717iHlVTYqPjxQ988bqUXTkmVlVAQA/ALBBAAGoZc2FegHf9+jqycO1ZNfniKTyaTaRod+9+8j+tPGPDlchq4an6jvXzVGqbEh3b5edUOrfv3+Ib20qUCSlJUQpshgmyKCbIoItikiyKqIYJvCg6yKCg5QZIhNUcG2E98DFBViU12zQ+/uPaZ1e45pU26l3IYUYDXrohHxKq9v1q6iWoUFWnXP3AzdPjt9wEw7AwB4hmACAIPM0bJ6Xf3kBsWGBmrdt+coMtjW6XhuRYN+se6A3tt/XGaTdH56rK6eNFRXjktUbFhgp3NdbkMvbcrXr947rNomh2akxegn14zVuKTIz1VjeX2L3t13TG/vLdXG7EpZzCbdckGall6axUaIAOCnCCYAMIi0OF267g//1aFjdXr17gs1Le3s07U2Zlfq+f/m6sND5Wp1umUxmzQzM1ZXTxyq+eMSdfi4XT/5xz4dKK3TkIhA/WDBGF0zKUkmU+/2eVQ3tMqQCCQA4OcIJgAwiDz8z/1a/Umu7ps3QvfNG+nRNfXNDv3rwHG9tbtUHx0ul8NlyGo2yek2FGAx64456Vp6SdZZG9YBAPBEV5/P+T8MAPiRDw+VafUnuZo2PFpLL8ny+LrwIJu+NCVZX5qSrNomh97bd0xv7z2m0ECrll0+UulxoV6sGgAAggkA+I3y+hY98NddCg+y6reLJ5/zSlaRwTYtnJaihdNSerlCAADOjmACAH7AMAw9sHaXKuyt+v3NU5Qc3f0qWwAA9CcsDA8AfuDPn+brP4fKdePUZF09McnX5QAA0GMEEwAY4LLL7Xp03QGlxATrp9eM83U5AACcE4IJAAxgDpdby17ZqRanWysWTVYYq2YBAAYoggkADGB/+PCodhXV6u6LMjW9i/1KAADo7wgmADBA7Sqs0ZP/PqrRieG6//IRvi4HAIDPhWACAANQU6tL97+yUxaTSb9dPFmBVouvSwIA4HNhMjKAfqGwqlEOl1vBARYF2ywKslkUaDXLZDL5urR+6ZdvH1BORYN+sGC0RidG+LocAAA+N4IJAJ9qaHHq4X/u1ytbC087ZjJJwTaLUmNCtOpr05QS0z/35jhW26xAq1nRoQG98noutyF7i1ORwbYzHl9/uFwvbMzXjPQY3TE7o1d+JwAAvkYwAeAzOwtrdN/LO5RX2ahZWbGanBKlpla3mhwuNTtcamp1qaHVqY+PVOjbL+/Qq3dfeM67mXuDy23o2Q05+tV7h2U1m3Tn7HR9/aIMhQedOVB0xzAMvb//uB5756Cyyxs0NDJI44dFasKwSE1IbvtuNZv0wNpdCgu06tcLJ8liZkQJAOAfTIZhGL4uwluSk5NVVFTk6zIAnMLlNvT//nNUv/nXEVnMJn3vytFaMjNN5rN8yP75W/u16uNcffPSLP3vFaP6uNozy61o0Hf+ukvb8quVFhsii9mk7PIGRYfY9D+XZOmrFwxXkM3zvo/tBdX6xboD2pJXrZAAiy4ZlaDscruOlNnlcn/2x3RogEUNrS49ceNELZyW4o23BgCA13T1+ZwREwB9qrCqUcte3aktedUaNSRc//flyd32SDwwf7Q+zanS7z88qllZcbogI7aPqj2d223oTxvz9Mt3DqrZ4daSmWn67pWjZbOY9Lcdxfrt+4e1/K0DenZDru6bN0I3nJfc5ShPbkWDnnj3oNbtOSaL2aSvnJ+qb88boYTwIElSs8OlA6V12lNcqz1FtdpbUqfJKVG6cWpyH71jAAD6BiMmAPqEy23o7zuK9bN/7FN9i1O3zWr7QO/pqEJuRYO+8LuPFRls07pvzem1fo6eKKxq1INrd2tjTqVSYoL1xI2TTgtJzQ6XXvw0X3/48KiqGx3KiA/VlJRoBdnMCrRaFGgzK+jE94KqRr26pVBOt6Erxg7Rg1eOVlZCWJ+/LwAA+kpXn88JJgC8qtnh0mvbi7RqfY7yKhsVHx6oXy2cpLkj43v8Wn/dWqgH1u7WFWOHaOUtU3t9xS6Hy62tedWqbmxVfbNDdU3Otu/NTtU1OfTuvmNqaHXpK+en6gcLxii0i13W65sdeubjXD27IVf2FudZz5uSGqUfLBjD5ogAgEGBYAKgz9U2OvTipnw990muKuytigy26WsXDtfts9LPebTDMAx96+Wd+ueuEi2/bry+esHwXqu3qLpR31yzQzsKas56TnJ0sH5x/QTNGeF5qHK7DTU7XWpxuE/7bjGbNC4pgiWRAQCDBj0mAPpMWV2z/rg+R2s2F6ih1aWkyCD96OqxWjw9pcsRBk+YTCb9/EvjtaOgWo+8uV8z0mM0ckj45675vX3H9MDa3aptcmjJzDSdNzxa4UFWRQTZFBFkVUSwTeFBVgXbLD0OEWazSSEBVoX0/cwzAAAGFEZMAPSa2iaHrn7yYxVWNWnUkHDdPTdDX5yUJFsvL/G7Lb9ai1Zu1IiEML3+P7N6tPrVyVqdbj32zkE9uyFX0SE2rVg0WZeMTujVWgEAwGcYMQHgdYZh6KG/71FhVZMeWjBGd85J99oUpanDo3XfZSP06/cP6+t/2qrM+M8axk/+lUmRwRo/LFLjh0WctrdIYVWjlq7ZoV2FNZo2PFq/+/IUJUUFe6VeAADQPYIJgF7x6tZCvbm7VPPHDfFqKGl37yVZ2ppfrY8Ol+vjIxXdnp8RF9qxSWFIgFW/fPuA6pqd+sbFmVp2+cheH9UBAAA9w1QuAJ/b0bJ6Xf3kBsWEBGjdt+coqo8aKgzDUFl9y0mPPzvmNgzlVTZob3GtdhfVam9xrfIqGzuOR4fYtOKmybpkFFO3AADoK0zlAuA1zQ6Xlr60Q61Ot/7vy1P6LJRIbc3wQyKCzno8KSpYMzPjOh7XNjm0r7hWuZUNumz0ECVGnv1aAADQtwgmAD6XX6w7oIPH6rXs8pH9fi+OyGCbZmbFaWZWXPcnAwCAPsWkagDn7L19x/TCxnxdkBGj/7kky9flAACAAYxgAuCclNY26cHXdisqxKbf3jRFFjObBAIAgHPHVC4APeZyG/r2yztV0+jQqq9No1cDAAB8bgQTAB5rcbr03r7j+vPGfG3Oq9KSmWm6fOwQX5cFAAD8AMEEQLdyyu16eUuh1m4rUlVDq2wWk66fMkzfu2q0r0sDAAB+gmAC4IzcbkNv7SnVS5sKtDGnUpKUFhuiuy/K0A1TkxUXFujjCgEAgD8hmAA4TW2TQ/e/slP/PlimAItZ10xK0pdnpOqCjBiv7+gOAAAGJ4IJgE4OH6/XXX/aqrzKRt1wXrIe+sIYxYT23aaJAABgcCKYAOiwbk+pvvPXXWp1uvXwteN0ywXDGSEBAAB9gmACQC63oSfePaSnP8pWXFiAnr9thmak9+9d3AEAgH8hmACDXE1jq765Zoc+PlKhySlRevqrU9mXBAAA9DmCCTAIGYahPcW1emt3qV7fWazjdS1aPD1FP7t2nAKtFl+XBwAABiGCCTBIGIah3UW1WrenVG/tKVVRdZMkaWhkkH5x/QR9eUaqjysEAACDGcEE8FOGYSi/slE7C2u0vaBa/z5Y1hFGkiKDdMfsdC2YMFRTUqJkNtPgDgAAfItgAviJumaHdhbUaGdhjXYUVGtnYY2qGx0dx4dFBevO2elaMHGoJicTRgAAQP9CMAEGqNLaJm3Jq9bWvCptyavWwWN1Moy2YwEWs8YmRejayVGakhqlKSnRSokJZulfAADQbxFMgAGguqFVB0rrtL+0TnuKa7U1r1rFNU0dx+PDA7Vg/FCdNzxa56VGaWxSBE3sAABgQCGYAP1IY6tTuRUNyq1o0MHSeu0vrdOB0jqV1jZ3Oi8rIUxfnpGiacNjND0thtEQAAAw4BFMAB9odri0Ja9KB0vrlVPRoNwKu/IqGnWsrnMAsVlMGpEQrpmZcRqbFKExQ8M1dmiEokICfFQ5AACAdxBMgD7gdhvaV1KnDUcrtOFoubbkVavV6e44Hh5oVVpcqGakxyg9LlTpcaEalRiuzPgwBVjNPqwcAACgbxBMgF7W0OJUQVWj8isblF/ZqN3Ftfrv0YqOFbICrWadnx6j2VlxmpwSpYz4MMWFBTAVCwAADGoEE+AcGYaho2V2bcqt0o6CGuVXNiivslEV9pZO55lM0rikCN00PVVzRsRp6vBoBdloTAcAADgZwQTwkNtt6OCxem3KrdTm3Cptzq1SZUNrx/GY0AClxoRodlasUmNDlRYbouGxIcqMD6MnBAAAoBsEE+AsWpwu7Smq1ea8Km09sV9IXbNTkmQ2SeOSInXdlGE6Pz1G09JiFBNK+AAAADhXBBPghJrGVu0oqNGWvCptyavSrqLajgZ1m8WkCcMiNSM9VudnxGjq8GhFBNl8XDEAAID/IJhgUDIMQ9nlDdqeX61t+dXaVlCto2X2juNhgVZdkBGrGWnRmp4Wo0kpUfSFAAAAeBHBBH7F5Ta0/ki51m4r0qfZlTKZJIvZJKvZfOK7SRazSeX2FtWcWCVLkpKjg3Xt5CSdlxqtqcOjNWZohCxmVskCAADoKwQT+IWccrv+uq1If9tepON1batiTUyOVJDVIqfbLZfbkNNtdHzPiAvtCCHnDY/WkIggH78DAACAwY1gggGrtLZJ/znUNjqyLb9akjQsKljfvmyEbpyarJSYEB9XCAAAAE8RTDBg1DY6tDGnUp8crdAn2RXKKW+QJAXZzPrSlGFaODVZF2TEyswULAAAgAGHYIJ+q7HVqa151dqYU6n/Hq3QnuJauY22Y0mRQbpxarJmZ8Xp0jEJrJAFAAAwwBFM0G80O1zall+tjdmV2phTqV2FNXKeSCKRwTbNH5eomVlxmp0Vp7TYEJlMjIwAAAD4C4IJfMLtNpRT0aDdRTXaXVSr3UU12ltcp1ZX274h4YFWzR0ZrwsyYnVhZiyrZAEAAPg5ggm8rrqhVTkVDcopt+tImb0jhNhbnB3nRAbbdGFmWwi5MCNW45IiZLWYfVg1AAAA+hLBBD1WWNWoFz/NV3Vjq2wWs2wWswKsZtksJtlOhInCqiblVNiVW9HQab8QSQoNsGjcsEhNSo7UxOQoTUyOVGoMU7MAAAAGM4IJPJZdbtdTH2br9Z3FcrV3oXchLixAIxLClB4XqvS4tu9ZCW0/My0LAAAAJyOYoFv7S+r0hw+Pat3eUhmGdGFGrJZemqWJyZFyuAw5XG61Ot1yuNwdmxgmRQUrMpiVsgAAAOAZggnOqLbRoe0F1Xrx03x9cLBMknTJqHgtvTRLU4fH+Lg6AAAA+BuCCeRyGzp8vF7bC6q1o6BGOwqqlX1i80KTSVowIVH3Xpyl8cMifVwpAAAA/BXBZJBxutzKLm/Q3uJa7S2p1b7iOu0rqVVDq6vjnJSYYF0zKUlTUqN00ch4ZcaH+bBiAAAADAYEEz/mchs6Ulav3YW12l3ctkTvgdI6tTjdHeeEB1o1ITlSU1KjNSUlSlNSoxUfHujDqgEAADAYEUz8hGEYKqxq0q6iGu0qbNu0cG9JrRpPGgmJCQ3Q+Sf2CBmfFKnxwyKUEh0iMytkAQAAwMcIJgNUeX2LdhfVaFdR7YkgUqPqk/YLCQ+0anJKlCalRHXsFzI0Moi9QgAAANAvEUz6oRanS/mVjaqob1G5vUUV9lZV2FtUUd+iCnuLDh+3q7imqeP8ADRFjS0AAAyuSURBVKtZ45IidG1ylCaltIWQ9NhQRkIAAAAwYBBM+gGny63dxbXamF2pjdmV2pJX1akP5GQBVrPSYkO0cGryidGQKI1KDFeA1dzHVQMAAAC9x+vB5MiRI7r11ltVUVGhqKgoPf/88xo7duxp5y1fvlzPPfecJOnmm2/WI4884tGxgcjpcmt/aZ025VRpY06lNudWyd7ilCQFWs2alhatySlRGhIRpLiwwBNfAYoLD1R4oJXpWAAAAPA7Xg8md999t+666y4tWbJEa9eu1R133KGNGzd2Omf9+vVas2aNdu/eLavVqlmzZmn27NmaP39+l8cGihanS7uLarU5t0qbcqu0La+qY3lem8WkySlRujAzThdmxGpKapSCbBYfVwwAAAD0La8Gk7KyMm3fvl3vvfeeJOmGG27Q0qVLlZeXp7S0tI7zXnnlFS1ZskShoaGSpNtvv11r1qzR/PnzuzzW3x0+Xq8fvr5XOwtr1HpialaA1azJKVE6Pz1G09NiNC0tWiEBzKgDAADA4ObVT8SFhYVKSkqS1dr2a0wmk1JTU1VQUNApmBQUFGju3Lkdj9PS0rR27dpuj51qxYoVWrFiRcdju93em2+nx6JCbNpXXKvz02N0fnqMZqTHamJyJCMiAAAAwCm8/lf1p/ZDGIbR7XmnntPVsZMtW7ZMy5Yt63icnJzco1p7W0J4kHb95ApZLTSmAwAAAF3x6ifmlJQUFRUVyelsa+w2DEOFhYVKTU3tdF5qaqry8vI6Hufn53ec09WxgYBQAgAAAHTPq5+aExISNGXKFL344ouSpNdee01paWmdpnFJ0sKFC/XCCy+ooaFBLS0tWr16tRYvXtztMQAAAAD+wet/nb9y5UqtXLlSI0eO1C9/+Us9++yzkqQFCxZo69atkqSLL75YixYt0oQJEzRmzBhdccUVuvLKK7s9BgAAAMA/mIyumjYGuOTkZBUVFfm6DAAAAADq+vM5DRAAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfI5gAgAAAMDnCCYAAAAAfM5kGIbh6yK8JTAwUPHx8b4uQ3a7XWFhYb4uA/0Q9wbOhnvj/7d3/zFV1X8cx5/Xi1F5E39Qbowfl1DWAuw6RdCgtLT4J0W2Fk0NtD8i02qWm3NTKIv+wNlSc7e/HM6NLVaDkTVMDVzLEJrXRKcDLr9uDDTcSiQIvJ/+cN1vfgW+Tb2d++2+Hn/dez7nnvPm8N77c96ccy4yHuWGTET5IeMJldy4fPkyw8PDY479qxuTUBEbG4vP57M6DAlByg0Zj3JDxqPckIkoP2Q8/w+5oVu5RERERETEcmpMRERERETEcvaSkpISq4MIB4sWLbI6BAlRyg0Zj3JDxqPckIkoP2Q8oZ4besZEREREREQsp1u5RERERETEcmpMRERERETEcmpMgqilpYXFixeTnJzMwoULOX/+vNUhiUWGhobIzc0lOTkZl8tFTk4OHR0dAFy6dImcnBzmzJlDamoq3377rbXBimXeeecdbDYbzc3NgGqIwPDwMBs3bmTOnDmkpKSwZs0aQLkhUFtby/z585k3bx6pqamUl5cDmlPC1euvv47T6bxpDoGJa0VI1hEjQbN06VJz4MABY4wxlZWVJjMz09qAxDK//fabOXz4sPH7/cYYY/bu3WuWL19ujDFm3bp1pri42BhjzKlTp0x8fLwZGRmxKlSxyA8//GBycnJMfHy8OXv2rDFGNUSMefPNN82mTZsCtaOnp8cYo9wId36/38yYMcOcOXPGGGNMe3u7iYyMNL/++qvmlDBVX19vuru7TUJCQmAOMWbiWhGKdUSNSZD09fWZqKioQDHw+/1m1qxZpr293drAJCQ0NjaapKQkY4wxU6ZMMZcuXQqMpaenm2+++caiyMQKQ0NDJjMz03i93sCkohoiAwMDJioqyly9evWm5coN+bMxqa+vN8YYc+bMGRMTE2OGh4c1p4S5vzYmE9WKUK0jupUrSLq7u4mJiSEiIgIAm81GfHw8XV1dFkcmoWDPnj0899xz9Pf34/f7efDBBwNjTqdTeRJmduzYwZo1a0hMTAwsUw2RtrY2Zs6cyXvvvceCBQvIzs7m2LFjyg3BZrPx6aefkpeXR0JCAllZWZSXl3P16lXNKRIwUa0I1TqixiSIbDbbTe+NvplZgNLSUlpaWnj//fcB5Um4O3nyJI2NjWzYsOGWMeVGeBsZGcHr9fLoo4/S1NTEvn37yM/PZ3R0VLkR5kZHR/nggw+orq6ms7OTY8eOUVBQAKhuyM0myodQzBU1JkESFxeHz+djdHQUuPHL7u7uJj4+3uLIxEq7du3i888/56uvvuL+++9n5syZAFy+fDmwTmdnp/IkjNTX13PhwgUSExNxOp34fD6effZZmpubVUPCXEJCApMmTWL16tUAPPbYYyQmJtLZ2ancCHMej4eenh4ef/xxANLT04mJieHHH38ENKfIDROdi4bqeaoakyB56KGHmDdvHocOHQLgs88+w+l04nQ6rQ1MLLN7924qKir4+uuvmTZtWmD5888/z8cffwxAY2Mjvb29ZGVlWRWm/MO2bt1KT08PHR0ddHR0EBsbS21tLQUFBaohYS46Opqnn36a2tpa4MYJZnt7O9nZ2cqNMPfnSeXFixcBaG1tpa2tjeTkZM0pEjDRuWionqfqP78H0cWLFyksLKS/v5+pU6dSXl5OSkqK1WGJBXw+H3FxcTz88MM88MADAERGRtLQ0EBfXx9r166lvb2de+65h/379/Pkk09aHLFYxel08sUXX5CamqoaIni9XtavX09/fz92u53i4mJWrVql3BAqKiooLS1l0qRJGGPYtm0b+fn5mlPC1GuvvUZ1dTW9vb1ER0fjcDhobW2dsFaEYh1RYyIiIiIiIpbTrVwiIiIiImI5NSYiIiIiImI5NSYiIiIiImI5NSYiIiIiImI5NSYiIiIiImI5NSYiInJbnE4nzc3NQdt+XV0dR44cGXe8u7ubFStWMHfuXNLS0nC5XBw/fhwAt9vNhx9+GLTYRETk7ouwOgAREZGx1NXVMTAwwDPPPDPm+IYNG1i2bBlvvPEGAD///DODg4MAFBUV/WNxiojI3aHGRERE7tiSJUvIyMjgu+++o6enh+XLl+N2uwEoLCxk8uTJeL1efvrpJzIzM/nkk0+IjIyksLCQBQsWsHHjRgDefvttHA4Hubm5uN1u/H4/R48eJS8vjx07dty0z66uLuLi4gLvo6OjA69LSkoYGBhg165dFBUV8f333wMwODhIS0sLxhhGRkbYvn07x48f5/fff+eRRx7B7XYzbdq0YB8uEREZg27lEhGRu6KtrY26ujqam5upra3l5MmTgbGGhgaqq6s5d+4cV65c4aOPPppwWy6Xi6KiIl566SU8Hs8tTQnA1q1bKSgoICsri7feeosTJ06MuS23243H46GpqYnZs2fz7rvvAlBWVobD4eDUqVN4PB5SUlIoLi6+gyMgIiJ3Qo2JiIjcFfn5+djtdu677z5cLhdtbW2BsRdeeAGHw4Hdbmf9+vUcPXr0jvf34osv0tXVxebNmwFYuXIlZWVl467/6quvEhMTw/bt2wGoqqri0KFDuFwuXC4XFRUVeL3eO45LRERuj27lEhGRu+Lee+8NvLbb7YyOjo67rs1mAyAiIoLr168Hlg8NDeFwOP72PqdPn05eXh55eXmkp6dTWlrKli1bbllv586d+Hw+ampqAsuMMezfv5+nnnrqb+9PRESCR1dMREQk6CorK7l27RrXr1/nwIEDLFu2DICkpCQaGhoA6O/v58svvwx8ZurUqfzyyy/jbrOmpibwsLsxhtOnT5OUlHTLegcPHqSqqorKykoiIv7z97gVK1awe/fuwDYGBwc5d+7cnf+wIiJyW9SYiIhI0D3xxBPk5uaSkpLC9OnT2bRpEwCvvPIKvb29pKWl8fLLL5ORkRH4zKpVq2hqasLlcgWeC/mrEydOMH/+fNLS0khLS6O1tZV9+/bdsl5xcTFXrlwhKysrcNsW3HhGxeVykZGRwdy5c8nMzMTj8QTpCIiIyP9iM8YYq4MQEZF/r//+5i0REZGx6IqJiIiIiIhYTldMRERERETEcrpiIiIiIiIillNjIiIiIiIillNjIiIiIiIillNjIiIiIiIillNjIiIiIiIillNjIiIiIiIillNjIiIiIiIilvsD2PTJM8k9B2oAAAAASUVORK5CYII=\n", | |
| "text/plain": [ | |
| "<Figure size 960x720 with 1 Axes>" | |
| ] | |
| }, | |
| "metadata": {}, | |
| "output_type": "display_data" | |
| } | |
| ], | |
| "source": [ | |
| "import matplotlib.pyplot as plt\n", | |
| "\n", | |
| "duration_list = []\n", | |
| "\n", | |
| "for N in range(0, 10001, 100):\n", | |
| " duration_list.append((timeit.timeit(randomized_quicksort, number=50))/50)\n", | |
| "\n", | |
| "plt.figure(num=None, figsize=(12, 9), dpi=80, facecolor='w', edgecolor='k')\n", | |
| "plt.plot(range(0, 10001, 100), duration_list)\n", | |
| "plt.xlabel(\"Input Size\")\n", | |
| "plt.ylabel(\"Average Duration (s))\")\n", | |
| "plt.title(\"Graph of the Average Duration for the Randomized Quicksort Algorithm to Sort Lists of Varying Input Sizes\")\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "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": "markdown", | |
| "metadata": {}, | |
| "source": [ | |
| "I'm not sure why the code for this didn't work - I removed the count term since we're not accounting for duplicates, but I keep getting the same error code of list index being out of range." | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 14, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "797888f53fa36bcf0f9d891c4819d8e9", | |
| "grade": false, | |
| "grade_id": "cell-a9d1f063c0340b14", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [ | |
| { | |
| "ename": "IndexError", | |
| "evalue": "list index out of range", | |
| "output_type": "error", | |
| "traceback": [ | |
| "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", | |
| "\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)", | |
| "\u001b[0;32m<ipython-input-14-563ea31fdc4b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m 65\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 66\u001b[0m \u001b[0;31m# Is our algorithm correct?\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 67\u001b[0;31m \u001b[0mtest_quicksort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 68\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 69\u001b[0m \u001b[0;31m# How fast is our algorithm?\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;32m<ipython-input-14-563ea31fdc4b>\u001b[0m in \u001b[0;36mtest_quicksort\u001b[0;34m()\u001b[0m\n\u001b[1;32m 60\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 61\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mtest_quicksort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 62\u001b[0;31m \u001b[0mlst\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrandomized_quicksort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 63\u001b[0m \u001b[0;32massert\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mlst\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 64\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;32m<ipython-input-14-563ea31fdc4b>\u001b[0m in \u001b[0;36mrandomized_quicksort\u001b[0;34m()\u001b[0m\n\u001b[1;32m 56\u001b[0m \u001b[0mlst\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 57\u001b[0m \u001b[0mrandom\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mshuffle\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 58\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mqsort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 59\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 60\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;32m<ipython-input-14-563ea31fdc4b>\u001b[0m in \u001b[0;36mqsort\u001b[0;34m(lst)\u001b[0m\n\u001b[1;32m 32\u001b[0m \u001b[0mN\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mfrm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 33\u001b[0m \u001b[0minds\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mfrm\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlocations\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 34\u001b[0;31m \u001b[0mvalues\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mind\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mind\u001b[0m \u001b[0;32min\u001b[0m \u001b[0minds\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 35\u001b[0m \u001b[0mpartition\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmedian\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 36\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;32m<ipython-input-14-563ea31fdc4b>\u001b[0m in \u001b[0;36m<listcomp>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 32\u001b[0m \u001b[0mN\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mfrm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 33\u001b[0m \u001b[0minds\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mfrm\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlocations\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 34\u001b[0;31m \u001b[0mvalues\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mind\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mind\u001b[0m \u001b[0;32min\u001b[0m \u001b[0minds\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 35\u001b[0m \u001b[0mpartition\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmedian\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 36\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;31mIndexError\u001b[0m: list index out of range" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Without duplicate handling\n", | |
| "\n", | |
| "import timeit\n", | |
| "import random\n", | |
| "import matplotlib.pyplot as plt\n", | |
| "import time \n", | |
| "\n", | |
| "random.seed(123)\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", | |
| "\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", | |
| "\n", | |
| " ind1 = frm + len(lower)\n", | |
| " ind2 = ind1 + 1\n", | |
| "\n", | |
| " # Push back into correct place:\n", | |
| " lst[frm:ind1] = lower\n", | |
| " lst[ind1:ind2] = [partition]\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": "code", | |
| "execution_count": 11, | |
| "metadata": { | |
| "deletable": false, | |
| "editable": false, | |
| "nbgrader": { | |
| "checksum": "ce755b787f1b82629d627d2f8bea66a5", | |
| "grade": true, | |
| "grade_id": "cell-2c0cbd296d612f85", | |
| "locked": true, | |
| "points": 1, | |
| "schema_version": 1, | |
| "solution": false | |
| } | |
| }, | |
| "outputs": [ | |
| { | |
| "ename": "IndexError", | |
| "evalue": "list index out of range", | |
| "output_type": "error", | |
| "traceback": [ | |
| "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", | |
| "\u001b[0;31mIndexError\u001b[0m Traceback (most recent call last)", | |
| "\u001b[0;32m<ipython-input-11-0ccbde90f5ed>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mqsort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m==\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m4\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 2\u001b[0m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mqsort\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m==\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;32m<ipython-input-10-00613ef8f3d4>\u001b[0m in \u001b[0;36mqsort\u001b[0;34m(lst)\u001b[0m\n\u001b[1;32m 9\u001b[0m \u001b[0mN\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mfrm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0minds\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mfrm\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlocations\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0mvalues\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mind\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mind\u001b[0m \u001b[0;32min\u001b[0m \u001b[0minds\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 12\u001b[0m \u001b[0mpartition\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmedian\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;32m<ipython-input-10-00613ef8f3d4>\u001b[0m in \u001b[0;36m<listcomp>\u001b[0;34m(.0)\u001b[0m\n\u001b[1;32m 9\u001b[0m \u001b[0mN\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mto\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mfrm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0minds\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mfrm\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mn\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlocations\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 11\u001b[0;31m \u001b[0mvalues\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0mlst\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mind\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mind\u001b[0m \u001b[0;32min\u001b[0m \u001b[0minds\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 12\u001b[0m \u001b[0mpartition\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmedian\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mvalues\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n", | |
| "\u001b[0;31mIndexError\u001b[0m: list index out of range" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "assert(qsort([4,2,1])==[1,2,4])\n", | |
| "assert(qsort([0])==[0])" | |
| ] | |
| }, | |
| { | |
| "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": null, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "33188fb282e53d117dfe275067ad3567", | |
| "grade": true, | |
| "grade_id": "cell-31ee807cec9ce8bf", | |
| "locked": false, | |
| "points": 0, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "# YOUR CODE HERE\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": 17, | |
| "metadata": { | |
| "deletable": false, | |
| "nbgrader": { | |
| "checksum": "90dbb100f881a2c9a61720a0753ca401", | |
| "grade": false, | |
| "grade_id": "cell-4daf36021c15eaf0", | |
| "locked": false, | |
| "schema_version": 1, | |
| "solution": true | |
| } | |
| }, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "0.24720884699991075\n" | |
| ] | |
| } | |
| ], | |
| "source": [ | |
| "# Without median-of-3\n", | |
| "\n", | |
| "import timeit\n", | |
| "import random\n", | |
| "\n", | |
| "random.seed(123)\n", | |
| "N = 10000\n", | |
| "\n", | |
| "def qsort2(lst):\n", | |
| " indices = [(0, len(lst))]\n", | |
| "\n", | |
| " while indices:\n", | |
| " (frm, to) = indices.pop()\n", | |
| " if frm == to:\n", | |
| " continue\n", | |
| "\n", | |
| " partition = lst[frm]\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_quicksort2():\n", | |
| " lst = [i for i in range(N)]\n", | |
| " random.shuffle(lst)\n", | |
| " return qsort2(lst)\n", | |
| "\n", | |
| "\n", | |
| "def test_quicksort():\n", | |
| " lst = randomized_quicksort2()\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_quicksort2, number=1))" | |
| ] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": 18, | |
| "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": "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": [ | |
| "import matplotlib.pyplot as plt\n", | |
| "\n", | |
| "median_list = []\n", | |
| "no_median_list = []\n", | |
| "\n", | |
| "for N in range(0, 10001, 100):\n", | |
| " median_list.append((timeit.timeit(randomized_quicksort, number=50))/50)\n", | |
| " no_median_list.append((timeit.timeit(randomized_quicksort2, number=50))/50)\n", | |
| "\n", | |
| "plt.figure(num=None, figsize=(12, 9), dpi=80, facecolor='w', edgecolor='k')\n", | |
| "plt.plot(range(0, 10001, 100), median_list, label = \"With median of 3\")\n", | |
| "plt.plot(range(0, 10001, 100), no_median_list, label = \"Without median of 3\")\n", | |
| "plt.xlabel(\"Input Size\")\n", | |
| "plt.ylabel(\"Average Duration (s))\")\n", | |
| "plt.legend()\n", | |
| "plt.title(\"Graph of the Average Duration for the Randomized Quicksort Algorithm to Sort Lists of Varying Input Sizes with and without median-3\")\n", | |
| "plt.show()" | |
| ] | |
| }, | |
| { | |
| "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": [ | |
| "By 500 recursive calls, I'm assuming that we'll be able to perform recursive up to 500 levels, where each level will have double the amount of subarrays as the previous one. \n", | |
| "\n", | |
| "Therefore, if we are doing recursive quicksort with median-of-3, we will be able to fit a dataset of up to $2^{500}$ elements." | |
| ] | |
| } | |
| ], | |
| "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.3" | |
| } | |
| }, | |
| "nbformat": 4, | |
| "nbformat_minor": 2 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment