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 CodeNote: 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 CodeHint: 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 ayear
stamp. Theupdate
method sets theyear
stamp of the instance to thepresent_year
class attribute of theMint
class. - The
create
method takes a subclass ofCoin
(not an instance!), then creates and returns an instance of that class stamped with themint
's year (which may be different fromMint.present_year
if it has not been updated.) - A
Coin
'sworth
method returns thecents
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 thepresent_year
class attribute of theMint
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 CodeNote: If the index is out of bounds, you should raise an
IndexError
with:raise IndexError('Out of bounds!')