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

).

- The max_product is just the element in that list (

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

.

- We just want to return 1, since

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