CS110. Pre-class work (1.2)

cs110_pcw_1_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Verina Armanyous\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "947eded9ca5fab593f017a71dd26277b",
     "grade": false,
     "grade_id": "cell-b46066345313bea6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 1.2\n",
    "\n",
    "\n",
    "\n",
    "## Question 1\n",
    "The following pseudocode has been extracted from Cormen et al. You should analyze the lines of the pseudocode trying to understand what every line in the pseudocode does and how many times is that line executed. \n",
    "![Insertion sort pseudo-code](insertionsort_pseudo.png)\n",
    "\n",
    "Answer the following questions: What does line 7 do? Why is it necessary?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "104f443d240e2139d778711f6bc0a766",
     "grade": true,
     "grade_id": "cell-3bac59ff24b11a27",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "\n",
    "i in line 4 initially represents the item to the left of the key. So as the comparison of i with the key is done, we move one step to the left to compare the rest of the items( to the left of the key) with the key. Line 7 does the previous by decreasing the index of the item compared by one each time. \n",
    "\n",
    "It also provides the termination of the code, or otherwise the while loop will continue to execute and compare infinitely only one element(the current value of i) to the key without moving forward to compare and sort other values to the left side of the key. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7872c2d656a6cb3aaeff2b4fa41eb204",
     "grade": false,
     "grade_id": "cell-0ca65d04b209f37f",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2\n",
    "The following Python code is an attempt to implement the Insertion-Sort pseudocode above. However, this code has a bug. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8e004cd5b12aee0ecf19786bc1a71d81",
     "grade": false,
     "grade_id": "cell-348fe9383ed7e0c7",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "def insertionSort(A):\n",
    "    for j in range(len(A)):\n",
    "        key = A[j]\n",
    "        i= j-1\n",
    "        while i >= 0 and A[i]>key:\n",
    "            A[i+1] = A[i]\n",
    "            i -= 1\n",
    "            A[i+1] = key\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "19a9183b993f6180d79385fed5dd07ee",
     "grade": false,
     "grade_id": "cell-16653cdc16be28b9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Copy and paste the code in the cell below. Identify and correct the bug. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7c22d14f97eaad956abf7dae17c7317f",
     "grade": false,
     "grade_id": "cell-1b7488e89cb501c5",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def insertionSort(A):\n",
    "    for j in range(1,len(A)):# the range should start from 1 so that we have the index zero item to compare with 1\n",
    "        #because if we start j from zero, i will be negative number, however I think it doesn't really matter because\n",
    "        # in line 5 the code ensures that there is no negative value to the i. \n",
    "        key = A[j]\n",
    "        i= j-1\n",
    "        while i >=0 and A[i]>key:\n",
    "            A[i+1] = A[i]\n",
    "            i -= 1\n",
    "        A[i+1] = key\n",
    "    return A\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4ff6145033c64da48f2a44f040b2c1b7",
     "grade": true,
     "grade_id": "cell-3432ce8ae2493fa6",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(insertionSort([0]) == [0])\n",
    "assert(insertionSort([-1,1]) == [-1,1])\n",
    "assert(insertionSort([1,-1]) == [-1,1])\n",
    "assert(insertionSort([1,6,3,6]) == [1,3,6,6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "a25900fe2fba8d1695b31865625ec1eb",
     "grade": false,
     "grade_id": "cell-1399c3a86cc2dd7c",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "How do you know this code works as intended now?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "4ff5af35daed9a5442ba229263bdde33",
     "grade": true,
     "grade_id": "cell-442998d5fdd8b561",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "assert() checks whether the condition is true or not. If the condition is true, it continues to excute without showing any error. If the condition is false, it shows an error. In that case, we are calling unsorted lists inside the insertionSort function that was created. By comparing the unsorted lists inside the insertionSort on the left hand side of the equality with the sorted lists to the right hand side of the equality, no error shows which means they are both equal in value. Thus, that means the insertionSort function has done its intended work which is sorting the unsorted list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "9d7a3b260b0fef93382fb52aa393f963",
     "grade": false,
     "grade_id": "cell-0ac1c20b43acb363",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3 \n",
    "Implement the bubble sort algorithm in the cell below. First, look up the corresponding pseudocode in Cormen et al. (page 40), and write a Python implementation for the bubble sort.  Like in the `insertionSort`,  your new Python function, `bubbleSort`, takes a list of elements as an argument and returns the sorted list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "16ff8874250907a794fdd3fa6c13bbec",
     "grade": false,
     "grade_id": "cell-b709733c96d8b615",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def bubbleSort(A):\n",
    "    n =len(A)\n",
    "    for i in range (n):\n",
    "        \n",
    "        for j in range (0,n-i-1):\n",
    "            tempA= A[j+1]\n",
    "            if A[j] > A[j+1]:\n",
    "                A[j+1] = A[j]\n",
    "                A[j] = tempA\n",
    "    return A\n",
    "            \n",
    "    raise NotImplementedError()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e7dc1709a92c6bcac7df39da1771e649",
     "grade": true,
     "grade_id": "cell-ffc9b251ea0047ba",
     "locked": true,
     "points": 2,
     "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": "eae899834db5b5ff1b2b1d67d8ef5929",
     "grade": false,
     "grade_id": "cell-60a96a427cd3e94e",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Is your program bug-free? Think of three different [“test cases”](https://www.hiredintech.com/classrooms/algorithm-design/lesson/83) to check the correctness of your code. If a code passes the tests you have just outlined, is this an unambiguous proof that the code is correct? Give your answer in the cell below. Feel free to use additional cells (Markdown or Code) as you wish."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "eb02c9951e19ee43d128fa93dd53eaad",
     "grade": true,
     "grade_id": "cell-5ecb51404140cb2f",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "The program is bug-free. The code was tested usiing three different types of tests: randomzied, sample and edge test. And it passed all of them.\n",
    "                                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# first test (randomized test)\n",
    "import random #import random module\n",
    "unsorted_list= [] #create empty list\n",
    "\n",
    "for i in range (0,10): # iterate through 10 items\n",
    "    unsorted_list.append(random.randrange(0,1000)) #add random items to the list\n",
    "sorted(unsorted_list)==bubbleSort(unsorted_list)\n",
    "#compare the built in function sorted - which creates a sorted copy of the list with the bubbleSort\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#second test (sample test):\n",
    "bubbleSort([3,20,2,100,-1])==bubbleSort([-1,100,2,20,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#third test(edge test):\n",
    "bubbleSort([])==bubbleSort([])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "cb0b8b9c4b153530d47b437baa24098d",
     "grade": false,
     "grade_id": "cell-b22dce6b32afe1a9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4\n",
    "The following pseudocode corresponds to a third sorting algorithm to be covered in Lesson 1.2, the selection sort.  Like in the previous step, write a Python implementation of the algorithm and make sure that your program is bug-free. `selectionSort` should take a list of elements as an argument and return the sorted list.\n",
    "\n",
    "![Selection sort pseudo-code](selectionsort_pseudo.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2f4365879ed0fd5b360bc25f4795c113",
     "grade": false,
     "grade_id": "cell-e04f94e5d418923c",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def selectionSort(A):\n",
    "    n=len(A)\n",
    "    for i in range(0, n-1):\n",
    "        minidx =i\n",
    "        for j in range(i+1, n):\n",
    "            if A[j]< A[minidx]:\n",
    "                A[j],A[i] = A[i], A[j]\n",
    "                   \n",
    "              \n",
    "    return A\n",
    "    \n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "352859ddf81204abd5eb3d91570919c7",
     "grade": true,
     "grade_id": "cell-ffe912ac7922de70",
     "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": "2305488ea190bf7b0347891f06164775",
     "grade": false,
     "grade_id": "cell-7ff8930bd7d30706",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "**Please make sure you try your best to code insertion sort, selection sort and bubble sort, and bring these programs to class. You will need them for a class activity.**"
   ]
  }
 ],
 "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
}