Due at 11:59pm on 10/01/2015.

Starter Files

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

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

  • Questions 1-3 are designed to help introduce and test your understanding of concepts.
  • To receive credit for this lab, you must complete Questions 4-8 in lab05.py and submit through OK.
  • Questions 9 is extra practice. It can be found in the lab05_extra.py file. It is recommended that you complete this problem on your own time.

Trees

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.

cs61a tree

As you can see, unlike trees in nature, which is where this data structure gets its name from, CS trees are drawn with the root at the top and the leaves at the bottom.

  • node: a single unit in a tree.
  • root: the node at the top of a tree; every tree has one root node.
  • branch: a child of a larger tree; has its own root and possibly branches of its own.
  • subtree: a descendant of a larger tree; a subtree is either a branch or a subtree of a branch of a larger tree.
  • leaf: a node that has no branches.

Our tree abstract data type consists of a root node and a list of its branches. To create a tree and access its root and branches, use the following constructor and selectors:

  • Constructor

    • tree(root, branches=[]): creates a tree object with the given root and list of branches.
  • Selectors

    • root(tree): returns the value of the root of the tree.
    • branches(tree): returns the list of branches of the given tree.
    • is_leaf(tree): returns True if tree's list of branches is empty, and False otherwise.

For example, the tree generated by

t = tree(1, [tree(2),
             tree(3, [tree(4), tree(5)]),
             tree(6, [tree(7)])])

would look like this:

   1
 / | \
2  3  6
  / \  \
 4   5  7

It may be easier to visualize this translation by formatting the code like this:

t = tree(1,
         [tree(2),
          tree(3,
               [tree(4),
                tree(5)]),
          tree(6,
               [tree(7)])])

To extract the number 3 from this tree, which is the value of the root of its second branch, we would do this:

root(branches(t)[1])

The print_tree function prints out a tree in a human-readable form. The exact form follows the pattern illustrated above, where the root is unindented, and each of its branches is indented one level further.

numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(root(t)))
    for branch in branches(t):
        print_tree(branch, indent + 1)

Question 1: Height & Depth

The depth of a node in a tree is defined as the number of edges between that node and the root. The root has depth 0, its children have depth 1, and so on.

The height of a tree is the depth of the lowest leaf (furthest away from the root).

Test your understanding of depth and height with OK tests using the following command:

python3 ok -q height_depth -u

Question 2: Tree Structure

As described above, trees are constructed recursively with smaller subtrees using the constructor:

tree(root, branches=[])

Test your understanding of how trees are constructed in Python by examining trees and deciding which of the choices of Python code matches that tree:

python3 ok -q structure -u

Question 3: Tree Height

We have now defined height in the context of trees. Consider the following function that computes the height of any tree.

def height(t):
    if is_leaf(t):
        return 0
    return 1 + max([height(b) for b in branches(t)])

Test your understanding of how this function works for any tree constructed in Python:

python3 ok -q height -u
>>> from lab05 import *
>>> def height(t):
...     if is_leaf(t):
...         return 0
...     return 1 + max([height(b) for b in branches(t)])
>>> t = tree(1, [tree(2, [tree(3)])])
>>> height(t)
______
2
>>> t = tree(1, [tree(2), tree(3, [tree(5)]), tree(4)]) >>> height(t)
______
2
>>> t = tree(1, [tree(2), tree(3, [tree(5)])]) >>> height(t)
______
2
>>> t = tree(1) >>> height(t)
______
0
>>> from lab05 import *
>>> def height(t):
...     if is_leaf(t):
...         current_height = 0
...     else:
...         current_height = 1 + max([height(subtree) for subtree in subtrees(t)])
...     print(current_height)
...     return current_height
>>> t = tree(1, [tree(2, [tree(3)])])
>>> height(t)
______
0 1 2 2
>>> t = tree(1, [tree(2), tree(3, [tree(5)]), tree(4)]) >>> height(t)
______
0 0 1 0 2 2
>>> t = tree(1, [tree(2), tree(3, [tree(5)])]) >>> height(t)
______
0 0 1 2 2

