15-112
Spring 19

Home

Syllabus

Schedule

Staff

Gallery

Piazza

Autolab

OH Queue

CMU 15-112: Fundamentals of Programming and Computer Science
Week9 Practice (Due never)

Code Comprehension

Below are a large number of recursive math functions. Try to determine what each function does before and after running the code.

Need help? Watch this video:

# A few example recursive functions. # Can you figure out what each one does, in general? import math def f1(x): if (x == 0): return 0 else: return 1 + f1(x-1) def f2(x): if (x == 0): return 40 else: return 1 + f2(x-1) def f3(x): if (x == 0): return 0 else: return 2 + f3(x-1) def f4(x): if (x == 0): return 40 else: return 2 + f4(x-1) def f5(x): if (x == 0): return 0 else: return x + f5(x-1) # why does this work? def f6(x): if (x == 0): return 0 else: return 2*x-1 + f6(x-1) # why does this work? def f7(x): if (x == 0): return 1 else: return 2*f7(x-1) def f8(x): if (x < 2): return 0 else: return 1 + f8(x//2) def f9(x): if (x < 2): return 1 else: return f9(x-1) + f9(x-2) def f10(x): if (x == 0): return 1 else: return x*f10(x-1) def f11(x, y): if (y < 0): return -f11(x, -y) elif (y == 0): return 0 else: return x + f11(x, y-1) def f12(x,y): if ((x < 0) and (y < 0)): return f12(-x,-y) elif ((x == 0) or (y == 0)): return 0 else: return x+y-1 + f12(x-1, y-1) # why does this work? def f13(L): assert(type(L) == list) if (len(L) < 2): return [ ] else: return f13(L[2:]) + [L[1]] def go(): while True: n = input("Enter function # (1-13, or 0 to quit): ") if (n == "0"): break elif (n == "11"): print("f11(5, 7) ==", f11(5, 7)) elif (n == "12"): print("f12(5, 7) ==", f12(5, 7)) elif (n == "13"): print("f13(list(range(20))) ==", f13(list(range(20)))) else: f = globals()["f"+n] print("f"+n+": ", [f(x) for x in range(10)]) print() go()
5 Reasoning About (Recursive) Code problems

In just a few words of plain English, state what each of the following functions does in general. You will receive no credit for describing the line-by-line low-level behavior of the code. For example:

def mystery(list): count = 0 for value in list: if (value == 0): count += 1 return count

Correct answer: "This function returns the number of 0's in the given list." Or, if you prefer to be succinct, just: "number of 0's".
Incorrect answer (no points): "This function sets count to 0, then sets value to each element in list in turn, and for each value, if it is 0, it adds one to count, and then returns count". This is all true, but completely misses the high-level behavior of the function, and so would receive zero points.

  1. def f(n): # assume n is a non-negative integer if (n < 10): return 1 else: return 1 + f(n//10)
  2. def f(a): # assume a is a list of strings if (len(a) == 0): return "" else: x = f(a[1:]) if (len(x) > len(a[0])): return x else: return a[0]
  3. def f(a): # assume a is a list of integers if (len(a) == 0): return 0 elif (len(a) == 1): return (a[0] % 2) else: i = len(a)//2 return f(a[:i]) + f(a[i:])
  4. def f(n): # assume n is a non-negative integer if (n == 0): return 1 else: return 2*f(n-1)
  5. def f(n): # assume n is a non-negative integer if (n == 0): return 0 else: return f(n-1) + 2*n - 1 # Hint: you may want to try this function with a few sample values. # The answer should quickly become apparent, though you may wish to # think about why the answer is in fact what it is.
Free Response

  1. Partial Permutations
    Write the recursive function permutations(a, k), which modifies the recursive permutations function from the course notes so that it returns all the permutations of length k from the elements in the list a, or the empty list [] if no such permutations exist. For example, permutations([1,2,3,4], 2) would return some ordering of this list:

    [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]

    We say "some ordering" because your list must include the correct permutations, but in any order. And, once again, your solution must be recursive, and in fact it must be an obvious adaptation of the code in the course notes.

    Hint: do not worry about the case where the original list contains duplicate values.

    Note: regarding efficiency, your code should compute the 870-item result to permutations(range(30), 2) almost instantly, and the 117,600-item result to permutations(range(50),3) with at most a couple of seconds delay. In other words, you should not compute all possible permutations, then trim them down to just those of the right size.

  2. twoStackHanoi
    Background: Here, we will consider a modified form of the Towers of Hanoi problem. Given an input n>0, there are 2n discs of increasing size (instead of just n discs of increasing size). There are 3 poles as in the original problem (Pole 0, Pole 1, and Pole 2). We label the discs with numbers {1, 2, 3, ..., 2n}, where the label of a disc corresponds to its size. Initially, the odd-numbered discs (i.e. the discs {1, 3, 5, ..., 2n-1}) are on Pole 0, and the even-numbered discs (i.e. the discs {2, 4, 6, ..., 2n}) are on Pole 2. The goal is to get all the discs on Pole 1 (the middle pole).

    With this in mind, write the function twoStackHanoi(n) that takes a positive int n and returns a list of the moves in order required to solve a 2-stack Hanoi problem as described above (so, to ultimately move the n discs from Pole 0 and the n other discs from Pole 2 all to Pole 1, while also maintaining the Hanoi rule that no disc can be placed on a smaller disc). A "move" will be represented as a tuple (x,y), where x and y are both in the set {0,1,2}, and means to move one disc from Pole x to Pole y.

  3. getCourse(courseCatalog, courseNumber)
    Background: for this problem, we will use a so-called courseCatalog, which for this problem is a recursively-defined list-of-lists like so (this being just an example, your solution must work for any similarly-defined courseCatalog):

    courseCatalog = ["CMU", ["CIT", [ "ECE", "18-100", "18-202", "18-213" ], [ "BME", "42-101", "42-201" ], ], ["SCS", [ "CS", ["Intro", "15-110", "15-112" ], "15-122", "15-150", "15-213" ], ], "99-307", "99-308" ]

    Each level is defined by a list, and the first element of the list is the name of that level ("CMU", "CIT", "ECE", etc). The rest of the elements of a list contain either strings, which are course names offered at that level, or lists, which contain a sub-level. So we see that "99-307" is offered by "CMU", and "15-122" is offered by "CS". Also, the fully-qualified name of a course includes the dot-separated names of all the levels that contain it, in top-down order. Thus, the fully-qualified name of "15-112" is "CMU.SCS.CS.Intro.15-112", and the fully-qualified name of "99-307" is just "CMU.99-307". Finally, you may assume that a course name may not occur more than once in a course catalog.

    With this in mind, write the function getCourse(courseCatalog, courseNumber) that takes a courseCatalog, as defined above, and a courseNumber (as a string, such as "18-100" or "15-112"), and returns the fully-qualified name of the given course, or None if it is not in the catalog. For example, given the courseCatalog above, here are some test cases:
    assert(getCourse(courseCatalog, "18-100") == "CMU.CIT.ECE.18-100") assert(getCourse(courseCatalog, "15-112") == "CMU.SCS.CS.Intro.15-112") assert(getCourse(courseCatalog, "15-213") == "CMU.SCS.CS.15-213") assert(getCourse(courseCatalog, "99-307") == "CMU.99-307") assert(getCourse(courseCatalog, "15-251") == None)