# Discussion 8: Linked Lists, Mutable Trees, Efficiency disc08.pdf

This is an online worksheet that you can work on during discussions. Your work is not graded and you do not need to submit anything.

# Representation: Repr, Str

### Q1: WWPD: Repr-esentation

Note: This is not the typical way `repr` is used, nor is this way of writing `repr` recommended, this problem is mainly just to make sure you understand how `repr` and `str` work.

``````class A:
def __init__(self, x):
self.x = x

def __repr__(self):
return self.x

def __str__(self):
return self.x * 2

class B:
def __init__(self):
print('boo!')
self.a = []

self.a.append(a)

def __repr__(self):
print(len(self.a))
ret = ''
for a in self.a:
ret += str(a)
return ret``````

Given the above class definitions, what will the following lines output?

``>>> A('one')``
``>>> print(A('one'))``
``>>> repr(A('two'))``
``>>> b = B()``
``````>>> b.add_a(A('a'))
>>> b``````

There are many different implementations of sequences in Python. Today, we'll explore the linked list implementation.

A linked list is either an empty linked list, or a Link object containing a `first` value and the `rest` of the linked list.

To check if a linked list is an empty linked list, compare it against the class attribute `Link.empty`:

``````if link is Link.empty:
else:
print('This linked list is not empty!')``````

You can find an implementation of the `Link` class below:

``````class Link:
empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest

def __repr__(self):
if self.rest:
rest_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'

def __str__(self):
string = '<'
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'``````

### Q2: The Hy-rules of Linked Lists

In this question, we are given the following Linked List:

``ganondorf = Link('zelda', Link('link', Link('sheik', Link.empty)))``

What expression would give us the value `'sheik'` from this Linked List?

What is the value of `ganondorf.rest.first`?

What would be the value of `str(ganondorf)`?

What expression would mutate this linked list to `<zelda ganondorf sheik>`?

### Q3: Sum Nums

Write a function that takes in a linked list and returns the sum of all its elements. You may assume all elements in `s` are integers. Try to implement this recursively!

Run in 61A Code

Write a function that takes in a Python list of linked lists and multiplies them element-wise. It should return a new linked list.

If not all of the `Link` objects are of equal length, return a linked list whose length is that of the shortest linked list given. You may assume the `Link` objects are shallow linked lists, and that `lst_of_lnks` contains at least one linked list.

Run in 61A Code

### Q5: Flip Two

Write a recursive function `flip_two` that takes as input a linked list `s` and mutates `s` so that every pair is flipped.

Run in 61A Code

# Trees

We define a tree to be a recursive data abstraction that has a label (the value stored in the root of the tree) and branches (a list of trees directly underneath the root). Previously, we implemented the tree abstraction using Python lists. Let's look at another implementation using objects instead:

``````class Tree:
def __init__(self, label, branches=[]):
for b in branches:
assert isinstance(b, Tree)
self.label = label
self.branches = branches

def is_leaf(self):
return not self.branches``````

With this implementation, we can mutate a tree using attribute assignment, which wasn't possible in the previous implementation using lists. That's why we sometimes call these objects "mutable trees."

``````>>> t = Tree(3, [Tree(4), Tree(5)])
>>> t.label = 5
>>> t.label
5``````

### Q6: Make Even

Define a function `make_even` which takes in a tree `t` whose values are integers, and mutates the tree such that all the odd integers are increased by 1 and all the even integers remain the same.

Run in 61A Code

Implement `add_d_leaves`, a function that takes in a `Tree` instance `t` and a number `v`.

We define the depth of a node in `t` to be the number of edges from the root to that node. The depth of root is therefore 0.

For each node in the tree, you should add `d` leaves to it, where `d` is the depth of the node. Every added leaf should have a label of `v`. If the node at this depth has existing branches, you should add these leaves to the end of that list of branches.

For example, you should be adding 1 leaf with label `v` to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Here is an example of a tree `t`(shown on the left) and the result after `add_d_leaves` is applied with `v` as 5. Try drawing out the second doctest to visualize how the function is mutating `t3`.

Hint: Use a helper function to keep track of the depth!

Run in 61A Code

# Efficiency (Orders of Growth)

When we talk about the efficiency of a function, we are often interested in the following: as the size of the input grows, how does the runtime of the function change? And what do we mean by runtime?

Example 1: `square(1)` requires one primitive operation: multiplication. `square(100)` also requires one. No matter what input `n` we pass into `square`, it always takes a constant number of operations (1). In other words, this function has a runtime complexity of Θ(1).

As an illustration, check out the table below:

