# Lab 7: Midterm Review lab07.zip

Due at 11:59pm on Friday, 07/19/2019.

## Starter Files

Download lab07.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

• In order to facilitate midterm studying, solutions to this lab were released with the lab. We encourage you to try out the problems and struggle for a while before looking at the solutions!
• Note: submitting this lab is entirely optional. It is not worth any credit, but will be helpful for your studying.

# Required Questions

## Functions

### Q1: WWPD: Call Expressions

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

``python3 ok -q call_expressions -u``

For all WWPD questions, type `Function` if you believe the answer is `<function...>`, > `Error` if it errors, and `Nothing` if nothing is displayed.

``````>>> from operator import add
>>> def double(x):
...     return x + x
...
>>> def square(y):
...     return y * y
...
>>> def f(z):
...
>>> f(4)
______# f(4) returns None, which is a special value that the interpreter hides unless explicitly printed``````
``````>>> def foo(x, y):
...     print("x or y")
...     return x or y
...
>>> a = foo
______# We aren't calling foo here; we are just binding the variable a in the global frame to the function object foo
>>> b = foo()
______TypeError: foo() missing 2 required positional arguments: 'x' and 'y'
>>> c = a(print("x"), print("y"))
______x
y
x or y
>>> print(c)
______None``````
``````>>> def welcome():
...     print('welcome to')
...     return 'hello'
...
>>> def cs61a():
...     print('cs61a')
...     return 'world'
...
>>> print(welcome(), cs61a())
______welcome to
cs61a
hello world``````

## Higher Order Functions

### Q2

Draw the environment diagram for the following code:

``````x = 5
def compose1(f, g):
def h(x):
return f(g(x))
return h
d = lambda y: y * x
x = 4
result = compose1(lambda z: z - 1, d)(3)``````

There are 5 frames total (including the Global frame). In addition, consider the following questions:

1. In frame `f1` (the frame for `compose1`), the parameter `f` points to a function object. What is the intrinsic name of that function object, and what frame is its parent?
2. In frame `f2`, what name is the frame labeled with (`h` or λ)? Which frame is the parent of `f2`?
3. In frame `f3`, what name is the frame labeled with (`f`, `g`, `d`, or λ)? Which frame is the parent of `f3`? In order to compute the return value `y * x`, in which frame does Python find `x`? What is that value of `x`?
4. In frame `f4`, what name is the frame labeled with (`f`, `g`, `d`, or λ)? Which frame is the parent of `f3`?
5. What value is the variable `result` bound to in the Global frame?

You can try out the environment diagram at tutor.cs61a.org.

1. The intrinsic name of the function object that `f` points to is λ (specifically, the lambda whose parameter is `z`). The parent frame of this lambda is Global.
2. `f2` is labeled with the name `h`; the parent frame of `f2` is `f1`, since that is where `h` is defined.
3. `f3` is labeled with the name λ (specifically, it is the λ that takes in a parameter `y`). The parent frame of `f3` is Global, since that is where this lambda was defined (the line `d = lambda y: y * x`).
4. `f4` is labeled with the name λ (specifically, it is the λ that takes a parameter `z`). The parent frame of `f4` is Global, since that is where the lambda is defined.

You might think that the parent of `f4` is `f1`, since `lambda z: z - 1` is being passed into `compose1`. Remember, however, that operands are evaluated before the operator is applied (that is, before we create the frame `f1`). Since we are evaluating `lambda z: z - 1` in the Global frame, its parent is Global.

5. The variable `result` is bound to 11.

## Recursion & Tree Recursion

### Q3: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function `paths` that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.) For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

``````def paths(m, n):
"""Return the number of paths from one corner of an
M by N grid to the opposite corner.

>>> paths(2, 2)
2
>>> paths(5, 7)
210
>>> paths(117, 1)
1
>>> paths(1, 157)
1
"""
if m == 1 or n == 1:
return 1
return paths(m - 1, n) + paths(m, n - 1)``````

Use Ok to test your code:

``python3 ok -q paths``

### Q4: Number of Trees

How many different possible full binary tree (each node has two branches or 0, but never 1) structures exist that have exactly n leaves?

For those interested in combinatorics, this problem does have a closed form solution):

``````def num_trees(n):
"""How many full binary trees have exactly n leaves? E.g.,

1   2        3       3    ...
*   *        *       *
/ \      / \     / \
*   *    *   *   *   *
/ \         / \
*   *       *   *

>>> num_trees(1)
1
>>> num_trees(2)
1
>>> num_trees(3)
2
>>> num_trees(8)
429

"""
if n == 1:
return 1
return sum(num_trees(k) * num_trees(n-k) for k in range(1, n))``````

Use Ok to test your code:

``python3 ok -q num_trees``

## Tree Practice

### Q5: Pruning Leaves

Define a function `prune_leaves` that given a tree `t` and a tuple of values `vals`, produces a version of `t` with all its leaves that are in `vals` removed. Do not attempt to try to remove non-leaf nodes and do not remove leaves that do not match any of the items in `vals`. Return `None` if pruning the tree results in there being no nodes left in the tree.

``````def prune_leaves(t, vals):
"""Return a modified copy of t with all leaves that have a label
that appears in vals removed.  Return None if the entire tree is
pruned away.

>>> t = tree(2)
>>> print(prune_leaves(t, (1, 2)))
None
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
1
2
3
4
5
6
7
>>> print_tree(prune_leaves(numbers, (3, 4, 6, 7)))
1
2
3
5
6
"""
if is_leaf(t) and (label(t) in vals):
return None
new_branches = []
for b in branches(t):
new_branch = prune_leaves(b, vals)
if new_branch:
new_branches += [new_branch]
return tree(label(t), new_branches)``````

Use Ok to test your code:

``python3 ok -q prune_leaves``

## Sequences and Mutability

### Q6: WWPD: Mutability?

What would Python display? Try to figure it out before you type it into the interpreter!

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

``python3 ok -q mutability -u``
``````>>> lst = [5, 6, 7, 8]
>>> lst.append(6)
______Nothing
>>> lst
______[5, 6, 7, 8, 6]
>>> lst.insert(0, 9)
>>> lst
______[9, 5, 6, 7, 8, 6]
>>> x = lst.pop(2)
>>> lst
______[9, 5, 7, 8, 6]
>>> lst.remove(x)
>>> lst
______[9, 5, 7, 8]
>>> a, b = lst, lst[:]
>>> a is lst
______True
>>> b == lst
______True
>>> b is lst
______False``````
``````>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
______25
>>> len(pokemon)
______3
>>> pokemon['jolteon'] = 135
>>> pokemon['mew'] = 25
>>> len(pokemon)
______4
>>> 'mewtwo' in pokemon
______False
>>> 'pikachu' in pokemon
______True
>>> 25 in pokemon
______False
>>> 151 in pokemon
______False
>>> pokemon['ditto'] = pokemon['jolteon']
>>> pokemon['ditto']
______135``````

### Q7: Dict to List

Fill in the blanks in the code to complete the implementation of the `dict_to_lst` function, which takes in a dictionary `d` and returns a list. The resulting list should contain all the (key, value) pairs in the input dictionary as two-element tuples, where the pairs with smaller values come first.

Note: The `.items()` method returns a collection of (key, value) pairs for a dictionary:

``````>>> for pair in {1: 2, 3: 4, 5: 6}.items():
...     print(pair)
(1, 2)
(3, 4)
(5, 6)``````
``````def dict_to_lst(d):
"""Returns a list containing all the (key, value) pairs in d as two-element
tuples ordered by increasing value.

>>> nums = {1: 5, 2: 3, 3: 4}
>>> dict_to_lst(nums)
[(2, 3), (3, 4), (1, 5)]
>>> words = {'first': 'yes', 'second': 'no', 'third': 'perhaps'}
>>> dict_to_lst(words)
[('second', 'no'), ('third', 'perhaps'), ('first', 'yes')]
"""
result = []
for _ in range(len(d)):
pair = min(d.items(), key=______________________)
pair = min(d.items(), key=lambda item: item)        d.pop(_________)
d.pop(pair)        _______________________
result.append(pair)    return result

# Alternate solution
# This solution is the ideal way to solve this problem, but we haven't learned
# how to use the sorted function so don't worry if you don't understand it.
def dict_to_list2(d):
return sorted(d.items(), key=lambda pair: pair)``````

Use Ok to test your code:

``python3 ok -q dict_to_lst``