# Rao Discussion 9: Midterm Review

This discussion worksheet is for the Rao offering of CS 61A. Your work is not graded and you do not need to submit anything.

This discussion is optional: that means that attendance is not expected, and you will receive no credit for attending this discussion.

Your TA will not be able to get to all of the problems on this worksheet so feel free to work through the remaining problems on your own. Bring any questions you have to office hours or post them on Ed. Good luck on the midterm!

# Fun

### Q1: Around and Around

Berkeley students can juggle a lot of responsibilities. But can they juggle balls? Your TA has brought some tennis balls for you to use. Let's learn to juggle!

#### 0. Get comfortable

Get into pairs, and introduce yourselves if you don't already know each other. Take a ball and toss it from hand to hand in whatever way feels right — get a feel for things!

#### 1. One ball

Now that you're comfortable with the feel of the ball, let's practice our one ball toss. Take a single ball and toss it from one hand to the other. The ball should reach its apex above your opposite shoulder, and you should catch it slightly outside of that shoulder.

Getting a solid, high throw is crucial here! Don't cut corners!

You should feel like you're "scooping" inward and upward as you do the throws. This will help you transition from catching to throwing.

After you do this for a minute, have one partner stop juggling to observe the other and provide guidance and feedback. Then, switch roles.

#### 2. Two balls

Let's double the number of balls we're using. To get the two-ball throw down, start by tossing one ball from hand to hand. When that ball reaches its apex, throw the second ball!

If you're having trouble throwing the second ball, don't even worry about catching the first one. Your body will know how to catch it. The throw is the hardest part! One tip is to say "left right" or "right left" as you throw the two balls.

Get comfortable throwing two balls, and consider switching up which hand you start with. After you do this for a minute, have one partner stop juggling to observe the other and provide guidance and feedback. Then, switch roles.

#### 3. Three balls

Let's add the final ball. Start with two balls in your preferred hand and one ball in your other hand. Throw the two balls as before, but now toss the third ball when the second one reaches its apex!

Again, the throw is the hardest part! Consider saying "left right left" or "right left right" as you throw to get it into your head.

After you do this for a minute, have one partner stop juggling to observe the other and provide guidance and feedback. Then, switch roles.

#### 4. Cascade

Now, all you have to do is keep the cycle going! If you're still having trouble with this, feel free to take some balls home and practice.

# Recursion

### Q2: Paths List

(Adapted from Fall 2013) Fill in the blanks in the implementation of `paths`

, which
takes as input two positive integers `x`

and `y`

. It returns a list of paths, where
each path is a list containing steps to reach `y`

from `x`

by repeated incrementing or
doubling. For instance, we can reach 9 from 3 by incrementing to 4, doubling to 8,
then incrementing again to 9, so one path is [3, 4, 8, 9].

# Trees

### Q3: Widest Level

Write a function that takes a `Tree`

object and returns the
elements at the depth with the most elements.

In this problem, you may find it helpful to use the second optional argument to
`sum`

, which provides a starting value. All items in the sequence to be
summed will be concatenated to the starting value. By default, start will
default to 0, which allows you to sum a sequence of numbers. We provide an
example of sum starting with a list, which allows you to concatenate items in a
list.

### Q4: Level Mutation Link

As a reminder, the depth of a node is how far away the node is from the root. We define this as the number of edges between the root to the node. As there are no edges between the root and itself, the root has depth 0.

Given a tree `t`

and a linked list of one-argument functions `funcs`

, write a function that will mutate the labels of `t`

using the function from `funcs`

at the corresponding depth. For example, the label at the root node (with a depth of 0) will be mutated using the function at `funcs.first`

. Assume all of the functions in `funcs`

will be able to take in a label value and return a valid label value.

If `t`

is a leaf and there are more than 1 functions in `funcs`

, all of the remaining functions should be applied in order to the label of `t`

. (See the doctests for an example.) If `funcs`

is empty, the tree should remain unmodified.

# Lists and Mutability

