CS110 Session 2.2 PCW

CS110 Session 2.2 PCW.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": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = Feng Nian Tey (Steven)\n",
    "COLLABORATORS = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "c650e4f3477fb1b0666f4f7d1d7cfd38",
     "grade": false,
     "grade_id": "cell-a415b724e36aa852",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 2.2\n",
    "\n",
    "## Question 1 (Exercise 3.1-3 of Cormen, et al. )\n",
    "Explain why the statement, \"The running time of algorithm A is at least $O(n^2)$,\" is meaningless.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "d6f28cb6ab1a8f547f022f1932f609f9",
     "grade": true,
     "grade_id": "cell-437d61c1420d4f99",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "This is because the term $O(n^2)$, also known as the “big-O notation\", is used to give an upper bound on a function, to within a constant factor. In other words, $O(n^2)$ is the upper bound on the the worst-case running time for a particular function $g(n)$, and not the minimum running time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "def6c9c9f606feea2e7a711e51c65304",
     "grade": false,
     "grade_id": "cell-7d82282e0c8a03e3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2 (Exercise 3.1-4 of Cormen, et al. )\n",
    "\n",
    "Is $2^{n+1}=O(2^n)$? Is $2^{2n}=O(2^n)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9ea64ba2361ca4a6d09f468ddf82f39b",
     "grade": true,
     "grade_id": "cell-6a0c4ee19dadfddf",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "To solve this, we need to recall the definition of the big-O notation -  it is a function whose curve on a graph will always exceed the curve of the runtime after a certain point. In mathematical prose, it means that $f(n) = O(g(n))$ if and only if there are positive constants $c$ and $k$, such that $0 ≤ f(n) ≤ cg(n)$ for all $n ≥ k$. The values of the constants $c$ and k must be fixed for the function f and must not depend on n.\n",
    "\n",
    "In the first equation, $2^{n+1}=O(2^n)$, we can factorize the LHS of the equation to:\n",
    "\n",
    "<div style=\"text-align:center\">$2\\times2^{n}=O(2^n)$</div>\n",
    "\n",
    "Here, we can see that the \"$2$\" that we factorized out is a constant term, and therefore, we can multiply the $2^n$ term on the RHS by any constant and it can either be equal or bigger than the LHS.\n",
    "\n",
    "In other words, with $c = 2$ and $k = 1$, we have $2\\times2^n \\geq 2^{n+1}$ for all $n \\geq 1$. Therefore , $2^{n+1}=O(2^n)$.\n",
    "\n",
    "As for the second example, $2^{2n}=O(2^n)$, we can once again factorize the LHS of the equation to:\n",
    "\n",
    "<div style=\"text-align:center\">$2^{n\\times n}=O(2^n)$</div>\n",
    "<div style=\"text-align:center\">$2^{n}\\times2^{n}=O(2^n)$</div>\n",
    "\n",
    "Here, we can see that the \"$c$\" term, $2^{n}$ is not a constant, and therefore, even if we multiplied $2^n$ term on the RHS by any constant, it might still be smaller than the LHS. Thus, $2^{2n}\\neq O(2^n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b7ea4393551187246e7a7a7399d38250",
     "grade": false,
     "grade_id": "cell-e4fe88238c9e912a",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "Write a function in Python that solves the maximum-subarray problem using a brute-force approach. Your Python function must:\n",
    "* Take as Input an array/list  of numbers\n",
    "* Produce the following Output: \n",
    "    * the start and end indices of the subarray containing the maximum sum.\n",
    "    * value of the maximum subarray (float)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "c98e89c42d52953c5e460a0126592e2a",
     "grade": false,
     "grade_id": "cell-527e6532d6992fd0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 3, 2)\n"
     ]
    }
   ],
   "source": [
    "list = []\n",
    "def bruteforce_max_subarray(A):\n",
    "    \"\"\"Implements brute-force maximum subarray finding.\n",
    "    \n",
    "    Inputs:\n",
    "    - A: a NON-EMPTY list of floats \n",
    "    \n",
    "    Outputs: A tuple of\n",
    "    - the start index of the max subarray\n",
    "    - the end index of the max subarray\n",
    "    - the value of the maximum subarray\n",
    "    \"\"\"\n",
    "    for i in range (0, len(A)): #iterates through the list from the first number to the last\n",
    "        for j in range (i+2, len(A)+1): #same as the previous step, but this iterates from the term to the ith term \n",
    "                                        #to the last term in the list\n",
    "            list.append(sum(A[i:j])) #add the list of sums to a list\n",
    "    \n",
    "    for i in range (0, len(A)): #iterate again\n",
    "        for j in range (i+2, len(A)+1):\n",
    "            if sum(A[i:j]) == max(list): #find the pair of integers in the list that give the biggest sums\n",
    "                return i, j-1, sum(A[i:j]) #return the index of said integers, as well as the sum\n",
    "\n",
    "A = [-2,1,-1,2,-5]\n",
    "print(bruteforce_max_subarray(A))\n",
    "\n",
    "# I acknowledge that there might be limitations of this algorithm that I created - for example, if the list was\n",
    "# [-1, -1, -1, 2, -1, -1], the algorithm will return \"None\" because it won't be able to find the maximum difference \n",
    "# since there are multiple of them. We would need to add a contingency by using an if statement in order to prevent\n",
    "# anything like this from happening."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "57ec4672631bc8d61833077d1977b3e3",
     "grade": true,
     "grade_id": "cell-a28a56466c9537ff",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(bruteforce_max_subarray([-2,1,-1,2,-5]) == (1, 3, 2))\n",
    "assert(bruteforce_max_subarray([-2, -5, 6, -2, -3, 1, 5, -6]) == (2, 6, 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(bruteforce_max_subarray([-2, -5, 6, -2, -3, 1, 5, -6]) == (2, 6, 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8625e044853f9c85838ca9f6ca4db9c4",
     "grade": false,
     "grade_id": "cell-ba342b15913cb4d3",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4. \n",
    "Test your Python maximum-subarray function using the following input list (from Figure 4.3 of Cormen et al.):  \n",
    "`A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7] `\n",
    "\n",
    "If your Python implementation is correct, your code must return: \n",
    "* 43 - which is the answer to the maximum subarray problem, and \n",
    "* <7, 10> -the start and the end indices of the max subarray. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9084301761509ba09820ee55035fd115",
     "grade": true,
     "grade_id": "cell-e4a632ce0edc1697",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(7, 10, 43)\n"
     ]
    }
   ],
   "source": [
    "list = []\n",
    "def bruteforce_max_subarray(A):\n",
    "    \"\"\"Implements brute-force maximum subarray finding.\n",
    "    \n",
    "    Inputs:\n",
    "    - A: a NON-EMPTY list of floats\n",
    "    \n",
    "    Outputs: A tuple of\n",
    "    - the start index of the max subarray\n",
    "    - the end index of the max subarray\n",
    "    - the value of the maximum subarray\n",
    "    \"\"\"\n",
    "    for i in range (0, len(A)):\n",
    "        for j in range (i+2, len(A)+1):\n",
    "            list.append(sum(A[i:j]))\n",
    "    \n",
    "    for i in range (0, len(A)):\n",
    "        for j in range (i+2, len(A)+1):\n",
    "            if sum(A[i:j]) == max(list):\n",
    "                return i, j-1, sum(A[i:j])\n",
    "\n",
    "A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n",
    "print(bruteforce_max_subarray(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "e99f275368a5231d3692d72e62ad372d",
     "grade": false,
     "grade_id": "cell-345f6f0bc7b4e001",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 5. Asymptotic notation. \n",
    "Complete the following table using the asymptotic notation that best describes the problem. For example, if both $O(n^3)$ and $O(n)$ are possible for an algorithm, the answer is $O(n)$ because the function $f(n) = O(n)$ provides a tighter and more accurate fit; if both $O(n)$ and $\\Theta(n)$ are possible, the correct answer is $\\Theta(n)$ because $\\Theta(n)$ provides both information about the upper and lower bound, thus it is more accurate than $O(n)$.\n",
    "\n",
    "You should copy the following table and paste and edit it in the cell below. \n",
    "\n",
    "Algorithm | Big Oh ($O$) | Big Theta ($\\Theta$)\n",
    "--- | --- | ---\n",
    "Insertion sort |  |\n",
    "Selection sort |  |\n",
    "Bubble sort |  | \n",
    "Finding maximum subarray |  |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "6a2e8546bb697eda40015086f8405788",
     "grade": true,
     "grade_id": "cell-247c51df276b622e",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "Algorithm | Big Oh ($O$) | Big Theta ($\\Theta$)\n",
    "--- | --- | ---\n",
    "Insertion sort |$O(n^2)$ | $\\Theta(n^2)$\n",
    "Selection sort | $O(n^2)$ |$\\Theta(n^2)$\n",
    "Bubble sort |$O(n^2)$  | $\\Theta(n^2)$\n",
    "Finding maximum subarray* |$O(n^2)$/$O(n^3)$ |$\\Theta(n^2)$/$\\Theta(n^3)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:center\">* values for Finding maximum subarray might differ based on the amount of nested for loops that are used.</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "033981aff08a9064f5553137db1a4841",
     "grade": false,
     "grade_id": "cell-9e53f43b4530cd79",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## [Optional] Question 6. \n",
    "How can you change this code to make it find the minimum-subarray?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "462bcec4b06cc6fbda0e34c29e30b1fb",
     "grade": false,
     "grade_id": "cell-f4553f71858d1bc4",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 4, -5)\n"
     ]
    }
   ],
   "source": [
    "list = []\n",
    "def bruteforce_min_subarray(A):\n",
    "    \"\"\"Implements brute-force minimum subarray finding.\n",
    "    \n",
    "    Inputs:\n",
    "    - A: a NON-EMPTY list of floats\n",
    "    \n",
    "    Outputs: A tuple of\n",
    "    - the start index of the min subarray\n",
    "    - the end index of the min subarray\n",
    "    - the value of the minimum subarray\n",
    "    \"\"\"\n",
    "    for i in range (0, len(A)):\n",
    "        for j in range (i+2, len(A)+1):\n",
    "            list.append(sum(A[i:j]))\n",
    "    \n",
    "    for i in range (0, len(A)):\n",
    "        for j in range (i+2, len(A)+1):\n",
    "            if sum(A[i:j]) == min(list):\n",
    "                return i, j-1, sum(A[i:j])\n",
    "\n",
    "A = [-2,1,-1,2,-5]\n",
    "print(bruteforce_min_subarray(A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "70322c36cf22b5f720e6c338f08925c2",
     "grade": true,
     "grade_id": "cell-4263c7494a5f09d3",
     "locked": true,
     "points": 0,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "assert(bruteforce_min_subarray([1]*10)[0] == bruteforce_min_subarray([1]*10)[1])\n",
    "assert(bruteforce_min_subarray([1]*10)[2] == 1)"
   ]
  }
 ],
 "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
}