Quiz 4
Contents
Quiz 4#
BEFORE YOU START THIS QUIZ:
Click on “Copy to Drive” to make a copy of the quiz,
Click on “Share”,
Click on “Change” and select “Anyone with this link can edit”
Click “Copy link” and
Paste the link into this Canvas assignment.
This quiz is open notes, open internet. The only thing you can’t do is ask for help.
Copyright 2021 Allen Downey, MIT License
from os.path import basename, exists
def download(url):
filename = basename(url)
if not exists(filename):
from urllib.request import urlretrieve
local, _ = urlretrieve(url, filename)
print('Downloaded ' + local)
download('https://github.com/AllenDowney/DSIRP/raw/main/american-english')
Question 1#
According to Wikipedia, a Gray code is “an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).”
A “Gray code list” is a table that lists the Gray code for each decimal number in order. For example, the following is the Gray code list for decimal numbers up to 3:
number Gray code
------ ---------
0 00
1 01
2 11
3 10
In this code, the representation of the number 3 is the bit sequence 10.
This section of the Wikipedia page presents an algorithm for constructing a Gray code list with a given number of binary digits.
Write a function called gray_code that takes the number of binary digits, n, as a parameter and returns a list of strings that represents a Gray code list.
For example, gray_code(3) should return
['000', '001', '011', '010', '110', '111', '101', '100']
Your function can be iterative or recursive.
# Buggy solution
def gray_code(n, codes=['0', '1']):
if n <= 1:
return codes
r = codes[::-1]
for i, code in enumerate(codes):
codes[i] = '0' + code
for i, code in enumerate(r):
r[i] = '1' + code
codes.extend(r)
return gray_code(n-1, codes)
You can use the following cells to test your solution.
gray_code(1) # should be ['0', '1']
['0', '1']
gray_code(2) # should be ['00', '01', '11', '10']
['00', '01', '11', '10']
gray_code(3) # see above
['0000',
'0001',
'0011',
'0010',
'0110',
'0111',
'0101',
'0100',
'1100',
'1101',
'1111',
'1110',
'1010',
'1011',
'1001',
'1000']
gray_code(4) # see above
['0000000',
'0000001',
'0000011',
'0000010',
'0000110',
'0000111',
'0000101',
'0000100',
'0001100',
'0001101',
'0001111',
'0001110',
'0001010',
'0001011',
'0001001',
'0001000',
'0011000',
'0011001',
'0011011',
'0011010',
'0011110',
'0011111',
'0011101',
'0011100',
'0010100',
'0010101',
'0010111',
'0010110',
'0010010',
'0010011',
'0010001',
'0010000',
'0110000',
'0110001',
'0110011',
'0110010',
'0110110',
'0110111',
'0110101',
'0110100',
'0111100',
'0111101',
'0111111',
'0111110',
'0111010',
'0111011',
'0111001',
'0111000',
'0101000',
'0101001',
'0101011',
'0101010',
'0101110',
'0101111',
'0101101',
'0101100',
'0100100',
'0100101',
'0100111',
'0100110',
'0100010',
'0100011',
'0100001',
'0100000',
'1100000',
'1100001',
'1100011',
'1100010',
'1100110',
'1100111',
'1100101',
'1100100',
'1101100',
'1101101',
'1101111',
'1101110',
'1101010',
'1101011',
'1101001',
'1101000',
'1111000',
'1111001',
'1111011',
'1111010',
'1111110',
'1111111',
'1111101',
'1111100',
'1110100',
'1110101',
'1110111',
'1110110',
'1110010',
'1110011',
'1110001',
'1110000',
'1010000',
'1010001',
'1010011',
'1010010',
'1010110',
'1010111',
'1010101',
'1010100',
'1011100',
'1011101',
'1011111',
'1011110',
'1011010',
'1011011',
'1011001',
'1011000',
'1001000',
'1001001',
'1001011',
'1001010',
'1001110',
'1001111',
'1001101',
'1001100',
'1000100',
'1000101',
'1000111',
'1000110',
'1000010',
'1000011',
'1000001',
'1000000']
Question 2#
Suppose you are given a very large sequence of numbers and you are asked to find the k largest elements.
One option would be to sort the sequence, but that would take time proportional to n log n, where n is the length of the sequence.
And you would have to store the entire sequence.
An alternative is to use a “bounded heap”, that is, a heap that never contains more than k elements.
Write a function called k_largest that takes as parameters an iterable and an integer k and returns a list that contains the k largest elements in the iterable. Don’t worry about ties.
Your implementation should not store more than k elements and it should take time proportional to n log k.
You can use the following cells to test your function.
from random import shuffle
sequence = list(range(10))
shuffle(sequence)
sequence
[4, 3, 0, 7, 1, 5, 9, 6, 8, 2]
k_largest(sequence, 3) # should return [7, 8, 9]
[7, 9, 8]
Question 3#
An expression tree is a tree that represents a mathematical expression.
For example, the expression (1+2) * 3 is represented by a tree with the multiplication operator at the root and two children:
The left child is a node that contains the addition operator and two children, the number 1 and the number 2.
The right child is a node that contains the number 3.
To represent an expression tree, we can use a namedtuple called Node that contains three attributes, data, left, and right.
from collections import namedtuple
Node = namedtuple('Node', ['data', 'left', 'right'])
In a leaf node, data contains a number. For example, here are two nodes representing the numbers 1 and 2.
operand1 = Node(1, None, None)
operand1
Node(data=1, left=None, right=None)
operand2 = Node(2, None, None)
operand2
Node(data=2, left=None, right=None)
For internal nodes (that is, not leaf nodes) data contains a function. To represent addition, subtraction, and multiplication, I’ll import functions from the operator module.
from operator import add, sub, mul
Now we can make an expression tree with the add function at the root and two operands as children.
etree = Node(add, operand1, operand2)
etree
Node(data=<built-in function add>, left=Node(data=1, left=None, right=None), right=Node(data=2, left=None, right=None))
To evaluate this tree, we can extract the function and the two operands, then call the function and pass the operands as arguments.
func = etree.data
left = operand1.data
right = operand2.data
func(left, right)
3
Write a function called evaluate that takes an arbitrary expression tree, evaluates it, and returns an integer.
You will probably want to write this one recursively.
You can test your function with the following examples:
etree
Node(data=<built-in function add>, left=Node(data=1, left=None, right=None), right=Node(data=2, left=None, right=None))
evaluate(etree) # result should be 3
3
operand3 = Node(3, None, None)
etree2 = Node(mul, etree, operand3)
evaluate(etree2) # result should be 9
9
operand4 = Node(4, None, None)
etree3 = Node(sub, etree2, operand4)
evaluate(etree3) # result should be 5
5