# Discussion 7: String Representation, Efficiency, Linked Lists, Mutable Trees

# Discussion 7 Vitamin

To encourage everyone to watch or attend discussion orientation, we have created small discussion vitamins. If you complete 5 of the next 6 vitamins, you can earn one point of extra credit added to your final grade in the course. Please answer all of the questions in this form by **Thursday at 11:59 PM**.

# Representation - Repr and Str

There are two main ways to produce the "string" of an object in Python:
`str()`

and `repr()`

. While the two are similar, they are
used for different purposes. `str()`

is used to describe
the object to the end user in a "Human-readable" form, while `repr()`

can be thought of as
a "Computer-readable" form mainly used for debugging and development.

When we define a class in Python, `str()`

and `repr()`

are
both built-in methods for the class. We can call an object's `str()`

and
`repr()`

by using their respective methods. These methods can be invoked by calling `repr(obj)`

or `str(obj)`

rather than the dot notation format `obj.__repr__()`

or `obj.__str__()`

. In addition, the `print()`

function calls the `str()`

method of the object,
while simply calling the object in interactive mode calls the `repr()`

method.

Here's an example:

```
class Rational:
def __init__(self, numerator, denominator):
self.numerator = numerator
self.denominator = denominator
def __str__(self):
return f'{self.numerator}/{self.denominator}'
def __repr__(self):
return f'Rational({self.numerator},{self.denominator})'
>>> a = Rational(1, 2)
>>> str(a)
'1/2'
>>> repr(a)
'Rational(1,2)'
>>> print(a)
1/2
>>> a
Rational(1,2)
```

## Questions

### Q1: Repr-esentation WWPD

What would Python display?```
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 = []
def add_a(self, a):
self.a.append(a)
def __repr__(self):
print(len(self.a))
ret = ''
for a in self.a:
ret += str(a)
return ret
```

`>>> A('one')`

`>>> print(A('one'))`

`>>> repr(A('two'))`

`>>> b = B()`

```
>>> b.add_a(A('a'))
>>> b.add_a(A('b'))
>>> b
```

# Linked Lists

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:
print('This linked list is empty!')
else:
print('This linked list is not empty!')
```

Check out the implementation of the `Link`

class below:

```
class Link:
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __repr__(self):
if self.rest:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(repr(self.first), rest_str)
def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'
```

## Questions

### Q2: Sum Nums

Write a function that takes in a 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!

**Your Answer**Run in 61A Code

**Solution**

```
def sum_nums(s):
"""
>>> a = Link(1, Link(6, Link(7)))
>>> sum_nums(a)
14
"""
if s == Link.empty:
return 0
return s.first + sum_nums(s.rest)
```

### Q3: (Tutorial) Inheritance Review: That's a Constructor, __init__?

Let's say we want to create a class `Monarch`

that inherits from another class, `Butterfly`

. We've partially written an `__init__`

method for `Monarch`

. For each of the following options, state whether it would correctly complete the method so that every instance of `Monarch`

has all of the instance attributes of a `Butterfly`

instance? You may assume that a monarch butterfly has the default value of 2 wings.

```
class Butterfly():
def __init__(self, wings=2):
self.wings = wings
class Monarch(Butterfly):
def __init__(self):
_________________________________________
self.colors = ['orange', 'black', 'white']
```

`super.__init__()`

`super`

function must be called with parentheses.
`super().__init__()`

`Butterfly.__init__()`

`self`

as an argument.
`Butterfly.__init__(self)`

Some butterflies like the Owl Butterfly have adaptations that allow them to mimic other animals with their wing patterns. Let's write a class for these `MimicButterflies`

. In addition to all of the instance variables of a regular `Butterfly`

instance, these should also have an instance variable `mimic_animal`

describing the name of the animal they mimic. Fill in the blanks in the lines below to create this class.

```
class MimicButterfly(______________):
def __init__(self, mimic_animal):
_______________.__init__()
______________ = mimic_animal
```

What expression completes the first blank?

`Butterfly`

What expression completes the second blank?

`super()`

What expression completes the third blank?

`self.mimic_animal`

### Q4: (Tutorial) Warmup: The Hy-rules of Linked Lists

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

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

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

`ganondorf.rest.rest.first`

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

?

### Q5: (Tutorial) Multiply Lnks

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.

**Your Answer**Run in 61A Code

**Solution**

```
def multiply_lnks(lst_of_lnks):
"""
>>> a = Link(2, Link(3, Link(5)))
>>> b = Link(6, Link(4, Link(2)))
>>> c = Link(4, Link(1, Link(0, Link(2))))
>>> p = multiply_lnks([a, b, c])
>>> p.first
48
>>> p.rest.first
12
>>> p.rest.rest.rest is Link.empty
True
"""
# Implementation Note: you might not need all lines in this skeleton code
product = 1 for lnk in lst_of_lnks: if lnk is Link.empty: return Link.empty product *= lnk.first lst_of_lnks_rests = [lnk.rest for lnk in lst_of_lnks] return Link(product, multiply_lnks(lst_of_lnks_rests)) # For an extra challenge, try writing out an iterative approach as well below!
# Alternate iterative approach
import operator
from functools import reduce
def prod(factors):
return reduce(operator.mul, factors, 1)
head = Link.empty
tail = head
while Link.empty not in lst_of_lnks:
all_prod = prod([l.first for l in lst_of_lnks])
if head is Link.empty:
head = Link(all_prod)
tail = head
else:
tail.rest = Link(all_prod)
tail = tail.rest
lst_of_lnks = [l.rest for l in lst_of_lnks]
return head
```

`Link`

s is empty, we can return the empty linked list as we're not going
to multiply anything.
Otherwise, we compute the product of all the firsts in our list of
`Link`

s. Then, the subproblem we use here is the rest of all the linked
lists in our list of Links. Remember that the result of calling
`multiply_lnks`

will be a linked list! We'll use the product we've
built so far as the first item in the returned `Link`

, and then the
result of the recursive call as the rest of that `Link`

.

The iterative solution is a bit more involved than the recursive solution.
Instead of building the list **backwards** as in the recursive solution (because of the order that the recursive calls result in, the last item in our list will be finished first), we'll build the resulting linked list as we go along.

We use`head`

and `tail`

to track the front and end of the new
linked list we're creating. Our stopping condition for the loop is if any of the
`Link`

s in our list of `Link`

s runs out of items.

Finally, there's some special handling for the first item. We need to update both head and tail in that case. Otherwise, we just append to the end of our list using tail, and update tail.

### Q6: (Tutorial) 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.
**Your Answer**Run in 61A Code

**Solution**

```
def flip_two(s):
"""
>>> one_lnk = Link(1)
>>> flip_two(one_lnk)
>>> one_lnk
Link(1)
>>> lnk = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> flip_two(lnk)
>>> lnk
Link(2, Link(1, Link(4, Link(3, Link(5)))))
"""
# Recursive solution:
if s is Link.empty or s.rest is Link.empty:
return
s.first, s.rest.first = s.rest.first, s.first
flip_two(s.rest.rest)
# For an extra challenge, try writing out an iterative approach as well below!
return # separating recursive and iterative implementations
# Iterative approach
while s is not Link.empty and s.rest is not Link.empty:
s.first, s.rest.first = s.rest.first, s.first
s = s.rest.rest
```

Otherwise, we swap the contents of the first and second items in the list. Since we've handled the first two items, we then need to recurse on

Although the question explicitly asks for a recursive solution, there is also a fairly similar iterative solution (see python solution).

We will advance `s`

until we see there are no more items or there is
only one more Link object to process. Processing each `Link`

involves
swapping the contents of the first and second items in the list (same as the
recursive solution).

# Trees

Recall the tree abstract data type: a tree is defined as having a label and some branches. 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
```

