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

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

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!

Run in 61A Code

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().__init__()
Butterfly.__init__()
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?

What expression completes the second blank?

What expression completes the third blank?

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?

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.

Run in 61A Code

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.

Run in 61A Code

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.
Run in 61A Code

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. Example Tree

Run in 61A Code

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

What is the efficiency of mod_7?

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