Skip to content

Instantly share code, notes, and snippets.

@Verina-Armanyous

Verina-Armanyous/cs110_pcw_2_2.ipynb

Created September 18, 2019 05:18
Show Gist options
  • Save Verina-Armanyous/7b733fec0aef5fc865e3e957afcfcf68 to your computer and use it in GitHub Desktop.
Save Verina-Armanyous/7b733fec0aef5fc865e3e957afcfcf68 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
cs110_pcw_2_2.ipynb
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Raw
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment