Discussion 06 Guide

2.3: Question 1 • Question 2 • Question 3

2.4: Question 1


Section 2.3 Question 1

Write a function that rotates the elements of a list to the right by k. Elements should not ”fall off”; they should wrap around the beginning of the list. rotate should return a new list. To make a list of n 0’s, you can do this: [0] * n

def rotate(lst, k):
    """ Return a new list, with the same elements
    of lst, rotated to the right k.
    >>> x = [1, 2, 3, 4, 5]
    >>> rotate(x, 3)
    [3, 4, 5, 1, 2]
    """

First, we should define what one rotation is. We are rotating to the right, so the last element of a list becomes the first element of our new, rotated list, and the first len(lst)-1 elements gets pushed over 1 space to the right. Rotating the lst [1, 2, 3, 4, 5] once gives you [5, 1, 2, 3, 4].

Solving with a loop

Since we need to make k rotations, and we know how to make one rotation, we can use a while loop like this:

rotation_num = 0
while rotation_num < k: 
    # TODO: rotate the list once
    rotation_num += 1
return lst

Now, let’s write the code that actually rotates the list once. Here’s what we know:

  • The last element of the list becomes the first
  • The first len(lst) - 1 elements of the list shift their index by +1.
  • We need to make a new list

This leads me to this solution:

    new_lst = 0 * len(lst)
    new_lst[0] = lst[lst(len(lst) - 1)]
    for i in range(1, len(new_lst)):
        new_lst[i] = lst[i - 1]
    lst = new_lst # For the next rotation

Putting it together:

def rotate(lst, k):
    rotation_num = 0
    while rotation_num < k: 
        new_lst = 0 * len(lst)
        new_lst[0] = lst[lst(len(lst) - 1)]
        for i in range(1, len(new_lst)):
            new_lst[i] = lst[i - 1]
        lst = new_lst
        rotation_num += 1
    return lst

You can also do this with list slicing:

    lst = lst[:len(lst) - 1] + lst[:len(lst) - 1]

Solving with Clever List Slicing

def rotate(lst, k):
    return lst[len(lst) - k:] + lst[:len(lst) - k)] # The 0 is implied

What if the k > len(lst)? We use % (modulus).

def rotate(lst, k):
    return lst[(len(lst) - k) % len(lst):] + lst[:(len(lst) - k)) % len(lst)]


Section 2.3 Question 2

Define a function foo that takes in a list lst and returns a new list that keeps only the even-indexed elements of lst and multiplies each of those elements by the corresponding index.

def foo(lst):
    """ 
    >>> x = [1, 2, 3, 4, 5, 6] 
    >>> >>> foo(x)
    [0, 6, 20]
    """
    return [_________________________________________________]

This can be done with a for loop or a list comprehension. Let’s do it with a for loop first:

    new_lst = []
    for i in range(len(lst)):
        if i % 2 == 0:
            new_lst.append(lst[i] + i)
    return new_lst

As a list comprehension:

    return [lst[i] + i for i in range(len(lst)) if i % 2 == 0]


Section 2.3 Question 3

Implement the functions max product, which takes in a list and returns the maximum product that can be formed using nonconsecutive elements of the list. The input list will contain only numbers greater than or equal to 1.

def max_product(lst):
    """Return the maximum product that can be formed using lst
    without using any consecutive numbers
    >>> [10,3,1,9,2] # 10 * 9
    90
    """

This one is quite tough. The crucial part of this problem is that the product can be made up of more that two numbers. In the doctest above, it just so happens that 10 * 9 > 10 * 1 * 2.

Finding the Base Case

So, the base case for this one isn’ super obvious, but let’s consider this cases:

  • A list of length 1.
    • The max_product is just the element in that list (lst[0]).

Reduction

If a list is more than length 1, then we can reduce it down to length 1 by slicing.

Extra Work

We are finding the product of non-consecutive numbers in a list, which means if you are given a list [1, 2, 3, 4, 5], your options are currently 1 * 3, 1 * 4, or 1 * 5. We want the case that yields maximum product, so one recursive call we make will be:

    lst[0] * max(max_product(lst[2:]))

This gives us a new base case (if lst[2:] returns []):

  • A list of length 0.
    • We just want to return 1, since 1 * x = x.

The second recursive call we make will be if we do not use the first number in the list:

    max_product(lst[1:])

And of course, we want the best out of those two recursive calls:

    max(lst[0] * max(max_product(lst[2:])), max_product(lst[1:]))

Putting it Together

    if lst == []:
        return 1
    elif len(lst) == 1:
        return lst[0]
    return max(lst[0] * max(max_product(lst[2:])), max_product(lst[1:]))


Section 2.4 Question 1

An expression tree is a tree that contains a function for each non-leaf root, which can be either '+' or '*'. All leaves are numbers. Implement eval tree, which evaluates an expression tree to its value. You may want to use the functions sum and prod, which take a list of numbers and compute the sum and product respectively.

def eval_tree(tree):
    """Evaluates an expression tree with functions as root
    >>> eval_tree(tree(1))
    1
    >>> expr = tree('*', [tree(2), tree(3)])
    >>> eval_tree(expr)
    6
    >>> eval_tree(tree('+', [expr, tree(4)]))
    10
    """

So first, let’s look at what an simple expression tree looks like:

    *
   / \
  2   3

The expression tree above represents 2 * 3. Now let’s look at a more complex one:

       *
     /   \  
    +     +
   / \   / \
  2   3 1   2

This one represents (2 + 3) * (1 + 2)**. Now you should see how this is a tree, and as a result, recursive.

Finding our Base Case

Question: What tree do we have to do absolutely no work on?

Answer: A leaf (number)! The tree 2 evaluates to the number 2.

    if is_leaf(tree):
        return entry(tree)

Reduction

Like many tree problems, the reduction is simply exploring the children of tree, which are subtrees.

    for c in children(tree):
        return eval_tree(c)

Extra Work

We have two possible cases if our tree is not a leaf: entry(tree) is either '*' or '+'. What we do for either case is obvious (we either sum or prod its children. The tricky part, however, is that we need to know what the children actually evaluate to (in the case of the complex expression tree above). That is where our “reduction” comes into play.

    evaluated_children = [eval_tree(c) for c in children(tree)]
    if entry(tree) == '*':
        return prod(evaluated_children)
    elif entry(tree) == '+':
        return sum(evaluated_children)

Putting it Together

def eval_tree(c):
    if is_leaf(tree):
        return entry(tree)
    evaluated_children = [eval_tree(c) for c in children(tree)]
    if entry(tree) == '*':
        return prod(evaluated_children)
    if entry(tree) == '+':
        return sum(evaluated_children)
back up