input function call return value operations
1 `square(1)` 1*1 1
2 `square(2)` 2*2 1
... ... ... ...
100 `square(100)` 100*100 1
... ... ... ...
n `square(n)` n*n 1

Example 2: `factorial(1)` requires one multiplication, but `factorial(100)` requires 100 multiplications. As we increase the input size of n, the runtime (number of operations) increases linearly proportional to the input. In other words, this function has a runtime complexity of Θ(`n`).

As an illustration, check out the table below:

input function call return value operations
1 `factorial(1)` 1*1 1
2 `factorial(2)` 2*1*1 2
... ... ... ...
100 `factorial(100)` 100*99*...*1*1 100
... ... ... ...
n `factorial(n)` n*(n-1)*...*1*1 n

Example 3: Consider the following function:

``````def bar(n):
for a in range(n):
for b in range(n):
print(a,b)``````

`bar(1)` requires 1 print statements, while `bar(100)` requires `100*100 = 10000` print statements (each time `a` increments, we have 100 print statements due to the inner for loop). Thus, the runtime increases quadratically proportional to the input. In other words, this function has a runtime complexity of Θ(`n^2`).

input function call operations (prints)
1 `bar(1)` 1
2 `bar(2)` 4
... ... ...
100 `bar(100)` 10000
... ... ...
n `bar(n)` n^2

Example 4: Consder the following function:

``````def rec(n):
if n == 0:
return 1
else:
return rec(n - 1) + rec(n - 1)``````

`rec(1)` requires one addition, as it returns `rec(0) + rec(0)`, and `rec(0)` hits the base case and requires no further additions. but `rec(4)` requires `2^4 - 1` = 15 additions. To further understand the intuition, we can take a look at the recurisve tree below. To get `rec(4)`, we need one addition. We have two calls to `rec(3)`, which each require one addition, so this level needs two additions. Then we have four calls to `rec(2)`, so this level requires four additions, and so on down the tree. In total, this adds up to 1 + 2 + 4 + 8 = 15 additions. As we increase the input size of n, the runtime (number of operations) increases exponentially proportional to the input. In other words, this function has a runtime complexity of Θ(`2^n`).

As an illustration, check out the table below:

input function call return value operations
1 `rec(1)` 2 1
2 `rec(2)` 4 3
... ... ... ...
10 `rec(10)` 1024 1023
... ... ... ...
n `rec(n)` `2^n` `2^n`

Here are some general guidelines for finding the order of growth for the runtime of a function:

• If the function is recursive or iterative, you can subdivide the problem as seen above:

• Count the number of recursive calls/iterations that will be made in terms of input size `n`.
• Find how much work is done per recursive call or iteration in terms of input size `n`.
• The answer is usually the product of the above two, but be sure to pay attention to control flow!
• If the function calls helper functions that are not constant-time, you need to take the runtime of the helper functions into consideration.
• We can ignore constant factors. For example `1000000n` and `n` steps are both linear.
• We can also ignore smaller factors. For example if `h` calls `f` and `g`, and `f` is Quadratic while `g` is linear, then `h` is Quadratic.
• For the purposes of this class, we take a fairly coarse view of efficiency. All the problems we cover in this course can be grouped as one of the following:

• Constant: the amount of time does not change based on the input size. Rule: `n --> 2n` means `t --> t`.
• Logarithmic: the amount of time changes based on the logarithm of the input size. Rule: `n --> 2n` means `t --> t + k`.
• Linear: the amount of time changes with direct proportion to the size of the input. Rule: `n --> 2n` means `t --> 2t`.
• Quadratic: the amount of time changes based on the square of the input size. Rule: `n --> 2n` means `t --> 4t`.
• Exponential: the amount of time changes with a power of the input size. Rule: `n --> n + 1` means `t --> 2t`.

### Q8: WWPD: Orders of Growth

What is the worst case (i.e. when `n` is prime) order of growth of `is_prime` in terms of `n`?

``````def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True``````

Choose one of:

• Constant
• Logarithmic
• Linear
• Exponential
• None of these

What is the order of growth of `bar` in terms of `n`?

``````def bar(n):
i, sum = 1, 0
while i <= n:
sum += biz(n)
i += 1
return sum

def biz(n):
i, sum = 1, 0
while i <= n:
sum += i**3
i += 1
return sum``````

Choose one of:

• Constant
• Logarithmic
• Linear
What is the order of growth of `foo` in terms of `n`, where `n` is the length of `lst`? Assume that slicing a list and calling `len` on a list can both be done in constant time. Write your answer in Θ notation.
``````def foo(lst, i):