cs110_pcw_2_2.ipynb

gistfile1.txt

{
 "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": "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": [
    "Big O is the upper bound to a function, and it represents the worst case scenario of an algorithm. Saying that the running time of algorithm A is at least $O(n^2)$ doesn't reflect neither the upper bound part nor the worst case scenario. Moreoever the phrase \"at least\" expresses that the $O(n^2)$ is the lower bound of the algorithm (which is not true) because big O it supposed to be the upper bound.\n",
    "\n"
   ]
  },
  {
   "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": [
    "#### First: Is $2^{n+1}=O(2^n)$?\n",
    "\n",
    "let f(n) = $2^{n+1}$, g(n)= $2^n $\n",
    "\n",
    "by the definition of big O for that expression to hold true, we know that a constant multiplied by g(n) must be bigger than or equal f(n)\n",
    "\n",
    "$2^{n+1}$ <= $ c *2^n $\n",
    "\n",
    "and since n+1 is approximately equals n (because we can drop the constant), then $2^{n+1}=O(2^n)$ (TRUE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  Second: Is  $2^{2n}=O(2^n)$?\n",
    "$2^{2n}$= $2^{n} * 2^{n}$ \n",
    "\n",
    "so, $2^{n} * 2^{n}$ <= $C * 2^{n}$\n",
    "\n",
    "dividing both sides by $2^{n}$, we get $2^{n}$ <= $C$ which doesn't hold true as the left hand side will be greater\n",
    "\n",
    "Therefore, $2^{2n}=O(2^n)$ is FALSE\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": 2,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "c98e89c42d52953c5e460a0126592e2a",
     "grade": false,
     "grade_id": "cell-527e6532d6992fd0",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def bruteforce_max_subarray(A):\n",
    "    Max_sum = 0 #intialize the value of Max_sum\n",
    "    for i in range(len(A)):#iterate through each element in the list\n",
    "        for j in range(len(A)+1): #add (+1) to ensure we reach the very last element\n",
    "            if A[i:j]!=[]: #remove the empty subarrays\n",
    "                sum_subarray = sum(A[i:j]) #calculate the sum of the possible subarrays\n",
    "                if sum_subarray > Max_sum: #if the current sum is greater than the initial sum\n",
    "                    Max_sum = sum_subarray #give the value of the current sum to the Max_sum\n",
    "                    z =A[i:j] #the subarray that has the max sum\n",
    "                    start_index= A.index(z[0]) #the start index of the subarray containing the maximum sum\n",
    "                    end_index = A.index(z[-1]) #the end index of the subarray containing the maximum sum\n",
    "    return start_index, end_index, Max_sum #return a tuple with start, end index and max sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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": "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": 4,
   "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": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n",
    "bruteforce_max_subarray(A)\n"
   ]
  },
  {
   "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)$:brute force /$ O(nlogn)$: divide and conquer | $ \\Theta(n^2)$/$ \\Theta(nlogn)$"
   ]
  },
  {
   "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": 5,
   "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",
    "    Min_sum = 0 #intialize the value of Min_sum\n",
    "    starting_index=0\n",
    "    ending_index=0\n",
    "    z=0\n",
    "    for i in range(len(A)):#iterate through each element in the list\n",
    "        for j in range(len(A)+1): #add (+1) to ensure we reach the very last element\n",
    "            if A[i:j]!=[]: #remove the empty subarrays\n",
    "                sum_subarray = sum(A[i:j]) #calculate the sum of the possible subarrays\n",
    "                if sum_subarray < Min_sum: #if the current sum is greater than the initial sum\n",
    "                    Min_sum = sum_subarray #give the value of the current sum to the Min_Sum\n",
    "                    z =A[i:j] #the subarray that has the min sum\n",
    "                    starting_index= A.index(z[0])#the start index of the minimum subarray\n",
    "                    ending_index = A.index(z[-1])#the end index of the minimum subarray\n",
    "    return starting_index, ending_index, Min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 6, -50)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#testing if the code works \n",
    "#the code will return a tuple that contains the start index, the end index and the sum of the min subarray respectively\n",
    "A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n",
    "bruteforce_min_subarray(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "70322c36cf22b5f720e6c338f08925c2",
     "grade": true,
     "grade_id": "cell-4263c7494a5f09d3",
     "locked": true,
     "points": 0,
     "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-7-c46b6dc5626e>\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[0mbruteforce_min_subarray\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m10\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[0mbruteforce_min_subarray\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\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[0mbruteforce_min_subarray\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m1\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(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": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}