# cs1001.py , Tel Aviv University, Spring 2020 # Recitation 9¶

We discussed OOP and special methods that allow us to define operators in Python. Then, we saw an implementation of a Linked list data structure.

#### Takeaways:¶

• OOP allows us to create classes at will and to define complex objects. Remember that the most important thing is to find a good inner representation of the object so that you will have an easy time working with it.

• Important properties of Linked lists:

• Not stored continuously in memory.
• Allows for deletion and insertion after a given element in $O(1)$ time.
• Accessing the $i$'th element takes $O(i)$ time.
• Search takes $O(n)$ time (no random access $\implies$ no $O(\log{n})$ search).

#### Code for printing several outputs in one cell (not part of the recitation):¶

In :
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"


## OOP¶

A link to special method names in python: https://diveintopython3.net/special-method-names.html

### Basic polynomial class¶

We represent a polynomial as a list of coefficients, where the $i$'th element in the list is the coefficient of $x^i$

In :
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:

f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

f
g

Out:
(1*x^0) + (1*x^1)
Out:
(2*x^0) + (3*x^1) + (4*x^2)

#### Add degree and evaluate functions (these are special to class polynomial and are not part of Python's recognized functions)¶

In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

f = Polynomial([1, 1])
f.degree()
f.evaluate(5)

Out:
1
Out:
6
In :
p = Polynomial([1,0,1])
q = Polynomial([1,0,1])
p == q

Out:
False

#### Add __eq__ function for the '==' operator¶

Without it, Python compares memory adderesses

In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

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)

Out:
False
Out:
True
Out:
True

In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs

assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms += other
return Polynomial(terms)
#else, other is a 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]
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, 3, 4])

f+g
f+100
100+f

Out:
(3*x^0) + (4*x^1) + (4*x^2)
Out:
(101*x^0) + (1*x^1)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-6-b1cbfd0c49d6> in <module>
49 f+g
50 f+100
---> 51 100+f

TypeError: unsupported operand type(s) for +: 'int' and 'Polynomial'

Since there is no support for addition with a Polynomial in the class int, python needs a definition of right addition for int in class Polynomial

When executing the command $f + 3$, python will first search for an __add__ method in class int that can support a second operand of type polynomial (self = int, other = polynomial). If such method does not exist, python will then search for an __radd__ method in class polynomial that can support a second operand of type int (self= polynomial, other = int). If such method does not exist, an exception is thrown.

Since + is commutative, then we set __radd__ to be identical to __add__

In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs

assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms += other
return Polynomial(terms)
#else, other is a 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]
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])

f = Polynomial([1, 1])
1 + f

Out:
(2*x^0) + (1*x^1)

#### Add __neg__ function for unary minus (placing a '-' before a polynomial object)¶

In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs

assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms += other
return Polynomial(terms)
#else, other is a 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]
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])

def __neg__(self):
return Polynomial([-co for co in self.coeffs])

f = Polynomial([1, 1])
-f

Out:
(-1*x^0) + (-1*x^1)

#### Add __sub__ function to subtract one poly form another or an int from a poly¶

Using the fact we already have __neg__ and __add__ we define $f-g = f + (-g)$

In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs

assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms += other
return Polynomial(terms)
#else, other is a 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]
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])

def __neg__(self):
return Polynomial([-co for co in self.coeffs])

def __sub__(self, other):
assert isinstance(other, (int, Polynomial))
return (self + (-other))

f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

g - f
g - 1

Out:
(1*x^0) + (2*x^1) + (4*x^2)
Out:
(1*x^0) + (3*x^1) + (4*x^2)

#### Add __rsub__ function for right subtraction¶

Using the fact we already have __neg__ and __sub__ we define $f-g = -(g-f)$

since oprator - is not commutative, then we cannot set __rsub__ to be identical to __sub__

Note that the following implementation of __rsub__ is promlematic, because it will keep calling itself (infinitely)

def __rsub__(self, other):
return other-self #PROBLEMATIC!
In :
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:

def degree(self):
return len(self.coeffs) - 1

def evaluate(self, x):
result = 0
for i, c in enumerate(self.coeffs):
result += c * pow(x, i)
return result

def __eq__(self, other):
assert isinstance(other, Polynomial)
return self.coeffs == other.coeffs

assert isinstance(other, (Polynomial, int))
if isinstance(other, int):
terms = [c for c in self.coeffs]
terms += other
return Polynomial(terms)
#else, other is a 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]
last = len(terms) - 1
while last > 0 and terms[last] == 0:
last -= 1
return Polynomial(terms[:last+1])

def __neg__(self):
return Polynomial([-co for co in self.coeffs])

