# Lab 4: Sequences, Trees lab04.zip

Due by 11:59pm on Friday, July 5.

## Starter Files

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

# Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.

## Lists

A list is a data structure that can hold an ordered collection of items. These items, known as elements, can be of any data type, including numbers, strings, or even other lists. A comma-separated list of expressions in square brackets creates a list:

``````>>> list_of_values = [2, 1, 3, True, 3]
>>> nested_list = [2, [1, 3], [True, [3]]]``````

Each position in a list has an index, with the left-most element indexed `0`.

``````>>> list_of_values[0]
2
>>> nested_list[1]
[1, 3]``````

A negative index counts from the end, with the right-most element indexed `-1`.

``````>>> nested_list[-1]
[True, [3]]``````

Adding lists creates a longer list containing the elements of the added lists.

``````>>> [1, 2] + [3] + [4, 5]
[1, 2, 3, 4, 5]``````

## List Comprehensions

A list comprehension describes the elements in a list and evaluates to a new list containing those elements.

There are two forms:

``````[<expression> for <element> in <sequence>]
[<expression> for <element> in <sequence> if <conditional>]``````

Here's an example that starts with `[1, 2, 3, 4]`, picks out the even elements `2` and `4` using `if i % 2 == 0`, then squares each of these using `i*i`. The purpose of `for i` is to give a name to each element in `[1, 2, 3, 4]`.

``````>>> [i*i for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]``````

This list comprehension evaluates to a list of:

• The value of `i*i`
• For each element `i` in the sequence `[1, 2, 3, 4]`
• For which `i % 2 == 0`

In other words, this list comprehension will create a new list that contains the square of every even element of the original list `[1, 2, 3, 4]`.

We can also rewrite a list comprehension as an equivalent `for` statement, such as for the example above:

``````>>> result = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         result = result + [i*i]
>>> result
[4, 16]``````

## List Slicing

To create a copy of part or all of a list, we can use list slicing. The syntax to slice a list `lst` is: `lst[<start index>:<end index>:<step size>]`.

This expression evaluates to a new list containing the elements of `lst`:

• Starting at and including the element at `<start index>`.
• Up to but not including the element at `<end index>`.
• With `<step size>` as the difference between indices of elements to include.

If the start, end, or step size are not explicitly specified, Python has default values for them. A negative step size indicates that we are stepping backwards through a list when including elements.

``````>>> lst = [6, 5, 4, 3, 2, 1, 0]
>>> lst[:3]     # Start index defaults to 0
[6, 5, 4]
>>> lst[3:]     # End index defaults to len(lst)
[3, 2, 1, 0]
>>> lst[:]      # Creates a copy of the list
[6, 5, 4, 3, 2, 1, 0]
>>> lst[:] == lst
True
>>> lst[:] is lst
False
>>> lst[::-1]   # Make a reversed copy of the entire list
[0, 1, 2, 3, 4, 5, 6]
>>> lst[::2]    # Skip every other; step size defaults to 1 otherwise
[6, 4, 2, 0]``````

## Dictionaries

A dictionary contains key-value pairs and allows the values to be looked up by their key using square brackets. Each key must be unique.

``````>>> d = {2: 4, 'two': ['four'], (1, 1): 4}
>>> d[2]
4
>>> d['two']
['four']
>>> d[(1, 1)]
4``````

The sequence of keys or values or key-value pairs can be accessed using `.keys()` or `.values()` or `.items()`.

``````>>> for k in d.keys():
...     print(k)
...
2
two
(1, 1)
>>> for v in d.values():
...     print(v)
...
4
['four']
4
>>> for k, v in d.items():
...     print(k, v)
...
2 4
two ['four']
(1, 1) 4``````

You can check whether a dictionary contains a key using `in`:

``````>>> 'two' in d
True
>>> 4 in d
False``````

A dictionary comprehension is an expression that evaluates to a new dictionary.

``````>>> {3*x: 3*x + 1 for x in range(2, 5)}
{6: 7, 9: 10, 12: 13}``````

## Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

# Required Questions

## Sequences and Containers

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

### Q1: WWPD: Lists & Ranges

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

``python3 ok -q lists-wwpd -u``

Predict what Python will display when you type the following into the interactive interpreter. Then try it to check your answers.

