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()