CS110 Session 1.2 PCW

CS110 Session 1.2 PCW

{
 "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\n",
    "COLLABORATORS = None"
   ]
  },
  {
   "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": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "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": 7,
   "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": 10,
   "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(len(A)): #scans the whole array A from first to last position\n",
    "        key = A[j] #the number under scrutiny\n",
    "        i= j-1 #the number before the number under scrutiny\n",
    "        while i >= 0 and A[i]>key: #the loop will keep going if the prev. no. is bigger than the no. under scrutiny\n",
    "            A[i+1] = A[i] #key switches places with the previous number\n",
    "            i -= 1 #keeps checking for the previous number to see if this condition is met or not\n",
    "        A[i+1] = key \n",
    "    return A\n",
    "#this while loop is what differs between an insertion sort and a bubble sort, as it allows the algorithm to \n",
    "#continuously compare the key to previous numbers until it is situated in the right position (where it is no longer\n",
    "#bigger than the previous number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "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": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "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\n",
    "\n",
    "print(insertionSort([0]) == [0])\n",
    "print(insertionSort([-1,1]) == [-1,1])\n",
    "print(insertionSort([1,-1]) == [-1,1])\n",
    "print(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": [
    "I tested it with the 4 examples that were given in the assert() functions and they all turned out to be true. "
   ]
  },
  {
   "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": 21,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "16ff8874250907a794fdd3fa6c13bbec",
     "grade": false,
     "grade_id": "cell-b709733c96d8b615",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def bubbleSort(A):\n",
    "    x = len(A)\n",
    "    for i in range(x):\n",
    "        for j in range(0, x-i-1):\n",
    "            if A[j] > A[j+1] :              \n",
    "                A[j+1], A[j] = A[j], A[j+1]\n",
    "    return A\n",
    "\n",
    "#Here, we are using for loops because we know exactly how long the list and how many positions we need to run the\n",
    "#algorithm through.\n",
    "\n",
    "print(bubbleSort([0]) == [0])\n",
    "print(bubbleSort([-1,1]) == [-1,1])\n",
    "print(bubbleSort([1,-1]) == [-1,1])\n",
    "print(bubbleSort([1,6,3,6]) == [1,3,6,6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": [
    "Like with the insertion sort algorithm, I ran the bubble sort algorithm with the 4 lines from the assert() section earlier and they turned out to be true."
   ]
  },
  {
   "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": 29,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "2f4365879ed0fd5b360bc25f4795c113",
     "grade": false,
     "grade_id": "cell-e04f94e5d418923c",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def selectionSort(A):\n",
    "    for i in range(len(A)): \n",
    "        smallest_number = i \n",
    "        for j in range(i+1, len(A)): \n",
    "            if A[smallest_number] > A[j]: \n",
    "                smallest_number = j \n",
    "      \n",
    "        A[i], A[smallest_number] = A[smallest_number], A[i]\n",
    "    \n",
    "    return A\n",
    "\n",
    "#Here, we are using for loops because we know exactly how long the list and how many positions we need to run the\n",
    "#algorithm through.\n",
    "\n",
    "print(selectionSort([0]) == [0])\n",
    "print(selectionSort([-1,1]) == [-1,1])\n",
    "print(selectionSort([1,-1]) == [-1,1])\n",
    "print(selectionSort([1,6,3,6]) == [1,3,6,6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}