Practice problems: Week 6

This set of practice problems will allow you to test your understanding of recursion.

To get started run git pull upstream master, which will pick up a directory named pp5.

As usual, the problems are broken up into two parts: a set of “be-a-computer” warm-up exercises and a set of programming problems. For the programming problems, we provide the code that handles the input/output of the problem. Make sure you read the comments in the provided code so you understand exactly what part of the code you need to modify.

Warm-up exercise #1: What is the output of the following code?

def mystery(a, b, c, d):
  if c == 0:
    return d
  elif c % 2 == 0:
    return b + mystery(a, b, c - 2, d)
  else:
    return a + mystery(a, b, c - 1, d)

print("Warmup Exercise #1")
print(mystery("x", "y", 6, "z"))
print(mystery("x", "y", 5, "z"))
print()

Warm-up exercise #2: What is the output of the following code?

def flip(s, a):
  if a == 0:
    return s
  for i in range(a):
    if s[i] == "*":
      s[i] = "-"
    else:
      s[i] = "*"
  return flip(s, a//2)

print("Warmup Exercise #2")
s = []
for i in range(64):
  s.append("*")
s = flip(s, 64)
t = ""
for c in s:
  t = t + c
print(t)

Some of the programming problems are taken from a placement exam; you can ignore the warning about getting “zero points”. As usual, these practice problems are not graded.

Please remember you can find instructions on how to test and submit the Kattis problems in our Using Kattis page.

We have included sample inputs and outputs for the Kattis programming problems in the distribution to allow you test your code on the sample data before trying it out on Kattis. Here is an example use of a sample input file for the first programming problem:

python3 gcd.py < gcd-sample/gcd-001.in

The corresponding output can be found in the file gcd-sample/gcd-001.ans.

We expect you to write recursive solutions for all of these problem.

Programming problem #1: Dijkstra’s Other Algorithm

Programming problem #2: Don’t Be Such a Square

Programming problem #3: Ninety-One

Programming problem #4: Line Them Up