Practice problems: Exam 2

This set of practice problems will allow you to test your understanding of some the material we have covered this quarter. While these problems will be good practice for Exam #2, we do not promise that they cover the full range of topics that might appear on the exam.

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

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 mystery0(N):
    if N < 1:
      return
    mystery0(N-1)
    print(N)
    mystery0(N-2)

print("Warmup exercise #1")
mystery0(4)

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

def mystery1(s, c, d, x):
    if s == "":
        return x
    elif s[0] == c:
        return mystery1(s[1:], c, d, x+1)
    elif s[0] == d:
        if x > 0:
            return mystery1(s[1:], c, d, x-1)        
        return -1
    else:
        return mystery1(s[1:], c, d, x)


def recursion_warmup():
    output_str = 'mystery1("{}", "a", "b", 0): {}'
    for s in ["ab", "abab", "abaab", "ababb", "ababaa"]:
        print(output_str.format(s,  mystery1(s, "a", "b", 0)))

print("Warmup exercise #2")
recursion_warmup()

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

def check_match(pattern, s):
   if (re.search(pattern, s)):
       print("{}: matches".format(s))

def reg_ex_warmup():
   pattern = "[a-zA-Z]\w*(\.[a-zA-Z]\w*)?\(\)"

   check_match(pattern, "abc()")
   check_match(pattern, "abc.()")
   check_match(pattern, "abc.3()")
   check_match(pattern, "abc.r3()")


print("Warmup exercise #3")
reg_ex_warmup()

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

def functional_programming_warmup():
    return map(lambda x: x + 1, 
               filter(lambda x: x % 3 == 0, range(0, 9)))

print("Warmup exercise #4")
l = functional_programming_warmup()
print(list(l))

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

def mystery2(fn, N):
    def g(x):
        for i in range(N):
            x = fn(x)
        return x
    return lambda y: g(y*2)


print("Warmup exercise #5")
f = mystery2(lambda x: x+1, 10)
print(f(10))

The following programming problems are on the Kattis site. If you have not already done so, please make sure you have read our Using Kattis page, which explains certain aspects of solving problems on Kattis.

Programming problem #1: Black Friday

Programming problem #2: Ferry Loading 4

Programming problem #3: Permutation Encryption

Programming problem #4: Torn to Pieces This question is challenging. We recommend writing two functions: one that computes a dictionary that maps a station to a list of the stations to which it is directly connected and another that looks for a path between two stations.

Programming problem #5: Shortest Manhattan Distance. This problem is from a previous CS 121 exam.

Programming problem #6: It’s All About the Miles. This problem is also from a previous CS 121 exam.