## Questions

### Q7: 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.
**Your Answer**Run in 61A Code

**Solution**

```
def make_even(t):
"""
>>> t = Tree(1, [Tree(2, [Tree(3)]), Tree(4), Tree(5)])
>>> make_even(t)
>>> t.label
2
>>> t.branches[0].branches[0].label
4
"""
if t.label % 2 != 0:
t.label += 1
for branch in t.branches:
make_even(branch)
return
# Alternate Solution
t.label += t.label % 2
for branch in t.branches:
make_even(branch)
return
```

### Q8: (Tutorial) Find Paths

**Hint**: This question is similar to

`find_paths`

on Discussion 05.
Define the procedure `find_paths`

that, given a Tree `t`

and an `entry`

, returns a list of lists containing the nodes along each path from the root of `t`

to `entry`

. You may return the paths in any order.

For instance, for the following tree `tree_ex`

, `find_paths`

should behave as specified in the function doctests.

**Your Answer**Run in 61A Code

**Solution**

```
def find_paths(t, entry):
"""
>>> tree_ex = Tree(2, [Tree(7, [Tree(3), Tree(6, [Tree(5), Tree(11)])]), Tree(1, [Tree(5)])])
>>> find_paths(tree_ex, 5)
[[2, 7, 6, 5], [2, 1, 5]]
>>> find_paths(tree_ex, 12)
[]
"""
paths = []
if t.label == entry: paths.append([t.label]) for b in t.branches: for path in find_paths(b, entry): paths.append([t.label] + path) return paths
```

# Efficiency

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**?

`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). 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 |

`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`

). 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 |

## Questions

### Q9: The First Order...of Growth

What is the efficiency of `rey`

?

```
def rey(finn):
poe = 0
while finn >= 2:
poe += finn
finn = finn / 2
return
```

`finn`

) times,
due to `finn`

being halved in every iteration. This is commonly known as Θ(log(`finn`

)) runtime. Another way of looking at this if you
duplicate the input, we only add a single iteration to the time, which also indicates logarithmic.
What is the efficiency of `mod_7`

?

```
def mod_7(n):
if n % 7 == 0:
return 0
else:
return 1 + mod_7(n - 1)
```