### Q5: Shuffle

Define a function `shuffle`

that takes a sequence with an even number of
elements (cards) and creates a new list that interleaves the elements
of the first half with the elements of the second half.

To interleave two sequences `s0`

and `s1`

is to create a new sequence such that the new sequence contains (in this order) the first element of `s0`

, the first element of `s1`

, the second element of `s0`

, the second element of `s1`

, and so on.

Run in 61A Code

Note:If you're running into an issue where the special heart / diamond / spades / clubs symbols are erroring in the doctests, feel free to copy paste the below doctests into your file as these don't use the special characters and should not give an "illegal multibyte sequence" error.

# Efficiency

### Q6: Bonk

Describe the order of growth of the function below.

```
def bonk(n):
sum = 0
while n >= 2:
sum += n
n = n / 2
return sum
```

Choose one of:

- Constant
- Logarithmic
- Linear
- Quadratic
- Exponential
- None of these

### Q7: Pow

Write the following function so it runs in ϴ(log k) time.

Run in 61A Code

Hint:This can be done using a procedure called repeated squaring.

# Generators

### Q8: Yield, Fibonacci!

Implement `fibs`

, a generator function that takes a one-argument pure function `f`

and yields all Fibonacci numbers `x`

for which `f(x)`

returns a true value.
The Fibonacci numbers begin with 0 and then 1. Each subsequent Fibonacci number is the sum of the
previous two. Yield the Fibonacci numbers in order.

### Q9: Partitions

Tree-recursive generator functions have a similar structure to regular
tree-recursive functions. They are useful for iterating over all possibilities.
Instead of building a list of results and returning it, just `yield`

each
result.

You'll need to identify a *recursive decomposition*: how to express the answer
in terms of recursive calls that are simpler. Ask yourself what will be yielded
by a recursive call, then how to use those results.

**Definition.** For positive integers `n`

and `m`

, a *partition* of `n`

using
parts up to size `m`

is an addition expression of positive integers up to `m`

in
non-decreasing order that sums to `n`

.

Implement `partition_gen`

, a generator functon that takes positive `n`

and `m`

.
It yields the partitions of `n`

using parts up to size `m`

as strings.

**Reminder:** For the `partitions`

function we studied in lecture
(video), the recursive decomposition was to
enumerate all ways of partitioning `n`

using at least one `m`

and then to
enumerate all ways with no `m`

(only `m-1`

and lower).

# OOP

### Q10: Mint

A mint is a place where coins are made. In this question, you'll implement a `Mint`

class that can output a `Coin`

with the correct year and worth.

- Each
`Mint`

*instance*has a`year`

stamp. The`update`

method sets the`year`

stamp of the instance to the`present_year`

*class attribute*of the`Mint`

*class*. - The
`create`

method takes a subclass of`Coin`

(*not*an instance!), then creates and returns an*instance*of that class stamped with the`mint`

's year (which may be different from`Mint.present_year`

if it has not been updated.) - A
`Coin`

's`worth`

method returns the`cents`

value of the coin plus one extra cent for each year of age*beyond 50*. A coin's age can be determined by subtracting the coin's year from the`present_year`

class attribute of the`Mint`

class.

# Linked Lists

### Q11: Every Other

Implement `every_other`

, which takes a linked list `s`

. It mutates `s`

such
that all of the odd-indexed elements (using 0-based indexing) are removed from
the list. For example:

```
>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True
```

If `s`

contains fewer than two elements, `s`

remains unchanged.

Run in 61A CodeDo not return anything!

`every_other`

should mutate the original list.

### Q12: Insert

Implement a function `insert`

that takes a `Link`

, a `value`

, and an
`index`

, and inserts the `value`

into the `Link`

at the given `index`

.
You can assume the linked list already has at least one element. Do not
return anything -- `insert`

should mutate the linked list.

Run in 61A Code

Note: If the index is out of bounds, you should raise an`IndexError`

with:`raise IndexError('Out of bounds!')`