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!

YouTube link

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].

Run in 61A Code

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.

Run in 61A Code

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.

Run in 61A Code

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.

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.

Run in 61A Code

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.

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

Run in 61A Code

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.

Run in 61A Code

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

Run in 61A Code

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.
Run in 61A Code

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.

Do not return anything! every_other should mutate the original list.

Run in 61A Code

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.

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

raise IndexError('Out of bounds!')
Run in 61A Code