``````>>> s = [7//3, 5, [4, 0, 1], 2]
>>> s[0]
______2
>>> s[2]
______[4, 0, 1]
>>> s[-1]
______2
>>> len(s)
______4
>>> 4 in s
______False
>>> 4 in s[2]
______True
>>> s[2] + [3 + 2]
______[4, 0, 1, 5]
>>> 5 in s[2]
______False
>>> s[2] * 2
______[4, 0, 1, 4, 0, 1]
>>> list(range(3, 6))
______[3, 4, 5]
>>> range(3, 6)
______range(3, 6)
>>> r = range(3, 6)
>>> [r[0], r[2]]
______[3, 5]
>>> range(4)[-1]
______3``````

### Q2: Dictionaries

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

``python3 ok -q pokemon -u``

``````>>> pokemon = {'pikachu': 25, 'dragonair': 148, 'mew': 151}
>>> pokemon['pikachu']
______25
>>> len(pokemon)
______3
>>> 'mewtwo' in pokemon
______False
>>> 'pikachu' in pokemon
______True
>>> 25 in pokemon
______False
>>> 148 in pokemon.values()
______True
>>> 151 in pokemon.keys()
______False
>>> 'mew' in pokemon.keys()
______True``````

### Q3: Flatten

Write a function `flatten` that takes in a list `s` and returns a new list that is the "flattened" version of `s`. You should not modify the original list.

Note: The input list may be deeply nested, meaning that there could be multiple layers of lists within lists. Make sure your solution supports this.

Hint: you can check if something is a list by using the built-in `type` function. For example:

``````>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True``````
``````def flatten(s):
"""Returns a flattened version of list s.

>>> flatten([1, 2, 3])
[1, 2, 3]
>>> deep = [1, [[2], 3], 4, [5, 6]]
>>> flatten(deep)
[1, 2, 3, 4, 5, 6]
>>> deep                                # input list is unchanged
[1, [[2], 3], 4, [5, 6]]
>>> very_deep = [['m', ['i', ['n', ['m', 'e', ['w', 't', ['a'], 't', 'i', 'o'], 'n']], 's']]]
>>> flatten(very_deep)
['m', 'i', 'n', 'm', 'e', 'w', 't', 'a', 't', 'i', 'o', 'n', 's']
"""
``````

Use Ok to test your code:

``python3 ok -q flatten``

### Q4: Merge

Implement `merge`, which takes 2 sorted lists of numbers `s` and `t`. It returns a new list that contains all the elements in both `s` and `t` in sorted order. Do not remove duplicates: the length of the result should be `len(s) + len(t)`. Use recursion (`while` or `for` loops are not allowed).

``````def merge(s, t):
"""Merges two sorted lists.

>>> s1 = [1, 3, 5]
>>> s2 = [2, 4, 6]
>>> merge(s1, s2)
[1, 2, 3, 4, 5, 6]
>>> s1
[1, 3, 5]
>>> s2
[2, 4, 6]
>>> merge([], [2, 4, 6])
[2, 4, 6]
>>> merge([1, 2, 3], [])
[1, 2, 3]
>>> merge([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
>>> merge([2, 3, 4], [2, 4, 6])
[2, 2, 3, 4, 4, 6]
>>> from construct_check import check
>>> check(LAB_SOURCE_FILE, 'merge', ['While', 'For'])    # ban iteration
True
"""
``````

Use Ok to test your code:

``python3 ok -q merge``

## Trees

Consult the drop-down if you need a refresher on trees. It's okay to skip directly to the questions and refer back here should you get stuck.

A path is a sequence of trees in which each is the parent of the next.

A `tree` is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your `cs61a` folder, you have folders separating your `projects`, `lab` assignments, and `homework`. The next level is folders that separate different assignments, `hw01`, `lab01`, `hog`, etc., and inside those are the files themselves, including the starter files and `ok`. Below is an incomplete diagram of what your `cs61a` directory might look like.

As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.

For a tree `t`:

• Its root label can be any value, and `label(t)` returns it.
• Its branches are trees, and `branches(t)` returns a list of branches.
• An identical tree can be constructed with `tree(label(t), branches(t))`.
• You can call functions that take trees as arguments, such as `is_leaf(t)`.
• That's how you work with trees. No `t == x` or `t[0]` or `x in t` or `list(t)`, etc.
• There's no way to change a tree (that doesn't violate an abstraction barrier).

Here's an example tree `t1`, for which its branch `branches(t1)[1]` is `t2`.

``````t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])``````

### Q5: Size

Define the function `size_of_tree`, which takes in a tree `t` and returns the number of entries it contains.

``````def size_of_tree(t):
"""Return the number of entries in the tree.
>>> 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
>>> size_of_tree(numbers)
7
"""
``````

Use Ok to test your code:

``python3 ok -q size_of_tree``

### Q6: Replace Loki at Leaf

Define `replace_loki_at_leaf`, which takes a tree `t` and a value `lokis_replacement`. `replace_loki_at_leaf` returns a new tree that's the same as `t` except that every leaf label equal to `"loki"` has been replaced with `lokis_replacement`.

If you want to learn about the Norse mythology referenced in this problem, you can read about it here.

``````  def replace_loki_at_leaf(t, lokis_replacement):
"""Returns a new tree where every leaf value equal to "loki" has
been replaced with lokis_replacement.

>>> yggdrasil = tree('odin',
...                  [tree('balder',
...                        [tree('loki'),
...                         tree('freya')]),
...                   tree('frigg',
...                        [tree('loki')]),
...                   tree('loki',
...                        [tree('sif'),
...                         tree('loki')]),
...                   tree('loki')])
>>> laerad = copy_tree(yggdrasil)    # copy yggdrasil for testing purposes
>>> print_tree(replace_loki_at_leaf(yggdrasil, 'freya'))
odin
balder
freya
freya
frigg
freya
loki
sif
freya
freya
>>> laerad == yggdrasil    # Make sure original tree is unmodified
True
"""
``````

Use Ok to test your code:

``python3 ok -q replace_loki_at_leaf``

You can locally check your score on each question of this assignment by running

``python3 ok --score``

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

# Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.

# Optional Questions

### Q7: Divide

Implement `divide`, which takes two lists of positive integers `quotients` and `divisors`. It returns a dictionary whose keys are the elements of `quotients`. For each key `q`, its corresponding value is a list of all the elements of `divisors` that can be evenly divided by `q`.

Hint: The value for each key needs be a list, so list comprehension might be useful here.

``````def divide(quotients, divisors):
"""Return a dictonary in which each quotient q is a key for the list of
divisors that it divides evenly.

>>> divide([3, 4, 5], [8, 9, 10, 11, 12])
{3: [9, 12], 4: [8, 12], 5: [10]}
>>> divide(range(1, 5), range(20, 25))
{1: [20, 21, 22, 23, 24], 2: [20, 22, 24], 3: [21, 24], 4: [20, 24]}
"""
return {____: ____ for ____ in ____}
``````

Use Ok to test your code:

``python3 ok -q divide``