Skip to content

Instantly share code, notes, and snippets.

@steven-tey

steven-tey/CS110 Session 3.1 Pre-Class Work.ipynb

Last active September 23, 2019 17:22
Show Gist options
  • Save steven-tey/38e5b4efc6fdd1bb5b1a810d34006363 to your computer and use it in GitHub Desktop.
Save steven-tey/38e5b4efc6fdd1bb5b1a810d34006363 to your computer and use it in GitHub Desktop.
Download ZIP
CS110 Session 3.1 Pre-Class Work
Display the source blob
Display the rendered blob
Raw
CS110 Session 3.1 Pre-Class Work.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 = Steven Tey\n",
"COLLABORATORS = "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "6eb33d4bbb91bdad042e00eb02fae1ad",
"grade": false,
"grade_id": "cell-f941f4ddd5e342f7",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"# CS110 Pre-class Work 3.1\n",
"\n",
"## Question 1. \n",
"Paste in your Python implementation of the maximum subarray from the previous class in the cell below and use that to find out the value of the maximum subarray of this array: `A = [-2, -3, 4, -1, -2, 1]`"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "6c4991e90ad8cdfb8cf42529b7e5edd6",
"grade": true,
"grade_id": "cell-e69c8bbcd40ca242",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The value of the maximum subarray of A is 4.\n"
]
}
],
"source": [
"list = []\n",
"def bruteforce_max_subarray(A):\n",
" \n",
" for i in range (0, len(A)):\n",
" for j in range (i+1, 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+1, len(A)+1):\n",
" if sum(A[i:j]) == max(list):\n",
" return i, j-1, sum(A[i:j])\n",
"\n",
"A = [-2, -3, 4, -1, -2, 1]\n",
"print(f\"The value of the maximum subarray of A is {bruteforce_max_subarray(A)[2]}.\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "676f4558ca97298a50665d2b57563a54",
"grade": false,
"grade_id": "cell-6b2d39096ef80c67",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 2. \n",
"Now, your friend Joe comes and appends a single extra number at the end of the array, which becomes: `B = [-2, -3, 4, -1, -2, 1, 8]`. Do you have to re-run the entire maximum subarray again? Explain your answer. \n",
"The subsequent questions will help you figure out an efficient algorithmic strategy to address the last question, but make sure to write your explanation above first, before answering the remaining questions.\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "b848c0f0fa07252cc99055a801b12e47",
"grade": true,
"grade_id": "cell-d4b7cd845c816263",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"Since the number that is added to the subarray is bigger than the value of the maximum subarray, we will only need to run the bruteforce maximum subarray algorithm from the first term of the previous maximum subarray to the last new appended number. "
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "055be509a3fd9e61e64a6572949aa994",
"grade": false,
"grade_id": "cell-7280eecbaa455be1",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 3. \n",
"\n",
"**Determine if the following statement is True or False and explain your answer.**\n",
"If the maximum subarray of the array A is different than the maximum subarray of the array B (questions 1 and 2), the new maximum-subarray doesn’t need to include 8 (i.e., the newly appended element). \n"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "2b29f3c119737d73a7578e00d43972a4",
"grade": true,
"grade_id": "cell-9377964a8756f13b",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"False. If the new maximum subarray value is different, that means that the added term must have added all or some of its value to the new max-subarray value, and thus, the new maximum-subarray has to include the newly appended element, 8."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "461bf61cb22c2304f3988c6f34a901e8",
"grade": false,
"grade_id": "cell-e7cc711ccdade69f",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"## Question 4.\n",
"Complete the Python function `incremental_max_subarray(x, mx)` in the cell below.\n",
"\n",
"This [video](https://www.youtube.com/watch?v=AAgErqQmwmA&list=PLF_a-qBXTGFektoI6JUOTRL36JlvD04BR&index=4&t=0s) might be helpful to understand the `incremental_max_subarray` problem."
]
},
{
"cell_type": "code",
"execution_count": 98,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "ac3f0799ce4ff7159403a97b99cbb5bd",
"grade": false,
"grade_id": "cell-0230e459f3d701f8",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10\n"
]
}
],
"source": [
"def incremental_max_subarray(x, mx):\n",
" \"\"\" \n",
" Inputs:\n",
" - x: a NON-EMPTY list of numbers (e.g., the array B in the first two questions above). \n",
" * If x has 1 element: returns the value of the element regardless of the value of mx\n",
" - mx: the maximum subarray of x excluding its last element (i.e., compute the \n",
" maximum subarray of the input array x considering only its first len(x) - 1 elements)\n",
" \n",
" Output: The maximum subarray of the array x.\n",
" \n",
" For example, using the array B in question 2, the result of incremental_max_subarray(B, 4) \n",
" is 10 (10 = 8 + 1 - 2 -1 + 4). \n",
" \"\"\"\n",
" list = []\n",
" if (len(x)) == 1: #if there is only 1 number in the array, that number is the sum of the max subarray\n",
" return x[0]\n",
" else:\n",
" for i in range(1,len(x)+1): #iterating from 1 to the amount of numbers in the array\n",
" if sum(x[-i:])> mx: #counting backwards - if the sum of the last number, last two numbers,..., is > mx \n",
" list.append(sum(x[-i:])) # add that number to the list\n",
" else:\n",
" list.append(mx) #else, mx is still the sum of the max subarray\n",
" return max(list) \n",
" \n",
"print(incremental_max_subarray([-2, -3, 4, -1, -2, 1, 8], 4))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "70a3880be02d6f703dfa95229957e71f",
"grade": true,
"grade_id": "cell-9abf19e56620ffa3",
"locked": true,
"points": 1,
"schema_version": 1,
"solution": false
}
},
"outputs": [],
"source": [
"B = [-2, -3, 4, -1, -2, 1, 8]\n",
"assert(incremental_max_subarray(B, 4) == 10)\n",
"assert(incremental_max_subarray(B[:1], 0) == B[0])"
]
},
{
"cell_type": "code",
"execution_count": 100,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"True\n"
]
}
],
"source": [
"B = [-2, -3, 4, -1, -2, 1, 8]\n",
"print(incremental_max_subarray(B, 4) == 10)\n",
"print(incremental_max_subarray(B[:1], 0) == B[0])"
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "278d2e7036e916ce0fafffdd0c237584",
"grade": true,
"grade_id": "cell-bacebe71191cbd0f",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"YOUR ANSWER HERE"
]
},
{
"cell_type": "code",
"execution_count": 93,
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "d9cdd0a60c40e487e87d79d21915e36b",
"grade": false,
"grade_id": "cell-fd96d4ccccd99fe6",
"locked": false,
"schema_version": 1,
"solution": true
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10\n"
]
}
],
"source": [
"A = [-2, -3, 4, -1, -2, 1, 8]\n",
"def max_subarray(A):\n",
" \"\"\"\n",
" Using `incremental_max_subarray` iteratively on A to produce the value of the maximum\n",
" subarray of A.\n",
" \n",
" Inputs:\n",
" - A: a NON-EMPTY list of floats\n",
" \n",
" Outputs: flaot, the sum of the maximum subarray of A\n",
" \"\"\"\n",
" max_list = []\n",
" for x in range(0, len(A)): #iterating across the list from the first to the last element\n",
" max_list.append(incremental_max_subarray(A[:x+1],sum(A[:x]))) #applying the 'incremental_max_subarray'\n",
" #strategy iteratively across A to produce\n",
" #the maximum subarray of A\n",
" return max(max_list)\n",
" \n",
"print(max_subarray(A)) "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"checksum": "74149a9559625383203ec1320bff5558",
"grade": true,
"grade_id": "cell-669ad779766aa2c3",
"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": "03054d2ff22ec9310060ab534208ec0d",
"grade": false,
"grade_id": "cell-ae966fc92d098939",
"locked": true,
"schema_version": 1,
"solution": false
}
},
"source": [
"### Part 2.\n",
"Is this more efficient than the divide-and-conquer approach? Explain."
]
},
{
"cell_type": "markdown",
"metadata": {
"deletable": false,
"nbgrader": {
"checksum": "69eb86a7f05367f6396017910664f67d",
"grade": true,
"grade_id": "cell-cd8f0b130a7136db",
"locked": false,
"points": 0,
"schema_version": 1,
"solution": true
}
},
"source": [
"Based on the readings, we learned that the divide and conquer algorithm takes $nlogn$ time to complete.\n",
"\n",
"On the other hand, the incremental maximum subarray strategy above uses a recurrence relation, which can be denoted as follows:\n",
"\n",
"$T(n) = T(n-1) + n + c$\n",
"\n",
"The first step will take $T(n)$ time to calculate.\n",
"\n",
"Then, we as go one step down, the time taken will be $T(n-1)$ since we are taking away one term.\n",
"\n",
"Therefore, if you keep iterating, you'll get the final sum to be:\n",
"\n",
"$T(n) + T(n-1) + T(n-2) + ... + T(1)$\n",
"\n",
"This means that the total time needed for this strategy is $T(n+(n-1)+(n-2)+...1) = \\frac{1}{2}\n",
"n(n+1)$ = $\\Theta(n)$, which is smaller than $nlogn$.\n",
"\n",
"Therefore, this strategy is more efficient than the divide-and-conquer strategy."
]
}
],
"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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment