# CS 61A

Time: Tue 10/11/17 3:15 pm

## Order of Growth

What's the big-theta notation?

What are some things that may or may not affect the orders of growth? Consider constant terms, logarithms, nesting, lower-order terms.

On the spectrum of orders of growth, what's considered the "worst," as in runtime?

Try to come up with an example for each of the big-theta notations introduced in the course.

### Instant Noodles (su17-mt1-4)

For each of the functions below, find the order of growth that best describes the execution time as a function of `N`, the size of the input number `n`, or infinite if the function never terminates.

1. Code:

``````def foo(n):
i = 1
while i < n:
i += 10
n += 5``````
2. Code:

``````def baz(n):
i = 1
while i < n:
j = i
while j < n:
while j < n:
j += 1
j += 1
i += 1``````
3. Code:

``````def bar(n):
i = 1
while i < n:
i += i
i += i``````
4. Code:

``````def garply(n):
for i in range(n):
for j in range(n):
for k in range(i + j):
return garply(n - 1)``````

### Will Code for Points (sp15-mt2-3)

1. Implement `objectify`, which takes a tree data abstraction and returns an equivalent `Tree` instance.

``````class Tree:

def __init__(self, root, branches=[]):
self.root = root
for branch in branches:
assert isinstance(branch, Tree)
self.branches = list(branches)

def is_leaf(self):
return not self.branches``````
``````def objectify(t):
"""
Return a Tree instance equivalent to a tree represented as a list.

>>> m = tree(2)
>>> m
>>> objectify(m)
Tree(2)
>>> r = tree(3, [tree(4, [tree(5), tree(6)]), tree(7, [tree(8)])])
>>> r
[3, [4, , ], [7, ]]
>>> objectify(r)
Tree(3, [Tree(4, [Tree(5), Tree(6)]), Tree(7, [Tree(8)])])
"""

return ``````
2. What's the big-theta expression that describes the number of `Tree` instances constructed by calling obejctify on a tree with n nodes?

## Midterm 2 Practice

### This One Goes to Eleven (fa14-mt2-3)

1. Fill in the blanks of the implementation of `sixty_ones` below, a function that takes a `Link` instance representing a sequence of integers and returns the number of times that 6 and 1 appear consecutively.

``````def sixty_ones(s):
"""
Return the number of times that 1 directly follows 6 in linked list s.

>>> apply_to_all(sixty_ones, [Link.empty, once, twice, thrice])
[0, 1, 2, 3]
"""

if :
return 0
elif :
return 1 +
else:
return ``````
2. Fill in the blanks of the implementation of `no_eleven` below, a function that returns a list of all distinct length-n lists of ones and sixes in which 1 and 1 do not appear consecutively.

``````def no_eleven(n):
"""
Return a list of lists of 1’s and 6’s that do not contain 1 after 1.

>>> no_eleven(2)
[[6, 6], [6, 1], [1, 6]]
>>> no_eleven(3)
[[6, 6, 6], [6, 6, 1], [6, 1, 6], [1, 6, 6], [1, 6, 1]]
>>> no_eleven(4)[:4] # first half
[[6, 6, 6, 6], [6, 6, 6, 1], [6, 6, 1, 6], [6, 1, 6, 6]]
>>> no_eleven(4)[4:] # second half
[[6, 1, 6, 1], [1, 6, 6, 6], [1, 6, 6, 1], [1, 6, 1, 6]]
"""

if n == 0:
return
elif n == 1:
return
else:
a, b = no_eleven(), no_eleven()
return [ for s in a] + [ for s in b]``````

### Game of Thrones (su16-mt-7)

This question uses the following tree data abstraction.

``````def tree(entry, children=[]):
return [entry, children]

def entry(tree):
return tree

def children(tree):
return tree``````
1. Define the function `track_lineage` that takes in a tree of strings `family_tree` and a string `name`. Assume that there is a unique node with entry `name`. `track_lineage` returns a list with the entries of the parent and grandparent of that node. If the node with entry name does not have a parent or grandparent, return `None` for that element in the list. See the doctests for details. Do not violate abstraction barriers. You may only use the lines provided. You may not need to fill all the lines.

