CS110 Maximum Subarray

cs110_pcw_2_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": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Tiago Flora\"\n",
    "COLLABORATORS = [\"Ara Mkhoyan\", \"Chloe Gabrielle\", \"Cormen et al and the internet\"]"
   ]
  },
  {
   "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": [
    "The key of the issue with the statement lies on the words \"at least.\" <br>\n",
    "Big-Oh (O-) notation denotes the set of functions that express the maximum running time of an algorithm of input size n. Thus, when we say the running time $T(n)\\geq g(n)$, and $g(n)$ is a function in $O(n^2)$, we are comparing completely arbitrary terms. It could be that the function $g(n)$ used as reference is a constant, which would be $O(n^2)$, but would be obvious for large enough input sizes. In the clearest example, if we just said $T(n)$ is positive ($g(n)=0$), it states the obvious, and so we see that the statement is redundant."
   ]
  },
  {
   "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": [
    "### 1. $2^{n+1}$ \n",
    "\n",
    "Yes. To check whether $T(n)=2^{n+1}=O(2^n)$, we need to prove $0 \\leq 2^{n+1} \\leq c2^{n}$ for any $n\\geq n_0$. Since $2^n$ will be positive for any real value of n, we worry about the right side of the inequality. First, in the case $n=n_0$, we have:\n",
    "$$2^{n_0+1} = c2^{n_0} \\implies 2\\cdot 2^{n_0} = c2^{n_0}$$\n",
    "Since $2^{n_0}\\neq0$, we can divide both sides by it and we arrive at $c=2$. $n_0$, thus, is the smallest of the possible values it can assume. Given that $n_0 > 0$ is the only bound on its value, and $n_0$ is an integer, we have $n_0=1$. Thus, we conclude $T(n)=2^{n+1}=O(2^n)$.\n",
    "\n",
    "### 2. $2^{2n}$ \n",
    "\n",
    "No. Again, we need to prove $0 \\leq 2^{2n} \\leq c2^{n}$. We have:\n",
    "$$2^{2n} = 2^{n}\\cdot2^{n} \\leq c2^{n}$$ \n",
    "$$ \\therefore 2^{n}\\leq c $$\n",
    "It is impossible to get a constant that is asymptotically larger than $2^n$. Thus, $2^{2n} \\neq O(2^n) $\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": 99,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "c98e89c42d52953c5e460a0126592e2a",
     "grade": false,
     "grade_id": "cell-527e6532d6992fd0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "\n",
    "def bruteforce_max_subarray(A):\n",
    "    \"\"\"\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",
    "    maximum = -float(math.inf)\n",
    "    right_max = 0\n",
    "    left_max = 0\n",
    "    for i in range(len(A)):\n",
    "        # Every iteration of the loop will restart the sum of the subarray\n",
    "        subsum = 0\n",
    "        for j in range(i, len(A)):\n",
    "            subsum += A[j]\n",
    "            \"\"\"\n",
    "            Instead of changing the maximum subarray inside the if statement,\n",
    "            we can define it as max(subsum, maximum).\n",
    "            However, if we do this, we will get an AssertionError for the first test,\n",
    "            for the algorithm will choose to update the starting index of\n",
    "            the maximum subarray of the first assert test, which can be either 1 or 3.\n",
    "            \"\"\"\n",
    "#            maximum = max(subsum, maximum)\n",
    "            if maximum < subsum:\n",
    "                maximum = subsum\n",
    "                right_max = j\n",
    "                left_max = i\n",
    "    return((left_max, right_max, maximum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "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": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 3, 2) (2, 6, 7)\n"
     ]
    }
   ],
   "source": [
    "print(bruteforce_max_subarray([-2,1,-1,2,-5]), # The algorithm chooses A[1] as the starting point\n",
    "bruteforce_max_subarray([-2, -5, 6, -2, -3, 1, 5, -6]))"
   ]
  },
  {
   "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": 102,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9084301761509ba09820ee55035fd115",
     "grade": true,
     "grade_id": "cell-e4a632ce0edc1697",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(7, 10, 43)"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n",
    "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 |  | $\\Theta(n^2)$\n",
    "Selection sort |  | $\\Theta(n^2)$\n",
    "Bubble sort |  | $\\Theta(n^2)$\n",
    "Finding maximum subarray | $O(n^2)$ | "
   ]
  },
  {
   "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": 96,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "462bcec4b06cc6fbda0e34c29e30b1fb",
     "grade": false,
     "grade_id": "cell-f4553f71858d1bc4",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def bruteforce_min_subarray(A):\n",
    "    \"\"\"\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 min subarray\n",
    "    \"\"\"\n",
    "    minimum = float(math.inf)\n",
    "    right_min = 0\n",
    "    left_min = 0\n",
    "    for i in range(len(A)):\n",
    "        # Every iteration of the loop will restart the sum of the subarray\n",
    "        subsum = 0\n",
    "        for j in range(i, len(A)):\n",
    "            subsum += A[j]\n",
    "#            minimum = min(subsum, minimum)\n",
    "            if minimum > subsum:\n",
    "                minimum = subsum\n",
    "                right_min = j\n",
    "                left_min = i\n",
    "    return((left_min, right_min, minimum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 6, -50)"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bruteforce_min_subarray(A)"
   ]
  }
 ],
 "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
}