CS61A Homework 2
Homework 2: Higher Order Functions hw02.zip
Several doctests refer to these functions:
1  from operator import add, mul 
Getting Started Videos
Parsons Problems
Q1: Count Until Larger
Implement the function count_until_larger
. count_until_larger
takes in a positive integer num
. count_until_larger
counts the distance between the rightmost digit of num
and the nearest greater digit; to do so, the function counts digits from right to left. Once it encounters a digit larger than the rightmost digit, it returns that count. If no such digit exists, then the function returns 1
.
For example, 8117
has a rightmost digit of 7
and returns a count of 3
. 9118117
also returns a count of 3
: for both, the count stops at 8
.
0
should be treated as having no digits and returns a count of 1
.
Consult the following doctests for specific behaviors of count_until_larger
.
1  def count_until_larger(num): 
Q2: Filter Sequence
Write a function filter_sequence
which takes in two integers, start
and stop
, as well as a function cond
, which takes in a single argument and outputs a boolean value. filter_sequence
returns the sum of all digits from start
to stop
(inclusive) for which cond
returns True
.
1  def filter_sequence(cond, start, stop): 
Code Writing Questions
Q3: Hailstone
Douglas Hofstadter’s Pulitzerprizewinning book, Gödel, Escher, Bach, poses the following mathematical puzzle.
 Pick a positive integer
n
as the start.  If
n
is even, divide it by 2.  If
n
is odd, multiply it by 3 and add 1.  Continue this process until
n
is 1.
The number n
will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried – nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.
This sequence of values of n
is often called a Hailstone sequence. Write a function that takes a single argument with formal parameter name n
, prints out the hailstone sequence starting at n
, and returns the number of steps in the sequence:
1  def hailstone(n): 
Hailstone sequences can get quite long! Try 27. What’s the longest you can find?
Note that if
n == 1
initially, then the sequence is one step long.
Use Ok to test your code:
1  python3 ok q hailstone✂️ 
Curious about hailstones or hailstone sequences? Take a look at these articles:
 Check out this article to learn more about how hailstones work!
 In 2019, there was a major development in understanding how the hailstone conjecture works for most numbers!
Q4: Product
The summation(n, term)
function from the higherorder functions lecture adds up term(1) + ... + term(n)
. Write a similar function called product
that returns term(1) * ... * term(n)
.
1  def product(n, term): 
Use Ok to test your code:
1  python3 ok q product✂️ 
Q5: Accumulate
Let’s take a look at how summation
and product
are instances of a more general function called accumulate
, which we would like to implement:
1  def accumulate(merger, start, n, term): 
accumulate
has the following parameters:
term
andn
: the same parameters as insummation
andproduct
merger
: a twoargument function that specifies how the current term is merged with the previously accumulated terms.start
: value at which to start the accumulation.
For example, the result of accumulate(add, 11, 3, square)
is
1  11 + square(1) + square(2) + square(3) = 25 
Note: You may assume that
merger
is commutative. That is,merger(a, b) == merger(b, a)
for alla
,b
, andc
. However, you may not assumemerger
is chosen from a fixed function set and hardcode the solution.
After implementing accumulate
, show how summation
and product
can both be defined as function calls to accumulate
.
Important: You should have a single line of code (which should be a return
statement) in each of your implementations for summation_using_accumulate
and product_using_accumulate
, which the syntax check will check for.
Use Ok to test your code:
1  python3 ok q accumulate 
1 

Bonus Questions
Homework assignments will also contain prior examlevel questions for you to take a look at. These questions have no submission component; feel free to attempt them if you’d like a challenge!
Note that exams from Spring 2020, Fall 2020, and Spring 2021 gave students access to an interpreter, so the question format may be different than other years. Regardless, the questions included remain good examlevel problems doable without access to an interpreter.
 Fall 2019 MT1 Q3: You Again [Higher Order Functions]
 Spring 2021 MT1 Q4: Domain on the Range [Higher Order Functions]
 Fall 2021 MT1 Q1b: tik [Functions and Expressions]