pyTunes

The CS 61A staff has created a music library called pyTunes. pyTunes organizes songs in folders that are labeled by category — in other words, in a tree! The value at the root of the tree is your account name, which branches out into a hierarchy of categories: genres, artists, and albums, in that order. Songs (leaves in the tree) can be stored at any of these levels. A category cannot be empty (i.e. there will never be a node for a genre, artist, or album with no branches).

Question 4: Create pyTunes

All pyTunes accounts come with the free songs below. Define the function make_pytunes, which takes in username and creates this tree:

pytunes tree

The doctest below shows the print_tree representation of a default pyTunes tree.

def make_pytunes(username):
    """Return a pyTunes tree as shown in the diagram with USERNAME as the value
    of the root.

    >>> pytunes = make_pytunes('i_love_music')
    >>> print_tree(pytunes)
    i_love_music
      pop
        justin bieber
          single
            what do you mean?
        2015 pop mashup
      trance
        darude
          sandstorm
    """
"*** YOUR CODE HERE ***"
return tree(username, [tree('pop', [tree('justin bieber', [tree('single', [tree('what do you mean?')])]), tree('2015 pop mashup')]), tree('trance', [tree('darude', [tree('sandstorm')])])])

Use OK to test your code:

python3 ok -q make_pytunes

Question 5: Number of Songs

A pyPod can only hold 10 songs, and you need to find out whether or not all the songs in your pyTunes account will fit. Define the function num_songs, which takes in a pyTunes tree t and returns the number of songs in t. Recall that there are no empty directories in pyTunes, so all leaves in t are songs.

Hint: You can use is_leaf to check whether a given tree is a leaf.

>>> no_branches = tree(1)
>>> is_leaf(no_branches)
True
>>> is_leaf(tree(5, [tree(3), tree(4)]))
False
def num_songs(t):
    """Return the number of songs in the pyTunes tree, t.

    >>> pytunes = make_pytunes('i_love_music')
    >>> num_songs(pytunes)
    3
    """
"*** YOUR CODE HERE ***"
if is_leaf(t): return 1 return sum([num_songs(b) for b in branches(t)]) # Alternate solution def num_songs(t): if is_leaf(t): return 1 leaves = 0 for b in branches(t): leaves += num_songs(b) return leaves

Use OK to test your code:

python3 ok -q num_songs

Question 6: Ctrl + F

In order to check if your pyTunes account contains a certain song or category, define the function find. It takes in a pyTunes tree t and returns True if t contains a either a song or a category called target and False otherwise.

def find(t, target):
    """Returns True if t contains a node with the value TARGET and False
    otherwise.

    >>> my_account = tree('kpop_king',
    ...                    [tree('korean',
    ...                          [tree('gangnam style'),
    ...                           tree('wedding dress')]),
    ...                     tree('pop',
    ...                           [tree('t-swift',
    ...                                [tree('blank space')]),
    ...                            tree('uptown funk'),
    ...                            tree('see you again')])])
    >>> find(my_account, 'korean')
    True
    >>> find(my_account, 'blank space')
    True
    >>> find(my_account, 'bad blood')
    False
    """
"*** YOUR CODE HERE ***"
if root(t) == target: return True if is_leaf(t): return False return any([find(b, target) for b in branches(t)]) # Alternate solution def find(t, target): if root(t) == target: return True for b in branches(t): if find(b, target): return True return False

Use OK to test your code:

python3 ok -q find

Question 7: Add Song

Of course, you should be able to add music to your pyTunes. Write add_song to add song to the given category. You should not be able to add a song under a song or to a category that doesn't exist. See the doctests for examples.