``````def track_lineage(family_tree, name):
"""
Return the entries of the parent and grandparent of the node with entry name in family_tree.

>>> t = tree('Tytos', [
...   tree('Tywin', [
...     tree('Cersei'), tree('Jaime'), tree('Tyrion')
...   ]),
...   tree('Kevan', [
...     tree('Lancel'), tree('Martyn'), tree('Willem')
...   ])])
>>> track_lineage(t, 'Tywin')
['Tytos', None]
>>> track_lineage(t, 'Tytos')
[None, None]
"""

def tracker(t, p, gp):
if

for c in children(t):

return tracker(, , )``````
2. Assuming that `track_lineage` works correctly, define the function are cousins that takes in a tree of strings `family_tree` and two strings `name1` and `name2` and returns `True` if the node with entry `name1` and the node with entry `name2` are cousins in `family_tree`. Assume that there are unique nodes with entries `name1` and `name2` in `family_tree`. See the doctests for details. Two nodes are cousins if they have the same grandparent but different parents.

You may only use the lines provided. You may not need to fill all the lines.

``````def are_cousins(family_tree, name1, name2):
"""Return True if a node with entry name1 is a cousin of a node with entry name2 in family_tree.
>>> are_cousins(t, ‘Kevan’, ‘Tytos’) # same tree as before False
>>> are_cousins(t, ‘Cersei’, ‘Lancel’)
True
>>> are_cousins(t, ‘Jaime’, ‘Lancel’)
True
>>> are_cousins(t, ‘Jaime’, ‘Tyrion’)
False
"""

``````

### Tree Time (fa14-mt2-4)

1. A `GrootTree` `g` is a binary tree that has an attribute `parent`. Its parent is the `GrootTree` in which `g` is a branch. If a `GrootTree` instance is not a branch of any other `GrootTree` instance, then its parent is `BinaryTree.empty`.

`BinaryTree.empty` should not have a `parent` attribute. Assume that every `GrootTree` instance is a branch of at most one other `GrootTree` instance and not a branch of any other kind of tree.

Fill in the blanks below so that the `parent` attribute is set correctly. You may not need to use all of the lines. Indentation is allowed. You should not include any `assert` statements. Using your solution, the doctests for `fib_groot` should pass.

``````class GrootTree(BinaryTree):
"""A binary tree with a parent."""

def __init__(self, entry, left=BinaryTree.empty, right=BinaryTree.empty):
BinaryTree.__init__(self, entry, left, right)

def fib_groot(n):
"""
Return a Fibonacci GrootTree.

>>> t = fib_groot(3)
>>> t.entry
2
>>> t.parent.is_empty
True
>>> t.left.parent.entry
2
>>> t.right.left.parent.right.parent.entry
1
"""

if n == 0 or n == 1:
return GrootTree(n)
else:
left, right = fib_groot(n - 2), fib_groot(n - 1)
return GrootTree(left.entry + right.entry, left, right)``````
2. Fill in the blanks of the implementation of `paths`, a function that takes two arguments: a `GrootTree` instance `g` and a list `s`. It returns the number of paths through `g` whose entries are the elements of `s`. A path through a `GrootTree` can extend either to a branch or its `parent`.

You may assume that the `GrootTree` class is implemented correctly and that the list `s` is non-empty.

There are two paths for `[2, 1, 2, 1, 0]`, one path for `[2, 1, 0, 1, 0]` in the tree below:

```    2
+-------+
1       1
+---+
0   1```

``````def paths(g, s):
"""
The number of paths through g with entries s.

>>> t = fib_groot(3)
>>> paths(t, )
0
>>> paths(t, )
1
>>> paths(t, [2, 1, 2, 1, 0])
2
>>> paths(t, [2, 1, 0, 1, 0])
1
>>> paths(t, [2, 1, 2, 1, 2, 1])
8
"""

if g is BinaryTree.empty :
return 0
elif :
return 1
else:
xs = []
return sum([ for x in xs])``````