cs110_pcw_5_2.ipynb

gistfile1.txt

{
 "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 = \"Verina Armanyous\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1a4c3cfc3c34bf644ee45d91835b6f70",
     "grade": false,
     "grade_id": "cell-61b183447ded09ef",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 5.2\n",
    "\n",
    "## Question 1.\n",
    "Using Figure 7.1 in Cormen et al. as a model, perform manually the partition process on the following list: A = [1,5,6,2,3,8,9,4,7]. You just need to specify the followings:\n",
    "1. The array after the process is done.\n",
    "2. The value of $i$ after the process is done."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](partition.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "06dce98d07f8f042785a795b32e7ef75",
     "grade": true,
     "grade_id": "cell-7aa520f8af13679b",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "1- The array after the process is done : A = [1,5,6,2,3,4,7,8,9]\n",
    "\n",
    "2- The value of i after the process is done ( according to the python idex rules): 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "21059776e9083caf84e8abb5b6fb893e",
     "grade": false,
     "grade_id": "cell-6c0a9dfd6980c336",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "Code up a Python implementation of `partition(A, p, r)`, closely follow the pseudo-code in Cormen et al., p.172. Your function should return the index of the pivot in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "395997ac94ed1416c67b22f7977c07a5",
     "grade": false,
     "grade_id": "cell-1ceb2600756c60ff",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def partition(A,p,r): \n",
    "    x = A[r] # assign the value of the last element in the list to variable \"x\"\n",
    "    i = p-1 #the pointer i is less than p by 1 (at the initialization)\n",
    "    for j in range(p, r): #for each element starting from p to the last element before r\n",
    "        if A[j] <= x: #if the element of index j is less than x\n",
    "            i +=1 #increment i\n",
    "            A[i], A[j] = A[j], A[i] #swap the element at index i with the element at index j\n",
    "    A[i+1], A[r] = A[r], A[i+1] #after finish for loop, swap the element at index i+1 with the pivot\n",
    "    return i+1 #return the index of the pivot\n",
    "    \n",
    "    \n",
    "\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "34aa315313b6f9d8de8efe0922e5b563",
     "grade": true,
     "grade_id": "cell-a57b60117a7b82fb",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "A = [1,5,6,2,3,8,9,4,7]\n",
    "assert(partition(A, 0, len(A)-1)==6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3496e310776eba92a8290d114db627cd",
     "grade": false,
     "grade_id": "cell-cd490c45f6733522",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "\n",
    "Code up your own Python implementation of `quicksort(A, p, r)`, using `partition(A,p,r)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7e40c51fd1bd31c790aa0dd8abde1fb7",
     "grade": false,
     "grade_id": "cell-8c39ebb8cd1aa83a",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def quick_sort(A,p,r):\n",
    "    if p<r: # if there is more than one element in the subarray \n",
    "        q = partition (A,p,r) # find the index of the pivot\n",
    "        quick_sort(A,p, q-1) # perform partition to the left of the pivot\n",
    "        quick_sort(A, q+1,r) #perform partition to the right of the pivot\n",
    "    return A \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "80923d1142f0ef958a616db1105a8c1a",
     "grade": true,
     "grade_id": "cell-4f822430efd456ee",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "A = [0]\n",
    "assert(quick_sort(A, 0, 0) == [0])\n",
    "A = [3,1,2]\n",
    "assert(quick_sort(A, 0, 2) == [1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "741cfe874ccaef343713f81ec963360c",
     "grade": false,
     "grade_id": "cell-53941fba9302c591",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4. \n",
    "Explain (using experimental plots) the running time of `quick_sort` when: \n",
    "1. all elements of array A have the same value (e.g., [1,1,1])?\n",
    "2. array A contains distinct elements sorted in decreasing order (e.g., [5,4,2,1])?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f5ddaf0e684d72d229df078b18f321f8",
     "grade": true,
     "grade_id": "cell-b58035dd5fa02329",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZ4AAAEKCAYAAAAiizNaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3Xd8VFX6+PHPSYcktJCETkInkNACCAgYmiCIoCCIuqiIW0TX9auLrI119be2tWDbVXGxg2IBhV3FFTQgCEGKEKQHCCWEBBLSMzPP74+5jCEdyGRSnvfrNa/M3Dn33OfOZOaZe8695xgRQSmllKouXp4OQCmlVP2iiUcppVS10sSjlFKqWmniUUopVa008SillKpWmniUUkpVK008SimlqpUmHqWUUtVKE49SSqlq5ePpAGqi5s2bS0REhKfDUEqpWmXz5s2nRCS0onKaeEoRERFBQkKCp8NQSqlaxRhzqDLltKlNKaVUtdLEo5RSqlpp4lFKKVWttI+nkgoLC0lOTiYvL8/ToSilarGAgADatGmDr6+vp0PxGE08lZScnExwcDAREREYYzwdjlKqFhIR0tLSSE5OJjIy0tPheIw2tVVSXl4eISEhmnSUUhfNGENISEi9bznRxHMBNOkopS6Vfo9o4lFKqXpPRNhxNIPnV+1h1/FMt29PE48qYdGiRcyZMweA+fPn8+yzz17UutVt69atrFy5skrqWrBgAd27d+fGG28sdxsX+voUd8UVV7guVr7qqqs4c+ZMmWVfeOEFcnJySn0uIiKCU6dOXXQcFyIpKYkPPvjA9diT73l1qmv7WWBzEL83lUeW7WDIk98y4aW1LPh2LwmHTrt923pygaoztm7dSkJCAlddddUl1/Xqq6/yn//8p0QHcFVuo7iKkuYLL7zATTfdRMOGDat82xfiXOKZMWOGR+NQFy4jt5A1u0+yKjGF73ancjbfRoCvF5d3CuWeUV2I6xZGaLC/2+PQI55a4uGHH+bFF190PX7wwQdZsGDBJdX5xRdfMHDgQPr06cOoUaNISUmp9Lqpqalcd9119O/fn/79+7Nu3bpKl5k/fz4zZ85kzJgxRERE8Omnn/LnP/+Z6Ohoxo4dS2FhIQCbN29m+PDh9OvXjyuvvJLjx48DzqOEuXPnMmDAALp06UJ8fDwFBQU88sgjLFmyhN69e7NkyRK+++47evfuTe/evenTpw9nz54tEeNzzz1Hz5496dmzJy+88AIAv/vd7zhw4AATJ07k+eefd5UtbRsAiYmJXHHFFXTo0OG89+S9995jwIAB9O7dm9/+9rfY7fZyX9NzRy3Z2dmMHz+eXr160bNnT5YsWcKCBQs4duwYcXFxxMXFlbr+Sy+9RN++fYmOjuaXX34BYOPGjQwePJg+ffowePBgdu/eDcDAgQPZuXOna90rrriCzZs3k52dzW233Ub//v3p06cPy5YtK7GdBx54gPj4eHr37u16fY4dO8bYsWPp3Lkzf/7zn11lv/76awYNGkTfvn2ZOnUqWVlZJepbsGABUVFRxMTEMH369HLjXrRoEZMmTeLqq68mMjKSl19+meeee44+ffpw2WWXkZ6eDsD+/fsZO3Ys/fr1Y+jQoa7X4xyHw0FERMR5R5idOnUiJSWlUp+LW265haVLl7oeBwUFue4/88wz9O/fn5iYGB599NFS36vqlHw6h0XrDnLjmxvo97dV/HHxVtbvT2NcdAve+E0sWx4ew5szY7m+f9tqSTqAs21Pb+ff+vXrJ8UlJia67s9fvkOu/+cPVXqbv3xHiW0WdfDgQenTp4+IiNjtdunQoYOcOnWqRLnLL79cevXqVeK2atWqEmXT09PF4XCIiMgbb7wh9957r4iI/Pvf/5Y777xTREQeffRReeaZZ0qse8MNN0h8fLyIiBw6dEi6detWYt2yyjz66KMyZMgQKSgokK1bt0qDBg1k5cqVIiIyadIk+eyzz6SgoEAGDRokJ0+eFBGRxYsXy6233ioiIsOHD3fFumLFChk5cmSJbYuITJgwQdauXSsiImfPnpXCwsLz9iEhIUF69uwpWVlZcvbsWYmKipKffvpJRETat28vqampJfa7+DYeffRRGTRokOTl5Ulqaqo0a9ZMCgoKJDExUSZMmCAFBQUiIvL73/9e3n777RL1DR8+XDZt2nTeNpcuXSq33367q8yZM2fKjenccwsWLBARkVdeeUVmzZolIiIZGRmu/V61apVce+21IiLy3HPPySOPPCIiIseOHZPOnTuLiMi8efPk3XffFRGR06dPS+fOnSUrK+u8ba1evVrGjx9/3msSGRkpZ86ckdzcXGnXrp0cPnxYUlNTZejQoa71n3zySfnrX/9aIvaWLVtKXl6ea5vlxf3vf/9bOnbsKJmZmXLy5Elp1KiRvPbaayIics8998jzzz8vIiIjRoyQPXv2iIjIhg0bJC4ursR27777bnnrrbdcZc79H1XmczFz5kz5+OOPXXUFBgaKiMhXX30ls2fPFofDIXa7XcaPHy/fffddiW0X/T6pag6HQ7YfOSP/+OoXGfvC99J+7pfSfu6XMuLZ1fL/ViZKQlKa2OwOt2wbSJBKfMdqU1stERERQUhICFu2bCElJYU+ffoQEhJSolx8fHyl60xOTmbatGkcP36cgoKCC7qu4JtvviExMdH1ODMzs8QRRXllxo0bh6+vL9HR0djtdsaOHQtAdHQ0SUlJ7N69mx07djB69GgA7HY7LVu2dNV17bXXAtCvXz+SkpJKjXHIkCHce++93HjjjVx77bW0adPmvOfXrl3L5MmTCQwMdNUZHx9Pnz59Kv06AIwfPx5/f3/8/f0JCwsjJSWF//3vf2zevJn+/fsDkJubS1hYWKXqi46O5r777mPu3LlMmDCBoUOHVmq9oq/Jp59+CkBGRgYzZ85k7969GGNcR5PXX389o0eP5q9//SsfffQRU6dOBZxHKMuXL3f1W+Xl5XH48GG6d+9e7rZHjhxJ48aNAYiKiuLQoUOcOXOGxMREhgwZAjiPGAcNGlRi3ZiYGG688UYmTZrEpEmTyo0bIC4ujuDgYIKDg2ncuDFXX32163Xbvn07WVlZ/PDDD659AsjPzy+x3WnTpvHYY49x6623snjxYqZNmwZc2ufi66+/5uuvv3b9D2VlZbF3716GDRtW6TouRr7NzoYD6axKPME3iSc5kZmHl4F+7Zvyl6u6Map7OB1CgyquqJpo4rkIj17dwyPbvf3221m0aBEnTpzgtttuK7XM0KFDS21SevbZZxk1atR5y+666y7uvfdeJk6cyJo1a5g/f36lY3E4HKxfv54GDRpcVBl/f+chvZeXF76+vq5TTL28vLDZbIgIPXr0YP369aXWfW59b29vbDZbqWUeeOABxo8fz8qVK7nsssv45ptv6Natm+t55w+0S3culqLxiAgzZ87k73//+wXX16VLFzZv3szKlSuZN28eY8aM4ZFHHql0HEVfk4cffpi4uDg+++wzkpKSuOKKKwBo3bo1ISEhbN++nSVLlvCvf/0LcL4mn3zyCV27dr2gmMt6DUaPHs2HH35Y7rorVqzg+++/Z/ny5fztb39j586dZcZdfFteXl7n/S/ZbDYcDgdNmjRh69at5W530KBB7Nu3j9TUVD7//HMeeughoHKfCx8fHxwOB+B8zQoKClz3582bx29/+9tyt10VMnIKWX2uv2ZPKln5Nhr4ejO0c3P+L6oLI7qFERJUTU1nF0j7eGqRyZMn89///pdNmzZx5ZVXllomPj6erVu3lrgVTzrg/FXZunVrAN5+++0LimXMmDG8/PLLrselfcgrU6YsXbt2JTU11ZV4CgsLz+uTKE1wcPB5SXf//v1ER0czd+5cYmNjS7TzDxs2jM8//5ycnByys7P57LPPKjy6KL6NsowcOZKlS5dy8uRJANLT0zl0qFIjxnPs2DEaNmzITTfdxH333cdPP/10Qdsuquh7vGjRovOemz59Ok8//TQZGRlER0cDcOWVV/LSSy+5kvKWLVtK1FnZOC677DLWrVvHvn37AMjJyWHPnj3nlXE4HBw5coS4uDiefvppzpw5Q1ZWVrlxV6RRo0ZERkby8ccfA85ksG3bthLljDFMnjyZe++9l+7du7taECrzuYiIiGDz5s0ALFu2zHVEduWVV/LWW2+5+rKOHj3q+h+oCkfSc3hr7UFueH0DfR9fxT1LtvLjwXQmxLRk4cxYtjwymtd/E8vU2LY1NumAJp5axc/Pj7i4OK6//nq8vb0vub758+czdepUhg4dSvPmzS9o3QULFpCQkEBMTAxRUVH885//vKgyZfHz82Pp0qXMnTuXXr160bt3b3744Ydy14mLiyMxMdHV8f/CCy/Qs2dPevXqRYMGDRg3btx55fv27cstt9zCgAEDGDhwILfffnuFzWzFt1GWqKgoHn/8ccaMGUNMTAyjR492nRxRkZ9//tl1UsITTzzh+iV+xx13MG7cuDJPLijNn//8Z+bNm8eQIUNKnNwwZcoUFi9ezPXXX+9a9vDDD1NYWEhMTAw9e/bk4YcfLlFnTEwMPj4+9OrV67yTL4oLDQ1l0aJF3HDDDcTExHDZZZeVSP52u52bbrqJ6Oho+vTpw5/+9CeaNGlSbtyV8f7777Nw4UJ69epFjx49Sj1JApzNbe+9956rmQ0q97mYPXs23333HQMGDODHH390NdeOGTOGGTNmMGjQIKKjo5kyZcoF/1goyuEQth05w7Nf7WbsC98z9OnVPPZlIqey8rljWAc+/cNgNv5lJE9eF8PI7uEE+F7690J1MFXV3FCXxMbGSvGJ4Hbt2lVhO7e7ORwO+vbty8cff0znzp09GotS6uKV932Sb7Pzw/40ViWm8L9dKaRk5uNlIDaiGWOiwhnVPZyI5oHVHHHlGGM2i0hsReW0j6eWSExMZMKECUyePFmTjlJ1zOnsAld/zfd7UskusNPQz5thnUMZHRVOXLcwmgX6eTrMKqOJp5aIioriwIEDng5DKVVFDqVlsyoxhVWJKSQcOo3dIYQF+zOxd2vGRIUzqGNIrWk6u1BuTTzGmLHAi4A38KaIPFnseX/gHaAfkAZME5Ek67l5wCzADtwtIl+VV6cxJhJYDDQDfgJuFpECY0w74G2gibXOAyJSNeOqKKVUJYkIuQV2MvMKScnM45a31wDQNTyY3w3vwOioFsS0boyXV90fRNRticcY4w28AowGkoFNxpjlIpJYpNgs4LSIdDLGTAeeAqYZY6KA6UAPoBXwjTGmi7VOWXU+BTwvIouNMf+06n4NeAj4SERes+pdCUS4a7+VUuoch0PIyreRmVdIZp4Nm92BweBlDA9PiGJU9zDah9TM/hp3cucRzwBgn4gcADDGLAauAYomnmuA+db9pcDLxnlBxzXAYhHJBw4aY/ZZ9VFancaYXcAI4NzgUW9b9b4GCNDIWt4YOFa1u6mUUr+y2R1k5tk4m1fI2TwbDhG8jCE4wIdGDQII9vdh71l/hnWvvxPBuTPxtAaOFHmcDAwsq4yI2IwxGUCItXxDsXVbW/dLqzMEOCMitlLKzwe+NsbcBQQCJS9oAYwxdwB3ALRr165SO6iUUgD5hXYy82xk5haSU2BDAF9vL5o29KVRA18C/X3w0nl4XNx5HU9pr3Lxc7fLKlNVywFuABaJSBvgKuBdY0yJ/RaR10UkVkRiQ0NDS6mu5ho7dixNmjRhwoQJVVJfUlISPXv2BCAhIYG777673LJFh8gv6tixY0yZMqXS261oWoCKFB2osSa41P25VJc6ZYMqm4iQnW/jeEYuu0+cZXfKWY5n5GIXITQ4gE5hQXRrEUzrpg0JDvDVpFOMO494koG2RR63oWQz17kyycYYH5xNYekVrFva8lNAE2OMj3XUU7T8LGAsgIisN8YEAM2Bqruc2MPuv/9+cnJyXMOeVKXY2FhiY8s+Lb+8IfJbtWp13gi+FamquXQuhc1mw8enaj4W1bk/drv9ki8qrsp9r4vO66/JtWFzOPtrAv29CQlqQKMAH/x86uZZaFXNnUc8m4DOxphIY4wfzpMFlhcrsxyYad2fAnxrjXC6HJhujPG3zlbrDGwsq05rndVWHVh1nrtU+TAwEsAY0x0IAFKrfG/drLxpEUaOHElwcLBbtrtmzRrXkVRp0wyUNkT+OUWPnHbu3Om6Gj8mJoa9e/eW2Na5aQGSkpLo3r07s2fPpkePHowZM4bc3NwS5Q8ePMigQYPo379/iSvsyxqa/p133iEmJoZevXpx8803A84h7u+9917i4uKYO3dumVMDJCUlMXToUPr27Uvfvn1dIykcP36cYcOG0bt3b3r27OkaqLUy+7Np0yZiYmIYNGgQ999/v+v1KkpEXM9FR0e7RkxYs2YNcXFxzJgxwzXkzRNPPEHXrl0ZNWqUayoBKHuagOL7rs5nsztIzy4g6VQ2icczSUrLJiOnkEB/b9o1a0j3lsF0CA2ieZC/Jp0LUZkhrC/2hrNpaw+wH3jQWvYYMNG6HwB8DOzDmVg6FFn3QWu93cC48uq0lnew6thn1elvLY8C1gHbgK3AmIrirmhaBFk5V+Stq6r2tnJuyTHGi6hoWoTiQ9UX9/TTT5c6XcJdd91V6rZ69OhRot7Sphkob7tF65kzZ4689957IiKSn58vOTk5JcqfG/b/4MGD4u3tLVu2bBERkalTp7qG6i/q6quvdk018PLLL1c4NP2OHTukS5curqkF0tLSRMQ5xP348ePFZrOJSNlTA2RnZ0tubq6IiOzZs0fO/Z88++yz8vjjj4uIiM1mk8zMzErvT48ePWTdunUiIjJ37lzX61XU0qVLZdSoUWKz2eTEiRPStm1bOXbsmKxevVoaNmwoBw4cEJFfp3nIzs6WjIwM6dixo2tKi7KmCSi+70okt8AmJzNzZV/KWdl25LRsO3JaEo9lSHJ6jmTmFojdcelTCrhzWgRPoiZMiyDO62VWFlv2SJH7ecDU4utZzz0BPFGZOq3lB/j1zLeiyxOBIRcae01T2WkRynL//fdz//33X1IMFU0zUJ5BgwbxxBNPkJyczLXXXlvh6AuRkZH07t0bKHvqg3Xr1vHJJ58AcPPNN7t+sZc1NP22bduYMmWKa/ytZs2aueqaOnWqq6mqrKkBWrVqxZw5c9i6dSve3t6uAS/79+/PbbfdRmFhIZMmTXLFXdH+nDlzhrNnzzJ48GAAZsyYwZdfflli3bVr13LDDTfg7e1NeHg4w4cPZ9OmTTRq1IgBAwa4hu2Pj49n8uTJrhlKJ06c6Nr/8qYJKLrv9ZGIkGNdX5OZayPf5hwbroGvN2GNAmgc4EOAr7drBHV16bRB92KMe7LiMm5QmWkRyvLMM8/w/vvvl1g+bNiwSs9kWto0A5U1Y8YMBg4cyIoVK7jyyit58803GTFiRJnliw+zX1pTG1Dql4GUMTT9ggULyvzyODfI47n1S5saYP78+YSHh7Nt2zYcDgcBAQGA8zX8/vvvWbFiBTfffDP3338/v/nNbyrcH6nkOInllSsaN5T+elQ0TUDxOuoDh0M4m2/jbK51fY3211QrHZ26FqnMtAhluf/++0udLuFCps8ubZqByg6Rf+DAATp06MDdd9/NxIkT2b59+wXFX5ohQ4awePFigPOSallD048cOZKPPvqItLQ0ANc0ycWVNTVARkYGLVu2xMvLi3fffdc1avKhQ4cICwtj9uzZzJo1yzWNQUWaNm1KcHAwGzY4rxw4ty/FDRs2jCVLlmC320lNTeX7779nwIASB/cMGzaMzz77jNzcXM6ePcsXX3wBVH6agLqu0O4gPTvf1V9zKC2bjNxCgvx9nP01rbS/prroEU8tcm5ahCZNmpzXNHKuszgrK4s2bdqwcOHCC05MlfHCCy+wevVqvL29iYqKYty4cXh5ebmGyL/lllv405/+VOq6S5Ys4b333sPX15cWLVpUamKzirz44ovMmDGDF198keuuu861fMyYMezatcs122VQUBDvvfcePXr04MEHH2T48OF4e3vTp0+fUud6efjhh7nnnnuIiYlBRIiIiODLL7/kD3/4A9dddx0ff/wxcXFxriOFNWvW8Mwzz+Dr60tQUBDvvPNOpfdh4cKFzJ49m8DAQK644grXLJ5FTZ48mfXr19OrVy+MMTz99NO0aNGixBQDffv2Zdq0afTu3Zv27dufN7fQ+++/z+9//3sef/xxCgsLmT59Or169ap0nLWRiJBvc7ia0HIKnJf5+Xl70TTQj0YBPnp9jYfotAil0GkRVHXJyspyXX/05JNPcvz48fPOXlQXprz+mkYNfGlUQ/prasL3iTvotAh1jE6LUDetWLGCv//979hsNtq3b3/Bs20qsJ+7vibXOUSNzeHAGEOgnzfNgxoQHOCLn4/2KtQkmnhqCZ0WoW6aNm3aebNfqsoptDub0M7m2sjKd46H5u1lCA5wHtUEB/jg7aXJpqbSxHMBRMTjh+hK1Ueu/hrrLLSi/TXNrP6ahrWkv0a7NzTxVFpAQABpaWmEhIRo8lGqGogI2QV2K9kUUmBzANDAz5vwRgE0CvAlwNerVn0eRYS0tDTXqfj1lSaeSmrTpg3Jycmkpta60XaUqjUcIuQXOsgttJNfaMcuYAz4+3gR4OtNA19vbF6GdJyDOtZGAQEBF3TxdV2kiaeSfH19XVeIK6WqTkpmHt/sSuGbxBTW7U+jwOagcQNfRnQLY3RUOMO6hBLkr19VdYm+m0qpaiUi7EnJYlXiCVYlprAtOQOAts0acNPA9oyOCic2oim+3npyQF2liUcp5XY2u4NNSadZlZjCN7tSOJyeA0Cvtk24b0wXRke1oEt4UK3qr1EXTxOPUsotsvJtfL8nlVWJKXz7y0kycgvx8/FiSMcQfju8A6O6hxPeqH53stdXmniUUlXmREYeq6z+mvX70yiwO2jS0JeR3cMYExXO0M6hBGp/Tb2n/wFKqYsmIvxy4qyrCW271V/TPqQhvxnk7K/p174pPtpfo4rQxKOUuiCFdgebDqbztZVskk87p6zo064J91/ZlTFR4XQK0/4aVTZNPEqpCp3NK+Q7q79m9S8nycyz4e/jxeWdmjMnrhMjuocRFqz9NapyNPEopUp17Ewu3+xKYVViChsOpFFoF5oF+jGmRwtGR4UztHNzGvrpV4i6cPpfo5QCnP01icczXf01O45mAhDZPJBbh0QyOiqcvu2a4u2lTWjq0mjiUaoeK7Q7+PFAOqsST/DNrpMcPZOLMdC3XVPmju3GaKu/RqmqpIlHqXomI/fX/po1u09yNs9GgK8Xl3cK5e6RnRjRLZzQYH9Ph6nqME08StUDR8/k8k3ir/01NocQEujHuJ4tGB3Vgss7NaeBn3fFFSlVBTTxKFUHiQg7jzn7a1YlppB43Nlf0yE0kFlDIxkTFU7vttpfozxDE49SdUSBzcGGA2mukwOOZ+RhDMS2b8q8cd0YFRVOx1Dtr1Gep4lHqVosI6eQNXtO8nViCt/tTiUr39lfM6xzKH8a3YWR3cIICdL+GlWzaOJRqpY5kp7jur5m48F0bA6heZA/E2JaMqp7OJd3bk6Ar/bXqJpLE49SNZyI8PPRDFd/zS8nzgLQOSyI2cM6MDoqnN5tmuCl/TWqltDEo1QNlG+zs36/s7/mf7tOciIzDy8DsRHNePCq7oyKCieyeaCnw1TqomjiUaqGOJNTwOrdJ1ll9ddkF9hp6OfNsM6hjIoKZ0S3MJoF+nk6TKUumSYepTzocFoOq3alsCrxBJuSTmN3CKHB/kzs3ZoxUeEM6hii/TWqztHEo1Q1cjiE7UczXBdz7k5x9td0CQ/id8M7MDqqBTGtG2t/jarTNPEo5WZ5hVZ/jTUz58mz+Xh7GfpHNOWh8d0ZHRVO+xDtr1H1hyYepdzgdHYB3/7i7K/5fm8qOQV2Av28Gd41lFHdw4nrGkZT7a9R9ZQmHqWqyKG0bFYlpvB1YgoJSek4BMIb+TO5T2tGRYUzqIP21ygFmniUumgOh7A1+Yyrv2bvySwAurUI5s64ToyOCqdnK+2vUao4TTxKXaBfTmTy9g9JfLPrJKlWf83AyGbcMKAdo6PCadusoadDVKpG08Sj1AV6d/0hPtx4hGB/H/4xtRejuofTuKGvp8NSqtbwcmflxpixxpjdxph9xpgHSnne3xizxHr+R2NMRJHn5lnLdxtjrqyoTmNMpFXHXqtOvyLPXW+MSTTG7DTGfOC+PVb1wUPjo7g+tg1n820s3ZxMvt3u6ZCUqlXclniMMd7AK8A4IAq4wRgTVazYLOC0iHQCngeestaNAqYDPYCxwKvGGO8K6nwKeF5EOgOnrboxxnQG5gFDRKQHcI+bdlnVEw38vHl6Si+emRLDliOnGb9gLT/sP+XpsJSqNdx5xDMA2CciB0SkAFgMXFOszDXA29b9pcBIY4yxli8WkXwROQjss+ortU5rnRFWHVh1TrLuzwZeEZHTACJy0g37quqhqbFtWXbn5QQH+HDTmz/y8rd7cTjE02EpVeO5M/G0Bo4UeZxsLSu1jIjYgAwgpJx1y1oeApyx6ii+rS5AF2PMOmPMBmPM2EvcL6VcurYI5os5l3N1r1Y8+/Ueblm0ifTsAk+HpVSN5s7EU9o5pMV/DpZVpqqWg/MEis7AFcANwJvGmCYlgjXmDmNMgjEmITU1tZTqlCpdoL8PL0zrzROTe7LhQBpXvRhPQlK6p8NSqsZyZ+JJBtoWedwGOFZWGWOMD9AYSC9n3bKWnwKaWHUU31YysExECq1mu904E9F5ROR1EYkVkdjQ0NAL3FVV3xljuHFgez79/WD8fb2Y9voGXv9+PyLa9KZUce5MPJuAztbZZn44TxZYXqzMcmCmdX8K8K04P6nLgenWWW+ROBPFxrLqtNZZbdWBVecy6/7nQByAMaY5zqa3A1W+t0oBPVs35ou7LmdMVDj/b+UvzH5nMxk5hZ4OS6kaxW2Jx+pvmQN8BewCPhKRncaYx4wxE61iC4EQY8w+4F7gAWvdncBHQCLwX+BOEbGXVadV11zgXquuEKturLJpxphEnMnpfhFJc9d+K9UowJdXb+zL/Kuj+G7PSca/FM+2I2c8HZZSNYbRpoAx9MV+AAAer0lEQVSSYmNjJSEhwdNhqDpg65Ez3Pn+T5w8m8eDV3Vn5uAInCdhKlX3GGM2i0hsReXcegGpUvVd77ZNWHH35QzrHMr8LxK584OfyMzTpjdVv2niUcrNmjT0443fxDJvXDe+2pnCxJfWsvNYhqfDUspjNPEoVQ28vAy/Hd6RxXdcRm6hncmv/sCHGw/rWW+qXtLEo1Q16h/RjJV3D2VgZDPmffoz9360jex8W8UrKlWHaOJRqpqFBPnz9q0D+L/RXVi29SjXvLKOPSlnPR2WUtVGE49SHuDlZbhrZGfemzWQMzmFXPPyOj7ZnOzpsJSqFpp4lPKgwZ2as/KPl9OrbWP+7+NtzF26nbxCnWZB1W2aeJTysLDgAN6bNZC7RnRiScIRJr2yjv2pWZ4OSym30cSjVA3g4+3F/43pyqJb+5OSmcfEl9byxbbiQxsqVTdo4lGqBrmiaxgr7h5Kt5aNuOvDLTz8+Q7ybdr0puoWTTxK1TCtmjRg8R2XccewDry74RBTXlvP4bQcT4elVJXRxKNUDeTr7cVfrurO6zf341BaNuNfiuernSc8HZZSVUITj1I12JgeLVhx91A6NA/kt+9u5m9fJlJgc3g6LKUuiSYepWq4ts0a8tHvBnHL4AgWrj3ItNfXc/RMrqfDUuqiaeJRqhbw9/Fm/sQevDKjL3tTshi/IJ7Vv5z0dFhKXRRNPErVIuNjWvLFXZfTsnEDbl20iaf++ws2uza9qdpFE49StUxk80A++8NgbhjQjtfW7GfGmz+Skpnn6bCUqjRNPErVQgG+3vz92mien9aLn5MzuOrFeNbuPeXpsJSqFE08StVik/u0YfmcITQL9OPmt37khW/2YHfoHD+qZtPEo1Qt1zk8mGVzhjC5d2te+GYvM9/aSOrZfE+HpVSZNPEoVQc09PPhH9f34qnrotmUlM74BfH8eCDN02EpVSpNPErVEcYYpvVvx+d3DiHQ34cb3tjAq2v24dCmN1XDVDrxGGMC3RmIUqpqdG/ZiOVzhnBVdEue/u9uZr29idPZBZ4OSymXChOPMWawMSYR2GU97mWMedXtkSmlLlpwgC8v3dCHv13Tg3X70hi/IJ6fDp/2dFhKAZU74nkeuBJIAxCRbcAwdwallLp0xhhuHhTBJ78fjLe34fp/rufN+AOIaNOb8qxKNbWJyJFii3SCEKVqieg2jfnyrqGM6BbG4yt28bv3NpORW+jpsFQ9VpnEc8QYMxgQY4yfMeY+rGY3pVTt0LiBL/+6uR8Pje/O/3adZMJL8fycnOHpsFQ9VZnE8zvgTqA1kAz0th4rpWoRYwy3D+3Akt8OwmYXrnvtB95dn6RNb6raGf2nKyk2NlYSEhI8HYZSbpOeXcC9H21lze5UJsS05MnrYgjy9/F0WKqWM8ZsFpHYispV+J9mjIkE7gIiipYXkYmXEqBSynOaBfrx1sz+vPbdfv7x9W4Sj2Xyyo196d6ykadDU/VAZZraPgeSgJeAfxS5KaVqMS8vw51xnfhg9mVk5duY9Mo6Ptp0RJvelNtV5tg6T0QWuD0SpZRHXNYhhBV3D+WeJVv48yfb+fFgOn+b1IOGftr0ptyjMkc8LxpjHjXGDDLG9D13c3tkSqlqExrszzu3DeSPIzvz6ZZkJr2yjn0nz3o6LFVHVeYnTTRwMzACODfVoViPlVJ1hLeX4U+juxAb0ZR7Fm9l4svreGJyTyb3aePp0FQdU5kjnslABxEZLiJx1k2TjlJ11NDOoaz841B6tmrMn5ZsY96n28kr1GvGVdWpTOLZBjRxdyBKqZojvFEAH8weyO+v6MiHG48w+dUfOJKe4+mwVB1RmcQTDvxijPnKGLP83M3dgSmlPMvH24vfDe9IbPum7DqeyYcbD3s6JFVHVKaP51G3R6GUqlFEhJU/n2D+FztJy8rntiGR3BnXydNhqTqiwiMeEfmutFtlKjfGjDXG7DbG7DPGPFDK8/7GmCXW8z8aYyKKPDfPWr7bGHNlRXUaYyKtOvZadfoV29YUY4wYYyq8qlap+iz5dA6z3k7gzg9+IizYn2V3Xs4jV0cRqCMbqCpSZuIxxqy1/p41xmQWuZ01xmRWVLExxht4BRgHRAE3GGOiihWbBZwWkU44p194ylo3CpgO9ADGAq8aY7wrqPMp4HkR6Qyctuo+F0swcDfwY0VxK1Vf2ewO3ow/wJjnv2f9/jQeGt+dZXcOIbpNY0+HpuqY8n7CBAKISPBF1j0A2CciBwCMMYuBa4DEImWuAeZb95cCLxtjjLV8sYjkAweNMfus+iitTmPMLpynd8+wyrxt1fua9fhvwNPAfRe5L0rVaT8nZzDvs+3sOJrJiG5hPHZND9o0bejpsFQdVV7iudRxM1oDRefxSQYGllVGRGzGmAwgxFq+odi6ra37pdUZApwREVvx8saYPkBbEfnSmtJBKWXJzrfx3Ko9/HvdQUKC/Hl5Rh/GR7fE+ftPKfcoL/GEGWPuLetJEXmugrpL+88tnszKKlPW8tKaBsssb4zxwtmEd0vZYVqBGHMHcAdAu3btKiquVK33v10pPLJsJ0fP5DJjYDvmju1G4wa+ng5L1QPlJR5vIIjSv9QrIxloW+RxG+BYGWWSjTE+QGMgvYJ1S1t+CmhijPGxjnrOLQ8GegJrrF9wLYDlxpiJInLevAci8jrwOjinRbiYHVaqNjiZmcf8L3ay8ucTdA4LYunvBhEb0czTYal6pLzEc1xEHruEujcBna1pFY7iPFlgRrEyy4GZwHpgCvCtiIh1ndAHxpjngFZAZ2AjziRYok5rndVWHYutOpeJSAbQ/NzGjDFrgPuKJx2l6gOHQ3h/42Ge/s8v5Nsd3DemC3cM64ifT2Uu51Oq6pSXeC6pkdfqs5kDfIXz6OktEdlpjHkMSBCR5cBC4F3r5IF0nIkEq9xHOE9EsAF3iogdoLQ6rU3OBRYbYx4Htlh1K6WA3SfO8pfPfmbzodMM7hjCE5OjiWwe6OmwVD1V5gykxphmIpJezfHUCDoDqaor8grtvPTtXv713QGCA3x4aHwU1/ZtrScPKLe45BlI62vSUaquWLfvFA9+9jNJaTlc17cND47vTrNAv4pXVMrN9FJkpeqYtKx8nlixi0+3HCUipCEf3D6QwZ2aV7yiUtVEE49SdYSI8MlPR3liRSJn82zMievEnBGdCPD19nRoSp1HE49SdcDBU9k8+NnP/LA/jX7tm/L3a6PpEn6xg44o5V6aeJSqxQpsDv713X5eWr0Pfx8vnpjckxv6t8PLS08eUDWXJh6laqlNSen85dOf2Xsyi/ExLXl0QhRhjQI8HZZSFdLEo1Qtk5FbyJP/+YUPNx6mdZMGvHVLLCO6hXs6LKUqTROPUrWEiPDl9uP89YtE0rPzuf3ySP40uovOk6NqHf2PVaoWOJKewyPLdrB6dyrRrRuz6Nb+9Gyt8+So2kkTj1I1mM3u4N/rknhu1R6MgYcnRDFzUHt8vHV8NVV7aeJRqobannyGeZ/+zM5jmYzsFsZjk3rSukkDT4el1CXTxKNUDZOVb+MfX+/m7R+SaB7kz6s39mVczxY6vpqqMzTxKFWDrEpM4dFlOziemceNA9vx57HdaBSgk7OpukUTj1I1QEpmHvOX7+Q/O07QNTyYl2b0pV/7pp4OSym30MSjlAc5HML7Px7i6f/upsDu4P4ru3LHsA746skDqg7TxKOUh/xyIpN5n/7MlsNnuLxTcx6f1JMInZxN1QOaeJSqZnmFdl78317e+P4AjRr48vy0XkzqrZOzqfpDE49S1Sh+byoPfraDw+k5TO3Xhr9c1Z2mOjmbqmc08ShVDdKy8nl8xS4+23KUyOaBfDB7IIM76uRsqn7SxKOUG4kIH29O5v+t3EV2vo27R3TiD3E6OZuq3zTxKOUm+1OzePCzn9lwIJ3+EU35f5Oj6ayTsymliUepqpZvs/PPNQd4ZfU+Any9+Pu10UyLbauTsyll0cSjVBXaeDCdv3z2M/tOZnF1r1Y8PKE7YcE6OZtSRWniUaoKZOQU8uR/d/HhxiO0btKAf9/an7iuYZ4OS6kaSROPUpdARPhi+3Ee+yKR0zkF3DGsA/eM6kxDP/1oKVUW/XQodZGOpOfw0Oc7+G5PKjFtGvP2bf3p0UonZ1OqIpp4lLpANruDhWsP8vw3e/A2hkevjuI3gyLw1pMHlKoUTTxKVVJugZ2lPyXz1tqDHDyVzaju4Tx2TQ9a6eRsSl0QTTxKVeBkZh7vrD/Eez8e4kxOIb3aNOb1m/sxOipcx1dT6iJo4lGqDLuOZ/Jm/EGWbzuKzSGMiQrn9qEdiG3fVBOOUpdAE49SRYgIa/aksjD+IGv3naKBrzczBrTjtssjaR+iUxYoVRU08SiFc6qCz7ccZeHag+w9mUV4I3/mju3GjAHtaNxQp55Wqipp4lH1WlpWPu9uOMS76w+Rll1AVMtGPD+tF+OjW+Hno7OAKuUOmnhUvbTv5FkWrj3IJz8dpcDmYES3MG4fGsmgDiHaf6OUm2niUfWGiPDD/jTejD/A6t2p+Pt4MaVfG24bEkmnsCBPh6dUvaGJR9V5BTYHX2w7xptrD7LreCbNg/y4d3QXbhzYjpAgf0+Hp1S9o4lH1Vlncgp4/8fDvP1DEifP5tMlPIinr4thYu9WOhGbUh7k1sRjjBkLvAh4A2+KyJPFnvcH3gH6AWnANBFJsp6bB8wC7MDdIvJVeXUaYyKBxUAz4CfgZhEpMMbcC9wO2IBU4DYROeTO/VaelXQqm7fWHeTjhGRyC+0M7dycZ6b2Yljn5tp/o1QN4LbEY4zxBl4BRgPJwCZjzHIRSSxSbBZwWkQ6GWOmA08B04wxUcB0oAfQCvjGGNPFWqesOp8CnheRxcaYf1p1vwZsAWJFJMcY83vgaWCau/ZbeYaIsCnpNG/GH2DVrhR8vby4pncrZg2NpFuLRp4OTylVhDuPeAYA+0TkAIAxZjFwDVA08VwDzLfuLwVeNs6fpNcAi0UkHzhojNln1UdpdRpjdgEjgBlWmbetel8TkdVFtrcBuKkqd1J5ls3uYOWOE7wZf4DtyRk0bejLnLhO3DyovU7AplQN5c7E0xo4UuRxMjCwrDIiYjPGZAAh1vINxdZtbd0vrc4Q4IyI2EopX9Qs4D8XvCeqxsnMK2TJxiMs+iGJo2dy6dA8kMcn9eS6vm1o4Kf9N0rVZO5MPKU1pksly5S1vLQr+sor/+uGjLkJiAWGl1IWY8wdwB0A7dq1K62IqgGOpOew6Icklmw6Qla+jcs6NOOvE3swolsYXjotgVK1gjsTTzLQtsjjNsCxMsokG2N8gMZAegXrlrb8FNDEGONjHfWcty1jzCjgQWC41XxXgoi8DrwOEBsbWzxBKg/bcvg0b8Yf5D87juNlDBNiWjLr8g5Et9GJ15SqbdyZeDYBna2zzY7iPFlgRrEyy4GZwHpgCvCtiIgxZjnwgTHmOZwnF3QGNuI8silRp7XOaquOxVadywCMMX2AfwFjReSkG/dXVTG7Q1iVeII34g+y+dBpggN8mD2sA7cMjqBlY50DR6naym2Jx+qzmQN8hfPU57dEZKcx5jEgQUSWAwuBd62TB9JxJhKsch/hPBHBBtwpInaA0uq0NjkXWGyMeRznmWwLreXPAEHAx9aptIdFZKK79ltduux8Gx8nHOGtdUkcTs+hbbMGPHp1FNfHtiXQXy89U6q2MyLaqlRcbGysJCQkeDqMeud4Ri6Lfkjiwx8Pk5lno1/7ptx+eSRjerTQaaWVqgWMMZtFJLaicvrzUXncjqMZvBl/gC+3H8chwrieLZk1NJK+7Zp6OjSllBto4lEe4XAIq3ef5I34A2w4kE6gnze/GRTBrUMiaNusoafDU0q5kSYeVa1yC+x8uiWZhWsPciA1m5aNA/jLVd2YPqAdjQJ0wjWl6gNNPKpanDybx7vrD/HehkOczikkunVjXpzem6uiW+LrrROuKVWfaOJRbvXLiUwWxh9k2dZjFDocjOoezuyhHegf0VQH7FSqntLEo6qciPD93lO8GX+A+L2naODrzfQBbbl1SCSRzQM9HZ5SysM08agqk2+zs2zLMd5ce4A9KVmEBvtz/5VduXFgO5o09PN0eEqpGkITj7pk6dkFvLfhEO+sP8SprHy6tQjmH1N7MaFXS/x9dMBOpdT5NPGoShMRUjLz2Z+axYHULPanZrM/NYuNB9PJtzm4omsos4d2YHDHEO2/UUqVSROPKiGv0E5SWjb7T2ZbCcaZZA6kZpFdYHeVC/L3oUNoINfHtuU3g9rTOTzYg1ErpWoLTTz1lIhwKqvAOnrJtpKL8/6R0zkUHUmpdZMGdAgNZGpsWzqGBdGxeSAdw4IIC/bXIxul1AXTxFPHFdgcHE7PdjWL7T+ZzYFTWew/mUVmns1VroGvN5HNA+nVtgnX9m1Nh9AgOoYGEtk8kIZ++m+ilKo6+o1SR5zOLrASyvlHL4fSc7A7fj18CW/kT8fQIK7p3ZqOoYHOBBMWRMtGATqRmlKqWmjiqUVsdgdHTuf+2u9y7uglNZv07AJXOT9vLyKbB9KtZTDjY1rSITSQjqFBRDYPJFiHpVFKeZgmnhooM6/Q2e9yMuu8o5ektGwK7b8evTQP8qNDaBBX9mhBRyu5dAwNonXTBjqNgFKqxtLE4yEOh3D0TK7rjLGipyinnv11dm4fL0P7kIZ0DA1iVFQ4HayO/Y7Ng2jcUI9elFK1jyYeN8vOt3Hw1LmO/V+TzMFT2eTbHK5yTRr60jE0iLiuoVbHvrNzv22zhjqIplKqTtHEU4X2ppzlh/1p552ifDwjz/W8l4F2zZxHL0M7N3cmlzBnkmkWqEPKKKXqB008VWjN7lSeWLmLYH8fOoQFMahjiOvIpWNoEO1CGuoQMkqpek8TTxWa0q8N1/RuRaheWKmUUmXSxFOFmmpzmVJKVUh7rZVSSlUrTTxKKaWqlSYepZRS1UoTj1JKqWqliUcppVS10rPalFKqthMBWz7Y88FWYP3NB3tBsb9Fny+jXOcx0LqvW8PVxKOUUhfKbru0L3dbfpGyla2jnLochVW3b4HNNfEopeo5h8P5BVsVv+arqrw4Ko67srz9wccfvP3K+OsPAY2tcn7F/pZRvrxyrjJlbNPL/aOraOJRSv1KBBy2i/yCvpRy1fRr3sunEl/MAdYXfSW/yC+lnLcv1MNRTjTxKOVJDoebvsgv9Jd+kfWQCsOuHFPOF3KRL2bfJlX3RV5ROS89n6om0MSj1IU6vh12La+CX/N5zqOLquLlW/EXs19D8G5a9b/cSyvn5VMvf82rimniUepC/bICvn/Gvdvwb+xs7mnQGAKaOO+7/jaGBkXuBzSBgEbg2xB8GzhvPg3qbTOOqvk08Sh1oeLmwdD/A1suFOZZf62bLQ8Kc6zlRe+XVebc8rxf6yvMcZbJz4SsFOfR0sUwXs5k5BNQJCEFnJ+cSl0eYCWxgCJlGkL7weAfVLWvpaqXNPEodTF8/Jy3gMbu24YI2AuhIAvyzkDOacg9DbnpkJNezv0zkJ/hPPOqIMt5qwqD74Yxf6uaulS9polHqfI4HM4vcHGA2H+9by+8gKOZc8uLPi52dFNaOVvuxZ+26+1fwRFMQClHPMXLFDsSauXeaztU/aGJp76qytNmHYXgsBf7ghbn/RLLrftlfaE7iqxbYrnDeq605cVuFxSPlB1nVTFe1hd6QJHmryL3GzQt0vxVRpnzmsjKWe7TQM/eUjWaJp7qUqdPm8X5xWq8rb9ezovQjJezc7vU5cVu5y33ttYrbbmX82yp0pYbL+cXbqnLi9RZFfF4+V7YEYW3n3b0K2Vxa+IxxowFXgS8gTdF5Mliz/sD7wD9gDRgmogkWc/NA2YBduBuEfmqvDqNMZHAYqAZ8BNws4gUlLeNKvfTO7BuQelf9HrarFJKAW5MPMYYb+AVYDSQDGwyxiwXkcQixWYBp0WkkzFmOvAUMM0YEwVMB3oArYBvjDFdrHXKqvMp4HkRWWyM+adV92tlbcMtO92wObToWYkv8ku50tlPm1GUUrWaO494BgD7ROQAgDFmMXANUDTxXAPMt+4vBV42xhhr+WIRyQcOGmP2WfVRWp3GmF3ACGCGVeZtq97XytqGiFRhO5Ol21XOm1JKqTK586dza+BIkcfJ1rJSy4iIDcgAQspZt6zlIcAZq47i2yprG0oppTzAnYmntEb/4kcZZZWpquWVjQNjzB3GmARjTEJqamopqyillKoK7kw8yUDbIo/bAMfKKmOM8QEaA+nlrFvW8lNAE6uO4tsqaxvnEZHXRSRWRGJDQ0MvaEeVUkpVnjsTzyagszEm0hjjh/NkgeXFyiwHZlr3pwDfWn0vy4Hpxhh/62y1zsDGsuq01llt1YFV57IKtqGUUsoD3HZygYjYjDFzgK9wnvr8lojsNMY8BiSIyHJgIfCudfJAOs5EglXuI5wnItiAO0XEDlBandYm5wKLjTGPA1usuilrG0oppTzD6I//kmJjYyUhIcHTYSilVK1ijNksIrEVldMLQpRSSlUrTTxKKaWqlTa1lcIYkwocusjVm+M8y64+0X2uH3Sf64dL2ef2IlLhacGaeKqYMSahMm2cdYnuc/2g+1w/VMc+a1ObUkqpaqWJRymlVLXSxFP1Xvd0AB6g+1w/6D7XD27fZ+3jUUopVa30iEcppVS10sRThYwxScaYn40xW40xdXLoA2PMW8aYk8aYHUWWNTPGrDLG7LX+NvVkjFWtjH2eb4w5ar3XW40xdWYiJmNMW2PMamPMLmPMTmPMH63ldfZ9Lmef6/L7HGCM2WiM2Wbt81+t5ZHGmB+t93mJNS5m1W5bm9qqjjEmCYgVkTp73r8xZhiQBbwjIj2tZU8D6SLypDHmAaCpiMz1ZJxVqYx9ng9kiciznozNHYwxLYGWIvKTMSYY2AxMAm6hjr7P5ezz9dTd99kAgSKSZYzxBdYCfwTuBT4tMpvzNhF5rSq3rUc86oKIyPeUnFbiGpyzvmL9nVStQblZGftcZ4nIcRH5ybp/FtiFc0LFOvs+l7PPdZY4ZVkPfa2b4JzNeam13C3vsyaeqiXA18aYzcaYOzwdTDUKF5Hj4PwAA2Eejqe6zDHGbLea4upMs1NRxpgIoA/wI/XkfS62z1CH32djjLcxZitwElgF7Kfs2ZyrjCaeqjVERPoC44A7rSYaVTe9BnQEegPHgX94NpyqZ4wJAj4B7hGRTE/HUx1K2ec6/T6LiF1EeuOcPHMA0L20YlW9XU08VUhEjll/TwKf4Xwj64MUq438XFv5SQ/H43YikmJ9aB3AG9Sx99pq8/8EeF9EPrUW1+n3ubR9ruvv8zkicgZYA1xG2bM5VxlNPFXEGBNodUpijAkExgA7yl+rzig6y2vR2V/rrHNfwJbJ1KH32up0XgjsEpHnijxVZ9/nsva5jr/PocaYJtb9BsAonH1bZc3mXHXb1rPaqoYxpgPOoxxwzuz6gYg84cGQ3MIY8yFwBc4RbFOAR4HPgY+AdsBhYKqI1JnO+DL2+QqczS8CJAG/Pdf/UdsZYy4H4oGfAYe1+C84+zzq5Ptczj7fQN19n2NwnjzgjfMg5CMRecz6LlsMNMM5m/NNIpJfpdvWxKOUUqo6aVObUkqpaqWJRymlVLXSxKOUUqpaaeJRSilVrTTxKKWUqlaaeJSqYsaYrIpLXXCdEcaYGWU852WMWWCM2WGNjr7JGBNpPbfy3LUaStUUPhUXUUrVABHADOCDUp6bBrQCYkTEYYxpA2QDiEidGcZf1R16xKOUmxhjrjDGrDHGLDXG/GKMed+6Qv7c3E1PWfOhbDTGdLKWLzLGTClSx7mjpyeBodacMH8qtqmWwHFrWBdEJFlEThfZTnNjzO+KzClz0Biz2np+jDFmvTHmJ2PMx9ZYZUq5lSYepdyrD3APEAV0AIYUeS5TRAYALwMvVFDPA0C8iPQWkeeLPfcRcLWVVP5hjOlTfGUR+ac1GGR/nCMOP2eMaQ48BIyyBrdNwDkXi1JupYlHKffaaB2BOICtOJvMzvmwyN9BF7sBEUkGugLzcA738j9jzMgyir8IfCsiX+AcEDIKWGcNjT8TaH+xcShVWdrHo5R7FR3jys75nzkp5b4N6weh1SxXqWmHrbG0/gP8xxiTgnPyrv8VLWOMuQVnYplzbhGwSkRuqMw2lKoqesSjlOdMK/J3vXU/Cehn3b8G56yQAGeB4NIqMcb0Nca0su57ATHAoWJl+gH34Rzw8dwgmBuAIUX6lxoaY7pc4j4pVSE94lHKc/yNMT/i/AF47qjjDWCZMWYjziOWbGv5dsBmjNkGLCrWzxMGvGGM8bceb8TZb1TUHJyjDa+2zm9IEJHbraOgD4us+xCwp6p2UKnS6OjUSnmAMSYJiBWRU56ORanqpk1tSimlqpUe8SillKpWesSjlFKqWmniUUopVa008SillKpWmniUUkpVK008SimlqpUmHqWUUtXq/wPl/YtNGNJL/AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# YOUR CODE HERE\n",
    "import time\n",
    "def average_time(lst):# to calculate the running time for each list\n",
    "    begin= time.time()\n",
    "    quick_sort(lst,0,len(lst)-1)\n",
    "    average_t = time.time()- begin\n",
    "    return average_t\n",
    "x =[5,10,15,20,15,30] #size of input \n",
    "y=[average_time([1]*5),average_time([1]*10),average_time([1]*15),average_time([1]*20),average_time([1]*25),average_time([1]*30)] #for storing the average time of 1\n",
    "y1= []\n",
    "z =[]\n",
    "k = 5 #number of elements in each list at the beginning\n",
    "n= 6  # number of lists to be generated\n",
    "import random\n",
    "for i in range(n): \n",
    "    l = (random.sample(range(0,100),k))\n",
    "    z.append(sorted(l,reverse = True))\n",
    "    y1.append(average_time(z))\n",
    "    k+=5\n",
    "#the plot code\n",
    "import matplotlib.pyplot as plt #import the library\n",
    "%matplotlib inline  \n",
    "#displa\n",
    "plt.plot(x,y)  #plot input size, and ruuning tume of threeWayMerge algorithm\n",
    "plt.plot(x,y1) #plot input size and running time of twoWayMerge algorithm\n",
    " #plot input size and running time of extended ThreeWayMerge algorithm \n",
    "\n",
    "plt.xlabel(\"Input Size\") #label the x-axis  as input size\n",
    "plt.ylabel(\"Time\") #label y-axis as time\n",
    "plt.legend({'y = all elements of the list have the same value','y1 = list is in decreasing order'}) # show the legend\n",
    "plt.show() "
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}