We discussed two data structures: Linked lists and Binary search trees. Then, we solved two (challenging) recursion exercises: Choose-sets and N-queens.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Code from class
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))+ "]"
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 envokes __repr__ of class Node
p = p.next
return out
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
if p != None and p.next != None:
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
def string_to_linked_list(str):
L= Linked_list()
for ch in str[::-1]:
L.add_at_start(ch)
return L
string_to_linked_list("abc")
[a,2491464885696] [b,2491464884856] [c,2491464887544]
Memory view
Adding elements one by one. Try using Python tutor.
l = Linked_list()
l.add_at_start("a")
l.add_at_start("b")
l
[b,2491465543576] [a,2491465542904]
Reversing a linked list in $O(1)$ additional memory. See the code and demo here
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))+ "]"
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 envokes __repr__ of class Node
p = p.next
return out
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
if p != None and p.next != None:
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 = string_to_linked_list("abc")
ll
ll.reverse()
ll
[a,2491465701024] [b,2491465700968] [c,2491465700912]
[c,2491465700912] [b,2491465700968] [a,2491465701024]
class Tree_node():
def __init__(self, key, val):
self.key = key
self.val = val
self.left = None
self.right = None
def __repr__(self):
return "(" + str(self.key) + ":" + str(self.val) + ")"
class Binary_search_tree():
def __init__(self):
self.root = None
def __repr__(self): #no need to understand the implementation of this one
out = ""
for row in printree(self.root): #need printree.py file
out = out + row + "\n"
return out
def lookup(self, key):
''' return node with key, uses recursion '''
def lookup_rec(node, key):
if node == None:
return None
elif key == node.key:
return node
elif key < node.key:
return lookup_rec(node.left, key)
else:
return lookup_rec(node.right, key)
return lookup_rec(self.root, key)
def insert(self, key, val):
''' insert node with key,val into tree, uses recursion '''
def insert_rec(node, key, val):
if key == node.key:
node.val = val # update the val for this key
elif key < node.key:
if node.left == None:
node.left = Tree_node(key, val)
else:
insert_rec(node.left, key, val)
else: #key > node.key:
if node.right == None:
node.right = Tree_node(key, val)
else:
insert_rec(node.right, key, val)
return
if self.root == None: #empty tree
self.root = Tree_node(key, val)
else:
insert_rec(self.root, key, val)
def minimum(self):
''' return node with minimal key '''
if self.root == None:
return None
node = self.root
left = node.left
while left != None:
node = left
left = node.left
return node
def depth(self):
''' return depth of tree, uses recursion'''
def depth_rec(node):
if node == None:
return -1
else:
return 1 + max(depth_rec(node.left), depth_rec(node.right))
return depth_rec(self.root)
def size(self):
''' return number of nodes in tree, uses recursion '''
def size_rec(node):
if node == None:
return 0
else:
return 1 + size_rec(node.left) + size_rec(node.right)
return size_rec(self.root)
def inorder(self):
'''prints the keys of the tree in a sorted order'''
def inorder_rec(node):
if node == None:
return
inorder_rec(node.left)
print(node.key)
inorder_rec(node.right)
inorder_rec(self.root)
t = Binary_search_tree()
t.insert(2,"hi")
t.insert(4,"tea")
t.insert(1,"mother")
t.insert(3,"CS")
t.insert(4,"recursion")
t.inorder()
1 2 3 4
def choose_sets(lst,k):
if k==0:
return [[]]
elif len(lst)<k:
return []
tmp = choose_sets(lst[1:],k-1)
for e in tmp:
e.append(lst[0])
tmp.extend(choose_sets(lst[1:],k))
return tmp
choose_sets([1,2,3,4], 0)
choose_sets([1,2,3,4], 2)
choose_sets([1,2,3,4], 4)
[[]]
[[2, 1], [3, 1], [4, 1], [3, 2], [4, 2], [4, 3]]
[[4, 3, 2, 1]]
The presentation can be found here.
First try to understand the queens() and queens_rec() functions and then try to understand how the function legal() works.
Some intuition for queens_rec:
assume we can find a solution for placing $k<N$ queens, how do we expand the solution to $k+1$? queens_rec returns the number of possible legal placements for $N$ queens, where $k$ are already placed at the leftmost columns and there are $N-k$ queens left to place. The recursive idea: Legally place queen number $(k+1)$ and recursively solve the problem, when there is one less queen to place.
Note that the complexity is $O(N!)$ (greater than $O(2^N)$)
def queens(n,show=True):
''' how many ways to place n queens on an nXn board? '''
partial = [] # list representing partial placement of queens
return queens_rec(n, partial,show)
def queens_rec(n, partial,show):
''' Given a list representing partial placement of queens,
can we legally extend it ? '''
if len(partial)==n: #all n queens are placed legally
if show:
print(partial)
return 1
else:
cnt=0
for i in range(n):
if legal(partial,i): #try to place a queen in row i of the next column
cnt += queens_rec(n, partial+[i],show)
return cnt
def legal(partial, i):
''' Can we place a queen in the next column in row i ? '''
left = [j for j in partial if j==i] #any queens in the same row to the left?
diag_up = [j for j in partial if j-partial.index(j) == i-len(partial)] #diagonal up-left
diag_down = [j for j in partial if j+partial.index(j) == i+len(partial)] #diagonal down-left
res = (left == diag_up == diag_down == [])
# print ("partial=",partial,"can add queen at row", i , "?",res)
return res