cs110_pcw_5_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Verina Armanyous\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "69779d40de39e2fcb822ffd099ed946a",
     "grade": false,
     "grade_id": "cell-361a67c139252f60",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 5.1\n",
    "\n",
    "## Question 1.\n",
    "\n",
    "### Question 1a.\n",
    "\n",
    "Write the worst sort function in the world, `worst_sort`. This function takes a list, and then randomly shuffles it until it happens to be in sorted order. Once it is in sorted order then the list is returned.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "c144735a0a3c9ee1e5a60e781fec46a9",
     "grade": false,
     "grade_id": "cell-ead9c74054a1c5da",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import random  #import random module\n",
    "def worst_sort(A): #define the function\n",
    "    print(A) # print the list if it's sorted\n",
    "    while A!= sorted(A): # as long as the list is not sorted\n",
    "        random.shuffle(A) #shuffle the list\n",
    "        if A == sorted(A): #if the list is sorted\n",
    "            return(A) # return the list\n",
    "            break # and stop\n",
    "        else: #if the list is not sorted yet\n",
    "            continue #keep going\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "09c3f02f46b5ba86c3aa80498b9c8c34",
     "grade": true,
     "grade_id": "cell-ff4db3a3e8b04515",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "# Please ignore this cell. This cell is for us to implement the tests \n",
    "# to see if your code works properly. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "18d2bd43c2db165cb6806cb1e14df4f1",
     "grade": false,
     "grade_id": "cell-3ffcfdae9ec3ea41",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 1b.\n",
    "What is the best case complexity of this algorithm?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "76bf94004078f73d21791758ac6db72b",
     "grade": true,
     "grade_id": "cell-afac80171b3b6232",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "#### The best case complexity of this algorithm has two possibilities:\n",
    "\n",
    "1- If we input a list that has one element only (because it's sorted be definition)\n",
    "\n",
    "2- If we input a sorted list\n",
    "\n",
    "The complexity of the best case will be O(1) --> constant time that doesn't depend on the input size as the algorithm won't execute the while loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1b1210d5a27f9933086d0f3a0d234361",
     "grade": false,
     "grade_id": "cell-d98018127b7e79f4",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 1c.\n",
    "\n",
    "What is the average case complexity?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "97d1e74314efdae93ea73d510e233468",
     "grade": true,
     "grade_id": "cell-9d52d34daa1e3478",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The complexity of this algorithm varies depending on the input size and the distribution of the list (is the list semi sorted? or is it in reverse order?) \n",
    "\n",
    "-So, if we have a list with three or four elements that are semi sorted, we might reach the average case complexity, but again it varies depending on the random.shuffle to generate the lucky results.\n",
    "\n",
    "-The expected value for average case would be 1/n! since n! factorial represents the possible permutation of the elements in the list.\n",
    "\n",
    "-That would result in average case complexity of O(n!) which is the worst among the other average cases complexities of other sort algorithms. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "fdbf5403114d2a68085e8172d0122685",
     "grade": false,
     "grade_id": "cell-d6d8ad45088488eb",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 1d.\n",
    "\n",
    "For what size lists is this a feasible method?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "080a5eecbe3afcffed278b7cbba7f51a",
     "grade": true,
     "grade_id": "cell-ab40f08768579798",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Theoretically, the algorithm can sort any list of any given size. Practically, the algorithm might take ages to sort a list of hundreds or thousands of elements. For instance, I tried a list that contains ten unsorted elements, and the algorithm took more than 5 minutes to execute. This example shows that even for a given list with sizes as small as 5 or 6 elements, it's not feasible or efficient to use this algorithm.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "cbe19c6348c19b5df04e84b537f6ebf0",
     "grade": false,
     "grade_id": "cell-56ae4e75a4086ee8",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### [Optional] Question 1e.\n",
    "\n",
    "Can you think of an even worse sorting method? In such a case, what would its complexity be? How big a list could you sort?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "564b860df18fb1bb2fc987ec4240f98d",
     "grade": true,
     "grade_id": "cell-ac05806942341926",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c8d4696c279cfb37108a84fdde271057",
     "grade": false,
     "grade_id": "cell-16012d2af0ef00ec",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "Approximate median finder. Given a list and δ (a number between 0 and 0.5), the approximate median finder function returns a number that is guaranteed to lie between the (50-δ/2)% and (50+δ/2)% percentiles. Implement such a function by randomly selecting an element from the list and testing whether or not it lies within the bounds. If it doesn’t then retry with a new random element, but only a limited number of retries are allowed (you decide the maximum number of retries.)\n",
    "\n",
    "### Question 2a.\n",
    "Complete the following function\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9ce93a3c3e022b8a93a85566123df36f",
     "grade": false,
     "grade_id": "cell-2ab65512a6148d3c",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np #import numpy library\n",
    "def check_approx_med(A, num, delta): #define the function that takes three arguments \n",
    "    mx = int(np.percentile(A, 0.5+ delta/2)) # the right bound value\n",
    "    mn= int(np.percentile(A,0.5-delta/2)) # the left bound value\n",
    "     \n",
    "    if num>=mn and num<=mx: #determine if the number inputed is within the boundaris of the percentile\n",
    "        return True \n",
    "    else:\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e36da35c2400ca389ff7bb609167a787",
     "grade": true,
     "grade_id": "cell-df56d7433abb6517",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-5-aa1f56e94d4b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcheck_approx_med\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m.25\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcheck_approx_med\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;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m.25\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;32mFalse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "assert(check_approx_med([0,1], 0, .25) == True)\n",
    "assert(check_approx_med([0], 0, .25) == False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ea4f76410780e7134e2bc46fbe5663e9",
     "grade": false,
     "grade_id": "cell-18a16dfd102f137c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 2b.\n",
    "Complete the following function that makes use of `check_approx_med` above.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2b3cfdf82e0efce4078cc52b3680f7be",
     "grade": false,
     "grade_id": "cell-e19685b545147dde",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import random \n",
    "\n",
    "def approx_med_finder(A, delta):\n",
    "    for trial in range(int(100//delta)): # iterate through the following lines of code (100//delta) times\n",
    "        x = random.choice(A) #pick a random number from the list without removing that number from the last\n",
    "        return check_approx_med(A,x,delta)   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "77b77f7047dea39f9b7526a785f0e652",
     "grade": false,
     "grade_id": "cell-1863e0846b176982",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 2c.\n",
    "\n",
    "What is the probability of failure in each random trial? What is the probability of failure after all the allowed random trials? Does this scale with δ or N (the number of elements in a list)?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f7d6ed353a91d12d66b53a735d84f81b",
     "grade": true,
     "grade_id": "cell-efe7ab76f6a2546a",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The probability of failure depends on the value of the percentile which depends on the delta value inputed. As we increase the percentile, we get wider interval of the population distribution, which means there is higher chance of getting the number to fall within this interval. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a602a3cad0ff35029b447d00dcee6b6c",
     "grade": false,
     "grade_id": "cell-a41fe377076cd283",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 2d.\n",
    "Analyze the expected runtime of `approx_med_finder`. Note that because the function uses `check_approx_med`, you will most likely need to analyze the runtime of that function, too."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "255d88cf8e4f6ff8b3eb05cab2aa5f48",
     "grade": true,
     "grade_id": "cell-86b199798477fc2a",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "In the check_approx_med, we verify whether the number is within the boundaris or not. So, I think that would depend on the delta entered and the input size. Thus, for each trial the expected value of getting the num in the boundaris is 1/n. "
   ]
  }
 ],
 "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
}