CS 61A Final Review solutions - Santa Clara University COMPUTER MISC

CS 61A Final Review Fall 2019 Discussion 14: December 4, 2019 Solutions 1 Recursion 1.1 (Adapted from Fall 2013) Fill in the blanks in the implementation of paths, which takes as input two positive integers x and y. ...

CS 61A Final Review Fall 2019 Discussion 14: December 4, 2019 Solutions 1 Recursion 1.1 (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] def paths(x, y): Return a list of ways to reach y from x by repeated incrementing or doubling. >>> paths(3, 5) [[3, 4, 5]] >>> sorted(paths(3, 6)) [[3, 4, 5, 6], [3, 6]] >>> sorted(paths(3, 9)) [[3, 4, 5, 6, 7, 8, 9], [3, 4, 8, 9], [3, 6, 7, 8, 9]] >>> paths(3, 3) # No calls is a valid path [[3]] if _________________________: return ______________________________________________ elif _______________________: return ______________________________________________ else: a = _________________________________________________ b = _________________________________________________ return ______________________________________________ def paths(x, y): if x > y: return [] elif x == y: return [[x]] else: 2 Final Review a = paths(x + 1, y) b = paths(x * 2, y) return [[x] + subpath for subpath in a + b] Final Review 3 1.2 We will now write one of the faster sorting algorithms commonly used, known as merge sort. Merge sort works like this: 1. If there is only one (or zero) item(s) in the sequence, it is already sorted! 2. If there are more than one item, then we can split the sequence in half, sort each half recursively, then merge the results, using the merge procedure from earlier in the notes. The result will be a sorted sequence. Using the algorithm described, write a function mergesort(seq) that takes an unsorted sequence and sorts it. def mergesort(seq):