Instructions:
Modify this notebook by adding the Python code described below.
Test your code using the menu item Cell ► Run All
Submit the notebook (the .ipynb file) to the appropriate dropbox on the course web site.
Define a class bitstr that subclasses the str(ing) type. The constructor bitstr(s) takes one string argument containing only the characters '0' and '1'. This class defines the operators * and + to do logical AND and OR respectively between successive characters of two bitstr values. For example, bitstr('1100')+bitstr('1010') would result in '1110' and bitstr('1100')*bitstr('1010') would result in '1000'.
class bitstr(str):
def __init__(self,s):
self=s
def __add__(self,s):
return ''.join(['1' if a == '1' or b == '1' else '0'
for a,b in zip(self,s)])
def __mul__(self,s):
return ''.join(['1' if a == '1' and b == '1' else '0'
for a,b in zip(self,s)])
print(bitstr("1100")+bitstr('1010'),
bitstr("1100")*bitstr('1010'),
bitstr("1100")+ '1010',
bitstr("1100")* '1010',
'1100' + '1010')
Write a recursive function named binsearch(l,s) that takes the following arguments:
l) of type maxlist whose elements are sorted in increasing order, and s)binsearch() searches l for s and returns s if s is found in l or None if l has length zero or if s is not in l.
The maxlist type is like a list but only supports the len() function and indexing (using the [] operator). You can only access elements of a maxlist up to $\lfloor\log_2(2\times\text{len(l)})\rfloor$ times. This means your search algorithm will need to use a binary search. You do not need to write the maxlist class, it is defined in the marking code below.
Hint: mid=len(l)//2 sets mid to the index of an element an element approximately half-way in the list and you can split l into two half-length lists: l[:mid] and l[mid:]. A recursive search algorithm would decide which half the value is in and return a binsearch() of the appropriate half.
def binsearch(l,s):
# print(l,s)
if len(l) == 0: # empty list
return None
if len(l) == 1: # one element left
if l[0] == s:
return s
else:
return None
# check appropriate sub-list
mid=len(l)//2;
if s >= l[mid]:
return binsearch(l[mid:],s)
else:
return binsearch(l[:mid],s)
binsearch([1,2,3],2)
# lab validation code; do not modify
def labcheck():
global maxlist
class maxlist(list):
'''list that can only be accessed log2(len(l)) times'''
def __init__(self,l):
self.l=list(l)
self.n=2*len(l)
def __repr__(self):
return repr(self.l)
def __getitem__(self,i):
assert self.n > 0, "Accessed too many times ."
self.n //= 2
return list.__getitem__(self.l,i)
def __len__(self):
return len(self.l)
def q1():
import random
m = [0,1,2,3]
random.shuffle(m)
shuf=lambda s: ''.join([s[i] for i in m])
a,b,c,d = shuf("1100"),shuf("1010"),shuf('1110'),shuf('1000')
e = bitstr(a)+bitstr(b)
f = bitstr(a)*bitstr(b)
assert c == e, "+ returns {} for {} and {}".format(e,a,b)
assert d == f, "* returns {} for {} and {}".format(f,a,b)
def q2():
import random, string
assert binsearch([],0) == None, "must return None for empty list"
for n in (1,5,8,14):
l=sorted(random.sample(string.ascii_lowercase,k=n))
c=random.sample(l,1)[0]
# print(l,c)
f = binsearch(maxlist(l),c)
assert f == c, f'found {f} searching for {c} in {l}'
for i,s in ((i,'q%d'%i) for i in range(1,20)):
if s in locals():
try:
locals()[s]()
print("Question {} OK.".format(i))
except Exception as e:
print("Failed check for Question {}: {}".format(i,e))
labcheck()