from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
class Node():
def __init__(self, val):
self.value = val
self.next = None
def __repr__(self):
#return str(self.value)
#for today's recitation, we print the id of self as well
return str(self.value) + "(" + str(id(self))+ ")"
class Linked_list():
def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:
self.add_at_start(x)
def __repr__(self):
out = ""
p = self.next
while p != None :
out += str(p) + ", " # str(p) envokes __repr__ of class Node
p = p.next
return "[" + out[:-2] + "]"
def __len__(self):
''' called when using Python's len() '''
return self.len
def add_at_start(self, val):
''' add node with value val at the list head '''
p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def add_at_end(self, val):
''' add node with value val at the list tail '''
p = self
while (p.next != None):
p = p.next
p.next = Node(val)
self.len += 1
def insert(self, loc, val):
''' add node with value val after location 0<=loc<len of the list '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1
def __getitem__(self, loc):
''' called when using L[i] for reading
return node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
return p
def __setitem__(self, loc, val):
''' called when using L[loc]=val for writing
assigns val to node at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self.next
for i in range(0, loc):
p = p.next
p.value = val
return None
def find(self, val):
''' find (first) node with value val in list '''
p = self.next
# loc = 0 # in case we want to return the location
while p != None:
if p.value == val:
return p
else:
p = p.next
#loc=loc+1 # in case we want to return the location
return None
def delete(self, loc):
''' delete element at location 0<=loc<len '''
assert 0 <= loc < len(self)
p = self
for i in range(0, loc):
p = p.next
# p is the element BEFORE loc
p.next = p.next.next
self.len -= 1
def insert_ordered(self, val):
''' assume self is an ordered list,
insert Node with val in order '''
p = self
q = self.next
while q != None and q.value < val:
p = q
q = q.next
newNode = Node(val)
p.next = newNode
newNode.next = q
self.len += 1
def find_ordered(self, val):
''' assume self is an ordered list,
find Node with value val '''
p = self.next
while p != None and p.value < val:
p = p.next
if p != None and p.value == val:
return p
else:
return None
ll = Linked_list("abc")
ll
[a(2302773147072), b(2302773147016), c(2302773146960)]
Let $L,K$ be two linked lists of length $n,m$, respectively. We say that the lists merge if there exists a node that is on both lists.
I.e. - there exists a node $q$ in $L$ and $p$ in $K$ such that q is p==True. In such a case we call $p$ a joint node.
a) Write a function are_merged that gets two linked lists as an input and returns True iff the lists merge.
The main idea - two linked lists merge if and only if their last node (their tail) is the same node.
def are_merged(L, K):
node_l = L.next
node_k = K.next
while node_l.next != None:
node_l = node_l.next
while node_k.next != None:
node_k = node_k.next
return node_k is node_l
#Here is an equivalent solution with a shorter code:
#last_node_l = L[len(L)-1]
#last_node_k = K[len(K)-1]
#return last_node_l is last_node_k
L = Linked_list("abcd")
L
K = Linked_list()
K.next = L.next.next.next
# Manually define the length of K
K.len = 2
K.add_at_start("e")
K
M = Linked_list()
M.add_at_start("d")
M
print(are_merged(L,K))
print(are_merged(L,M))
[a(2302773149144), b(2302773149088), c(2302773149032), d(2302773148976)]
[e(2302772881560), c(2302773149032), d(2302773148976)]
[d(2302773149312)]
True False
time and space complexity:
Space: Saving a pointer to two nodes can be done in $O(1)$ memory
Time: Each node in the lists is read exactly once and all operations run in time $O(1)$ so runtime is $O(n+m)$
Next, write a function find_shared that gets two merged linked lists as an input and returns the first joint node of the lists.
B) find_shared_1(L,K) should have time complexity: expected $O(max(m,n))$, and space complexity $O(min(m,n))$
def find_shared_1(L, K):
id_set = set()
p = L.next if len(L) < len(K) else K.next
while p != None:
id_set.add(id(p))
p = p.next
q = K.next if len(L) < len(K) else L.next
while q != None:
if id(q) in id_set:
return q
q = q.next
return None # should not reach here since L, K have joint items
x = K.next.next
print(find_shared_1(L,K), find_shared_1(L,K) == x)
c(2302773149032) True
Suppose that $L$ is not shorter than $K$. That is, $n\leq m$.
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)$
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))$.
C) find_shared_2(L,K) should have time complexity: $O(max(m,n))$, and space complexity $O(max(\log m,\log n))$
def find_shared_2(L, K):
n = len(L)
m = len(K)
p = L.next
q = K.next
for i in range(max(0, n-m)):
p = p.next
for i in range(max(0, m-n)):
q = q.next
while p != None:
if p is q:
return p
p = p.next
q = q.next
return None # Should never get here
x = K.next.next
print(find_shared_2(L,K), find_shared_1(L,K) == x)
c(2302773149032) True
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)$
Time: First two for loops and the while loop traverse each node in $K,L$ exactly once - $O(n+m) = O(max(n,m))$
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...)
def find_shared_3(L, K):
p = L.next
q = K.next
while p != None and q != None:
if p is q:
return p
p = p.next
q = q.next
if p == None:
p = K.next
if q == None:
q = L.next
return None # must end before, since L, K have joint items
x = K.next.next
print(find_shared_3(L,K), find_shared_1(L,K) == x)
c(2302773149032) True
Space: Saving one or two node pointers throughout the while loop is $O(1)$
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))$.
We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$
First, let's implement evaluate and degree methods
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
f = Polynomial([1, 1])
f.degree()
f.evaluate(5)
1
6
Adding the derivative method that returns a new Polynomial object
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
g = Polynomial([2, 3, 4])
r = g.derivative()
r
(3*x^0) + (8*x^1)
Now we would like to implement __eq__ method such that the following test using == operator returns True rather than False. Without it, Pthon compares the id of the two objects.
p = Polynomial([1,0,1])
q = Polynomial([1,0,1])
p == q
False
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
f = Polynomial([1, 1])
f2 = Polynomial([1, 1])
g = Polynomial([2, 3, 4])
f == g
f == f2
f.__eq__(f2)
False
True
True
Implementing __add__ method: making sure that the resulting polynomial does not have leading zeros
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, Polynomial)
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
f = Polynomial([1, 1])
g = Polynomial([2, 30, 4])
r = f + g
r
f1 = Polynomial([1, 2, -4])
g1 = Polynomial([2, 30, 4])
r1 = f1 + g1
r1
(3*x^0) + (31*x^1) + (4*x^2)
(3*x^0) + (32*x^1)
Implementing __mul__
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, Polynomial)
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
def __mul__(self, other):
assert isinstance(other, Polynomial)
terms = [0 for i in range(1 + self.degree()+other.degree())]
for i, c1 in enumerate(self.coeffs):
for j, c2 in enumerate(other.coeffs):
terms[i+j] += c1*c2
return Polynomial(terms)
p = Polynomial([3,4,-2])
g = Polynomial([1,0, 10])
r = p * g
r
(3*x^0) + (4*x^1) + (28*x^2) + (40*x^3) + (-20*x^4)
Implementing __neg__
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, Polynomial)
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
def __mul__(self, other):
assert isinstance(other, Polynomial)
terms = [0 for i in range(1 + self.degree()+other.degree())]
for i, c1 in enumerate(self.coeffs):
for j, c2 in enumerate(other.coeffs):
terms[i+j] += c1*c2
return Polynomial(terms)
def __neg__(self):
return Polynomial([-co for co in self.coeffs])
p = Polynomial([3,4,-2])
-p
(-3*x^0) + (-4*x^1) + (2*x^2)
Implementing __sub__: Using the fact we already have __neg__ and __add__ we define $f−g=f+(−g)$
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, Polynomial)
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
def __mul__(self, other):
assert isinstance(other, Polynomial)
terms = [0 for i in range(1 + self.degree()+other.degree())]
for i, c1 in enumerate(self.coeffs):
for j, c2 in enumerate(other.coeffs):
terms[i+j] += c1*c2
return Polynomial(terms)
def __neg__(self):
return Polynomial([-co for co in self.coeffs])
def __sub__(self, other):
assert isinstance(other, Polynomial)
return (self + (-other))
p = Polynomial([3,4,0,5])
q = Polynomial([10,1,0,5])
r = p-q
r
(-7*x^0) + (3*x^1)
Tests:
q = Polynomial([0, 0, 0, 6])
q
Polynomial([0, 0, 0, -6])
q.degree()
p = Polynomial([3, -4, 1])
p
p.evaluate(10)
dp = p.derivative()
dp
ddp = p.derivative().derivative()
ddp
q == p
r = p+q
r
p + Polynomial([-1])
q == Polynomial([0, 0, 0, 5]) + Polynomial([0, 0, 0, 1])
-p
p-q
p*q
Polynomial([0])*p
q = Polynomial([0, 0, 0, 6])
mq = Polynomial([1, 0, 0, -6])
z = q + mq
z.coeffs
(6*x^3)
(-6*x^3)
3
(3*x^0) + (-4*x^1) + (1*x^2)
63
(-4*x^0) + (2*x^1)
(2*x^0)
False
(3*x^0) + (-4*x^1) + (1*x^2) + (6*x^3)
(2*x^0) + (-4*x^1) + (1*x^2)
True
(-3*x^0) + (4*x^1) + (-1*x^2)
(3*x^0) + (-4*x^1) + (1*x^2) + (-6*x^3)
(18*x^3) + (-24*x^4) + (6*x^5)
0
[1]
Adding find_root method
class Polynomial():
def __init__(self, coeffs):
self.coeffs = coeffs
def __repr__(self):
terms = [" + (" + str(self.coeffs[k]) + "*x^" + \
str(k) + ")" \
for k in range(len(self.coeffs)) \
if self.coeffs[k] != 0]
terms = "".join(terms)
if terms == "":
return "0"
else:
return terms[3:] #discard leftmost '+'
def degree(self):
return len(self.coeffs) - 1
def evaluate(self, x):
result = 0
for i in range(1, len(self.coeffs)+1):
result = result*x + self.coeffs[-i]
return result
def derivative(self):
coeffs = [0 for i in range(len(self.coeffs)-1)]
for i in range(1,len(self.coeffs)):
coeffs[i-1] = self.coeffs[i]*i
return Polynomial(coeffs)
def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs
def __add__(self, other):
assert isinstance(other, Polynomial)
size = min(self.degree(), other.degree()) + 1
terms = [self.coeffs[i] + other.coeffs[i] for i in range(size)]
terms += self.coeffs[size : self.degree() + 1]
terms += other.coeffs[size : other.degree() + 1]
#remove leading zeros
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])
def __mul__(self, other):
assert isinstance(other, Polynomial)
terms = [0 for i in range(1 + self.degree()+other.degree())]
for i, c1 in enumerate(self.coeffs):
for j, c2 in enumerate(other.coeffs):
terms[i+j] += c1*c2
return Polynomial(terms)
def __neg__(self):
return Polynomial([-co for co in self.coeffs])
def __sub__(self, other):
assert isinstance(other, Polynomial)
return (self + (-other))
def find_root(self):
return NR(lambda x:self.evaluate(x), lambda x: self.derivative().evaluate(x))
p = Polynomial([3, -4, 1])
p.find_root()
p.find_root()
p.find_root()
3.0000000003611356
3.0
0.9999999999598665