15-110 PS5 Sample Solutions - Spring 2018

1. Homer is demonstrating recursion since the image repeats inside the image.

2. 
(a) 
Move 7 discs to middle: 127
Move largest disc: 1
Move 7 discs to last peg: 127
127 + 1 + 127 = 255

(b) 2**n - 1

(c) Approximately 2.1 * 10**15 years

3. 
(a)
bs_helper(datalist, 12, -1, 7)
bs_helper(datalist, 12, -1, 3)
returns 1

(b)
bs_helper(datalist, 50, 7, 15)
bs_helper(datalist, 50, 7, 11)
bs_helper(datalist, 50, 7,9)
bs_helper(datalist, 50, 8,9)
Returns None

4. 
(a)
14 vs 39: [14] (given)
58 vs 39: [14, 39]
58 vs 40: [14, 39, 40]
58 vs 71: [14, 39, 40, 58]
86 vs 71: [14, 39, 40, 58, 71]
86 vs 85: [14, 39, 40, 58, 71, 85]
List b is completely used. Merge rest of a:
[14, 39, 40, 58, 71, 85, 86, 97]

(b) Perform the sort steps using merge sort! 

5. 

(a) len(numlist) == 0   OR   len(numlist) < 1   OR   numlist == []

(b) numlist[0] % 6 == 0

(c) 1 + count_multiples_of_6(numlist[1:len(numlist)])
    OR 
    1 + count_multiples_of_6(numlist[1:])

(d) count_multiples_of_6(numlist[1:len(numlist)])
    OR 
    count_multiples_of_6(numlist[1:])

6. It compresses the given folder and zips any subfolders inside. 
   The base case is when there are no subfolders in a folder.