def add_song(t, song, category):
    """Returns a new tree with SONG added to CATEGORY. Assume the CATEGORY
    already exists.

    >>> indie_tunes = tree('indie_tunes',
    ...                  [tree('indie',
    ...                    [tree('vance joy',
    ...                       [tree('riptide')])])])
    >>> new_indie = add_song(indie_tunes, 'georgia', 'vance joy')
    >>> print_tree(new_indie)
    indie_tunes
      indie
        vance joy
          riptide
          georgia

    """
"*** YOUR CODE HERE ***"
if root(t) == category: return tree(root(t), branches(t) + [tree(song)]) kept_branches = [] for b in branches(t): kept_branches += [add_song(b, song, category)] return tree(root(t), kept_branches) # Alternative Solution def add_song(t, song, category): if root(t) == category: return tree(root(t), branches(t) + [tree(song)]) all_branches = [add_song(b, song, category) for b in branches(t)] return tree(root(t), all_branches)

Use OK to test your code:

python3 ok -q add_song

Question 8: Delete

You also want to be able to delete a song or category from your pyTunes. Define the function delete, which takes in a pyTunes tree t and returns a new tree that is the same as t except with target deleted. If target is a genre, artist, or album, delete everything inside of it. It should not be possible to delete the entire account or root of the tree. Deleting all the songs within a category should not remove that category.

def delete(t, target):
    """Returns the tree that results from deleting TARGET from t. If TARGET is
    a category, delete everything inside of it.

    >>> my_account = tree('kpop_king',
    ...                    [tree('korean',
    ...                          [tree('gangnam style'),
    ...                           tree('wedding dress')]),
    ...                     tree('pop',
    ...                           [tree('t-swift',
    ...                                [tree('blank space')]),
    ...                            tree('uptown funk'),
    ...                            tree('see you again')])])
    >>> new = delete(my_account, 'pop')
    >>> print_tree(new)
    kpop_king
      korean
        gangnam style
        wedding dress
    """
"*** YOUR CODE HERE ***"
kept_branches = [] for b in branches(t): if root(b) != target: kept_branches += [delete(b, target)] return tree(root(t), kept_branches) # Alternate solution def delete(t, target): kept_branches = [delete(b, target) for b in branches(t) if root(b) != target] return tree(root(t), kept_branches)

Use OK to test your code:

python3 ok -q delete

Extra Questions

The following questions are for extra practice — they can be found in the the lab05_extra.py file. It is recommended that you complete these problems on your own time.

Question 9: Info

You wish to be able to take a quick look at all the information we have about each song in your library. Define the function info, which takes in a pyTunes tree t and returns a list of all the information about the target. The information about the target are all of the values of the nodes in the path from the root to the target.

def info(t, target):
    """Returns a list of all the information about the song TARGET. If the song
    cannot be found in the tree, return None.

    >>> my_account = tree('inSTRUMental', [
    ...     tree('classical', [
    ...         tree('Tchaikowsky', [
    ...             tree('Piano Concerto No. 1', [
    ...                 tree('Allegro non troppo'),
    ...                 tree('Andantino'),
    ...                 tree('Allegro con fuoco')])]),
    ...         tree('Bruch', [
    ...             tree('Violin Concerto No. 1', [
    ...                 tree('Allegro moderato'),
    ...                 tree('Adagio'),
    ...                 tree('Allegro energico')])])])])
    >>> info(my_account, 'Adagio')
    ['inSTRUMental', 'classical', 'Bruch', 'Violin Concerto No. 1', 'Adagio']
    >>> info(my_account, 'Allegro non troppo')
    ['inSTRUMental', 'classical', 'Tchaikowsky', 'Piano Concerto No. 1', 'Allegro non troppo']
    >>> info(my_account, 'Sandstorm') # Should return None, which doesn't appear in the interpreter
    """
"*** YOUR CODE HERE ***"
if root(t) == target: return [target] elif is_leaf(t): return None for b in branches(t): branch_info = info(b, target) if branch_info is not None: return [root(t)] + branch_info

Use OK to test your code:

python3 ok -q info