<jupyter_start><jupyter_text>Quiz 4BEFORE YOU START THIS QUIZ:1. Click on "Copy to Drive" to make a copy of the quiz,2. Click on "Share",    3. Click on "Change" and select "Anyone with this link can edit"    4. Click "Copy link" and5. Paste the link into [this Canvas assignment](https://canvas.olin.edu/courses/313/assignments/5032). This quiz is open notes, open internet. The only thing you can't do is ask for help.Copyright 2021 <NAME>, [MIT License](http://opensource.org/licenses/MIT)<jupyter_code>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')<jupyter_output><empty_output><jupyter_text>Question 1According to [Wikipedia](https://en.wikipedia.org/wiki/Gray_code), 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         001         012         113         10```In this code, the representation of the number 3 is the bit sequence `10`.[This section of the Wikipedia page](https://en.wikipedia.org/wiki/Gray_codeConstructing_an_n-bit_Gray_code) 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. You can use the following cells to test your solution.<jupyter_code>gray_code(1)   # should be ['0', '1']
gray_code(2)   # should be ['00', '01', '11', '10']
gray_code(3)   # see above<jupyter_output><empty_output><jupyter_text>Question 2Suppose 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.<jupyter_code>from random import shuffle

sequence = list(range(10))
shuffle(sequence)
sequence
k_largest(sequence, 3)   # should return [7, 8, 9]<jupyter_output><empty_output><jupyter_text>Question 3An 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`.<jupyter_code>from collections import namedtuple

Node = namedtuple('Node', ['data', 'left', 'right'])<jupyter_output><empty_output><jupyter_text>In a leaf node, `data` contains a number. For example, here are two nodes representing the numbers `1` and `2`.<jupyter_code>operand1 = Node(1, None, None)
operand1
operand2 = Node(2, None, None)
operand2<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>from operator import add, sub, mul<jupyter_output><empty_output><jupyter_text>Now we can make an expression tree with the `add` function at the root and two operands as children.<jupyter_code>etree = Node(add, operand1, operand2)
etree<jupyter_output><empty_output><jupyter_text>To evaluate this tree, we can extract the function and the two operands, then call the function and pass the operands as arguments.<jupyter_code>func = etree.data
left = operand1.data
right = operand2.data
func(left, right)<jupyter_output><empty_output><jupyter_text>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:<jupyter_code>etree
evaluate(etree)  # result should be 3 
operand3 = Node(3, None, None)
etree2 = Node(mul, etree, operand3)
evaluate(etree2)  # result should be 9
operand4 = Node(4, None, None)
etree3 = Node(sub, etree2, operand4)
evaluate(etree3) # result should be 5<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09075342465753425, 'fraction_numerical': 0.0213089802130898, 'mean_word_length': 5.0286697247706424, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 38, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '113345', 'license': 'MIT', 'n_tokens_mistral': 1581, 'n_tokens_neox': 1491, 'n_words': 662, 'path': 'notebooks/quiz04.ipynb', 'repo_name': 'AhmedOmarEissa/DSIRP', 'size': '5262'}