Created
September 18, 2019 05:18
-
-
Save Verina-Armanyous/7b733fec0aef5fc865e3e957afcfcf68 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "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 | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "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 | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment