{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

cs1001.py , Tel Aviv University, Spring 2019

\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Code for printing several outputs in one cell (not part of the recitation):" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "from IPython.core.interactiveshell import InteractiveShell\n", "InteractiveShell.ast_node_interactivity = \"all\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution to the question on Linked lists" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[a(2302773147072), b(2302773147016), c(2302773146960)]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Node():\n", " def __init__(self, val):\n", " self.value = val\n", " self.next = None\n", " \n", " def __repr__(self):\n", " #return str(self.value)\n", " \n", " #for today's recitation, we print the id of self as well\n", " return str(self.value) + \"(\" + str(id(self))+ \")\"\n", "\n", "\n", "class Linked_list():\n", "\n", " def __init__(self, seq=None):\n", " self.next = None\n", " self.len = 0\n", " if seq != None:\n", " for x in seq[::-1]:\n", " self.add_at_start(x)\n", " \n", "\n", " def __repr__(self):\n", " out = \"\"\n", " p = self.next\n", " while p != None :\n", " out += str(p) + \", \" # str(p) envokes __repr__ of class Node\n", " p = p.next\n", " return \"[\" + out[:-2] + \"]\"\n", "\n", " \n", " def __len__(self):\n", " ''' called when using Python's len() '''\n", " return self.len\n", " \n", " \n", " def add_at_start(self, val):\n", " ''' add node with value val at the list head '''\n", " p = self\n", " tmp = p.next\n", " p.next = Node(val)\n", " p.next.next = tmp\n", " self.len += 1\n", " \n", " def add_at_end(self, val):\n", " ''' add node with value val at the list tail '''\n", " p = self\n", " while (p.next != None):\n", " p = p.next\n", " p.next = Node(val)\n", " self.len += 1\n", " \n", " \n", " def insert(self, loc, val):\n", " ''' add node with value val after location 0<=locq is p==True. In such a case we call $p$ a joint node.\n", "\n", "\n", "\n", "\n", "\n", "a) Write a function are_merged that gets two linked lists as an input and returns True iff the lists merge. \n", "\n", "\n", "The main idea - two linked lists merge if and only if their last node (their tail) is the same node." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "def are_merged(L, K):\n", " node_l = L.next\n", " node_k = K.next\n", " while node_l.next != None:\n", " node_l = node_l.next\n", " while node_k.next != None:\n", " node_k = node_k.next\n", " return node_k is node_l\n", " \n", " #Here is an equivalent solution with a shorter code:\n", " #last_node_l = L[len(L)-1]\n", " #last_node_k = K[len(K)-1]\n", " #return last_node_l is last_node_k\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[a(2302773149144), b(2302773149088), c(2302773149032), d(2302773148976)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[e(2302772881560), c(2302773149032), d(2302773148976)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[d(2302773149312)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" }, { "name": "stdout", "output_type": "stream", "text": [ "True\n", "False\n" ] } ], "source": [ "L = Linked_list(\"abcd\")\n", "L\n", "\n", "K = Linked_list()\n", "K.next = L.next.next.next\n", "# Manually define the length of K\n", "K.len = 2\n", "K.add_at_start(\"e\")\n", "K\n", "\n", "M = Linked_list()\n", "M.add_at_start(\"d\")\n", "M\n", "\n", "print(are_merged(L,K))\n", "print(are_merged(L,M))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "time and space complexity:\n", "\n", "Space: Saving a pointer to two nodes can be done in $O(1)$ memory \n", "\n", "Time: Each node in the lists is read exactly once and all operations run in time $O(1)$ so runtime is $O(n+m)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, write a function find_shared that gets two merged linked lists as an input and returns the first joint node of the lists.\n", "\n", "B) find_shared_1(L,K) should have time complexity: expected $O(max(m,n))$, and space complexity $O(min(m,n))$" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "def find_shared_1(L, K):\n", " id_set = set()\n", " p = L.next if len(L) < len(K) else K.next\n", " while p != None:\n", " id_set.add(id(p))\n", " p = p.next\n", " q = K.next if len(L) < len(K) else L.next\n", " while q != None:\n", " if id(q) in id_set:\n", " return q\n", " q = q.next\n", " return None # should not reach here since L, K have joint items\n" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "c(2302773149032) True\n" ] } ], "source": [ "x = K.next.next\n", "print(find_shared_1(L,K), find_shared_1(L,K) == x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suppose that $L$ is not shorter than $K$. That is, $n\\leq m$.\n", "\n", "Space: Saving all of the node ids from $L$ in a set: $O(n) = O(min(n,m))$, saving one or two node pointers at a time is $O(1)$\n", "\n", "Time: All lookups in the set run in $O(1)$ on average, apart from that each node in $K,L$ is read exactly once. Therefore, the expected time complexity $O(m) = O(max(n,m))$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C) find_shared_2(L,K) should have time complexity: $O(max(m,n))$, and space complexity $O(max(\\log m,\\log n))$" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "def find_shared_2(L, K):\n", " n = len(L)\n", " m = len(K)\n", " p = L.next\n", " q = K.next\n", " for i in range(max(0, n-m)):\n", " p = p.next\n", " for i in range(max(0, m-n)):\n", " q = q.next\n", " while p != None:\n", " if p is q:\n", " return p\n", " p = p.next\n", " q = q.next\n", " return None # Should never get here" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "c(2302773149032) True\n" ] } ], "source": [ "x = K.next.next\n", "print(find_shared_2(L,K), find_shared_1(L,K) == x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Space: Saving $n,m$ and an index for the for loop: $O(max (\\log n, \\log m))$, saving one or two node pointers at a time is $O(1)$\n", "\n", "Time: First two for loops and the while loop traverse each node in $K,L$ exactly once - $O(n+m) = O(max(n,m))$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "D) find_shared_3(L,K) should have time complexity: $O(max(m,n))$, and space complexity $O(1)$ (better than $O(min(m,n))$, as was written in the requirement...)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "def find_shared_3(L, K):\n", " p = L.next\n", " q = K.next\n", " while p != None and q != None:\n", " if p is q:\n", " return p\n", " p = p.next\n", " q = q.next\n", " if p == None:\n", " p = K.next\n", " if q == None:\n", " q = L.next\n", " return None # must end before, since L, K have joint items \n" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "c(2302773149032) True\n" ] } ], "source": [ "x = K.next.next\n", "print(find_shared_3(L,K), find_shared_1(L,K) == x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Space: Saving one or two node pointers throughout the while loop is $O(1)$\n", "\n", "Time: Pointer $p$ will first traverse the $n$ nodes of $L$ and then the $m$ nodes of $K$. Pointer $q$ will first traverse the $m$ nodes of $K$ and then the $n$ nodes of $L$. Suppose that the joint part is of length $w$, then both pointers will reach it after $n+m−w$ steps. Since all operations in the while loop run in $O(1)$ time, the overall running time is $O(max(n,m))$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solution to the object oriented question " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Basic polynomial class\n", "We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, let's implement evaluate and degree methods" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "6" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", "\n", "f = Polynomial([1, 1])\n", "f.degree()\n", "f.evaluate(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Adding the __derivative__ method that returns a new Polynomial object" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3*x^0) + (8*x^1)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", "\n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", "\n", "g = Polynomial([2, 3, 4])\n", "r = g.derivative()\n", "r" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we would like to implement \\_\\_eq__ method such that the following test using == operator returns True rather than False.\n", "Without it, Pthon compares the __id__ of the two objects." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = Polynomial([1,0,1])\n", "q = Polynomial([1,0,1])\n", "p == q" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", " \n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", "f = Polynomial([1, 1])\n", "f2 = Polynomial([1, 1])\n", "g = Polynomial([2, 3, 4])\n", "\n", "f == g\n", "f == f2\n", "f.__eq__(f2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Implementing \\_\\_add__ method: making sure that the resulting polynomial does not have leading zeros" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3*x^0) + (31*x^1) + (4*x^2)" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(3*x^0) + (32*x^1)" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", " \n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, Polynomial) \n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms) - 1\n", " while last > 0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", "f = Polynomial([1, 1])\n", "g = Polynomial([2, 30, 4])\n", "r = f + g\n", "r\n", "f1 = Polynomial([1, 2, -4])\n", "g1 = Polynomial([2, 30, 4])\n", "r1 = f1 + g1\n", "r1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Implementing \\_\\_mul__" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(3*x^0) + (4*x^1) + (28*x^2) + (40*x^3) + (-20*x^4)" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", " \n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, Polynomial) \n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms) - 1\n", " while last > 0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " def __mul__(self, other):\n", " assert isinstance(other, Polynomial) \n", " terms = [0 for i in range(1 + self.degree()+other.degree())]\n", " for i, c1 in enumerate(self.coeffs):\n", " for j, c2 in enumerate(other.coeffs):\n", " terms[i+j] += c1*c2\n", " return Polynomial(terms)\n", "\n", "p = Polynomial([3,4,-2])\n", "g = Polynomial([1,0, 10])\n", "r = p * g\n", "r" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Implementing \\_\\_neg__" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-3*x^0) + (-4*x^1) + (2*x^2)" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", " \n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, Polynomial) \n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms) - 1\n", " while last > 0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " def __mul__(self, other):\n", " assert isinstance(other, Polynomial) \n", " terms = [0 for i in range(1 + self.degree()+other.degree())]\n", " for i, c1 in enumerate(self.coeffs):\n", " for j, c2 in enumerate(other.coeffs):\n", " terms[i+j] += c1*c2\n", " return Polynomial(terms)\n", "\n", " def __neg__(self):\n", " return Polynomial([-co for co in self.coeffs])\n", "\n", "p = Polynomial([3,4,-2])\n", "-p" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Implementing \\_\\_sub__:\n", "Using the fact we already have \\_\\_neg__ and \\_\\_add__ we define $f−g=f+(−g)$" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-7*x^0) + (3*x^1)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", " \n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, Polynomial) \n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms) - 1\n", " while last > 0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " def __mul__(self, other):\n", " assert isinstance(other, Polynomial) \n", " terms = [0 for i in range(1 + self.degree()+other.degree())]\n", " for i, c1 in enumerate(self.coeffs):\n", " for j, c2 in enumerate(other.coeffs):\n", " terms[i+j] += c1*c2\n", " return Polynomial(terms)\n", "\n", " def __neg__(self):\n", " return Polynomial([-co for co in self.coeffs])\n", "\n", " def __sub__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return (self + (-other))\n", " \n", "\n", "p = Polynomial([3,4,0,5])\n", "q = Polynomial([10,1,0,5])\n", "r = p-q\n", "r" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Tests:" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(6*x^3)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(-6*x^3)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "3" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(3*x^0) + (-4*x^1) + (1*x^2)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "63" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(-4*x^0) + (2*x^1)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(2*x^0)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "False" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(3*x^0) + (-4*x^1) + (1*x^2) + (6*x^3)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(2*x^0) + (-4*x^1) + (1*x^2)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "True" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(-3*x^0) + (4*x^1) + (-1*x^2)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(3*x^0) + (-4*x^1) + (1*x^2) + (-6*x^3)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "(18*x^3) + (-24*x^4) + (6*x^5)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "0" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "[1]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "q = Polynomial([0, 0, 0, 6])\n", "q\n", "Polynomial([0, 0, 0, -6])\n", "q.degree()\n", "p = Polynomial([3, -4, 1])\n", "p\n", "p.evaluate(10)\n", "dp = p.derivative()\n", "dp\n", "ddp = p.derivative().derivative()\n", "ddp\n", "q == p\n", "r = p+q\n", "r\n", "p + Polynomial([-1])\n", "q == Polynomial([0, 0, 0, 5]) + Polynomial([0, 0, 0, 1])\n", "-p\n", "p-q\n", "p*q\n", "Polynomial([0])*p\n", "q = Polynomial([0, 0, 0, 6])\n", "mq = Polynomial([1, 0, 0, -6])\n", "z = q + mq\n", "z.coeffs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Adding __find_root__ method" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3.0000000003611356" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "3.0" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" }, { "data": { "text/plain": [ "0.9999999999598665" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\n", "\n", "class Polynomial():\n", " def __init__(self, coeffs):\n", " self.coeffs = coeffs\n", "\n", " def __repr__(self):\n", " terms = [\" + (\" + str(self.coeffs[k]) + \"*x^\" + \\\n", " str(k) + \")\" \\\n", " for k in range(len(self.coeffs)) \\\n", " if self.coeffs[k] != 0]\n", " terms = \"\".join(terms)\n", " if terms == \"\":\n", " return \"0\"\n", " else:\n", " return terms[3:] #discard leftmost '+'\n", "\n", " def degree(self):\n", " return len(self.coeffs) - 1\n", "\n", " def evaluate(self, x):\n", " result = 0\n", " for i in range(1, len(self.coeffs)+1):\n", " result = result*x + self.coeffs[-i]\n", " return result\n", " \n", " def derivative(self):\n", " coeffs = [0 for i in range(len(self.coeffs)-1)]\n", " for i in range(1,len(self.coeffs)):\n", " coeffs[i-1] = self.coeffs[i]*i\n", " return Polynomial(coeffs)\n", " \n", " def __eq__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return self.coeffs == other.coeffs\n", "\n", " def __add__(self, other):\n", " assert isinstance(other, Polynomial) \n", " size = min(self.degree(), other.degree()) + 1\n", " terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]\n", " terms += self.coeffs[size : self.degree() + 1]\n", " terms += other.coeffs[size : other.degree() + 1]\n", " #remove leading zeros\n", " last = len(terms) - 1\n", " while last > 0 and terms[last] == 0:\n", " last -= 1\n", " return Polynomial(terms[:last+1])\n", "\n", " def __mul__(self, other):\n", " assert isinstance(other, Polynomial) \n", " terms = [0 for i in range(1 + self.degree()+other.degree())]\n", " for i, c1 in enumerate(self.coeffs):\n", " for j, c2 in enumerate(other.coeffs):\n", " terms[i+j] += c1*c2\n", " return Polynomial(terms)\n", "\n", " def __neg__(self):\n", " return Polynomial([-co for co in self.coeffs])\n", "\n", " def __sub__(self, other):\n", " assert isinstance(other, Polynomial) \n", " return (self + (-other))\n", " \n", " def find_root(self):\n", " return NR(lambda x:self.evaluate(x), lambda x: self.derivative().evaluate(x))\n", "\n", "p = Polynomial([3, -4, 1])\n", "p.find_root()\n", "p.find_root()\n", "p.find_root()\n", " \n", " \n", " \n" ] }, { "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.2" } }, "nbformat": 4, "nbformat_minor": 1 }