def __sub__(self, other):
assert isinstance(other, (int, Polynomial))
return (self + (-other))

#__rsub__ = __sub__ #not what we want...

def __rsub__(self, other):
# other - self
return -(self - other) #why not just other-self ?

f = Polynomial([1, 1])
g = Polynomial([2, 3, 4])

1 - f
1 - g

Out:
(-1*x^1)
Out:
(-1*x^0) + (-3*x^1) + (-4*x^2)

A linked list is a linear data structure (i.e. - nodes can be accessed one after the other). The list is composed of nodes, where each node contains a value and a "pointer" to the next node in the list.

Linked lists support operations such as insertion, deletion, search and many more.

In :
class Node():
def __init__(self, val):
self.value = val
self.next = None

def __repr__(self):
#return "[" + str(self.value) + "," + str(id(self.next))+ "]"

#for today's recitation, we print the id of self instead of self.next
return "[" + str(self.value) + "," + str(id(self))+ "]"

def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:

def __repr__(self):
out = ""
p = self.next
while p != None:
out += str(p) + " " #str envokes __repr__ of class Node
p = p.next
return out

def __len__(self):
''' called when using Python's len() '''
return self.len

p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1

''' 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


Converting a string to a list

In :
L= Linked_list("abc")
L

Out:
[a,91843024] [b,91843088] [c,91842992]

memory view Adding elements one by one. Try using Python tutor.

In :
l = Linked_list()
l

Out:
[b,91843568] [a,91843664]
##### A short summary of methods complexity of Linked lists vs. lists:¶
 Method List Linked list init $O(1)$ $O(1)$ init with $k$ items $O(k)$ $O(k)$ for the rest of the methods we assume that the structure contains $n$ items add at start $O(n)$ $O(1)$ add at end $O(1)$ $O(n)$ $lst[k]$ (get the $k$th item) $O(1)$ $O(k)$ delete $lst[k]$ $O(n-k)$ $O(k)$

Reversing a linked list in $O(1)$ additional memory. See the code and demo here

In :
class Node():
def __init__(self, val):
self.value = val
self.next = None

def __repr__(self):
#return "[" + str(self.value) + "," + str(id(self.next))+ "]"

#for today's recitation, we print the id of self instead of self.next
return "[" + str(self.value) + "," + str(id(self))+ "]"

def __init__(self, seq=None):
self.next = None
self.len = 0
if seq != None:
for x in seq[::-1]:

def __repr__(self):
out = ""
p = self.next
while p != None:
out += str(p) + " " #str envokes __repr__ of class Node
p = p.next
return out

def __len__(self):
''' called when using Python's len() '''
return self.len

p = self
tmp = p.next
p.next = Node(val)
p.next.next = tmp
self.len += 1

''' 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

def reverse(self):
prev = None
curr = self.next
while curr != None:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
self.next = prev

ll
ll.reverse()
ll

Out:
[a,91941296] [b,91941232] [c,91941200]
Out:
[c,91941200] [b,91941232] [a,91941296]

Exam question (2018, Spring Semester)

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.

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.

In :
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

K.next = L.next.next.next
# Manually define the length of K
K.len = 2
K

M

print(are_merged(L,K))
print(are_merged(L,M))

Out:
[a,2582652271360] [b,2582652268728] [c,2582652271808] [d,2582652268840]
Out:
[e,2582652270800] [c,2582652271808] [d,2582652268840]
Out:
[d,2582652629344]
True
False


### Time and space analysis¶

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.

Analyze its running time and space complexity.

In :
def find_shared_1(L, K):
id_set = set()
p = L.next
while p != None:
p = p.next
q = K.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

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

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

L

K.next = L.next.next.next
# Save the first joint node
x = K.next
K.len = 2
K

M

print(are_merged(L,K))
print(are_merged(L,M))

print(find_shared_1(L,K), find_shared_1(L,K) == x)
print(find_shared_2(L,K), find_shared_2(L,K) == x)
print(find_shared_3(L,K), find_shared_3(L,K) == x)

Out:
[a,91940784] [b,91940624] [c,91940592] [d,91940272]
Out:
[e,91940432] [c,91940592] [d,91940272]
Out:
[d,1901584]
True
False
[c,91940592] True
[c,91940592] True
[c,91940592] True


For the analysis assume wlog that $n \geq m$:

• For find_shared_1:
• Space: Saving all of the node ids from $L$ in a set: $O(n)$, 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 - $O(n)$ on average
• For find_shared_2:
• Space: Saving $n,m$ and an index for the for loop: $O(\log n)$, 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)$
• For find_shared_3:
• 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(n)$