CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 9 (Due Sunday March 24, at 5pm)

• In the assignment, several problems need to be solved without loops or iterative function calls. Each of these problems is labeled as Recursion-Only. For these problems, the autograder will automatically give a 0 to any solution that uses for loops, while loops, comprehensions, generators, or the following built-in functions: range, sum, max, min, reversed, sorted, list.count, list.sort, list.reverse, str.replace, and str.join.
• If a problem is not labeled as Recursion-Only, feel free to use loops as much as you like! However, every problem will need to use recursion in some way.
• When writing recursive code, watch out for destructive functions! Changing mutable values in a function can be useful, but can also make debugging tricky.


• Do you need new collaborator(s) for hw9? Fill out this form and we'll try to pair you up with other students in the class. We'll stop checking for new entries on Friday morning, so fill it out before then!


• To start:
  1. Create a folder named 'week9'
  2. Create a hw9.py file in that folder.
  3. When you have completed hw9, submit hw9.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.


• Do not hardcode the test cases in your solutions.

---

---

0. Style [0 pts]
   As usual, write your code with good style, and following the 15-112 style guidelines.

---

---

Collaborative problems

---

---

1. Recursion-Only alternatingSum(lst) [10pts]
   Write the function alternatingSum(lst) that takes a possibly-empty list of numbers, lst, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If lst is empty, return 0. You may not use loops/iterative functions in this problem.


2. Recursion-Only binarySearchValues(lst, item) [20pts]
   Recall the algorithm Binary Search which we discussed in class in week7. Write the function binarySearchValues(lst, item) that takes a sorted list lst and a value item and returns a list of tuples, (index, value), of the values that binary search must check to verify whether or not item is in lst. You may not use loops/iterative functions in this problem.
   
   For example, binarySearchValues(['a', 'c', 'f', 'g', 'm', 'q'], 'c') should return [(2, 'f'), (0, 'a'), (1, 'c')]. On the other hand, binarySearchValues(['a', 'c', 'f', 'g', 'm', 'q'], 'n') should return [(2, 'f'), (4, 'm'), (5, 'q')], since 'n' cannot be found.
   
   Hint: recall that in binary search, we keep track of a lo and hi indicies into the list, and use them to compute a mid index. Consider keeping track of these values instead of slicing lst.


3. findCategoryPath(d, value) [20pts]
   Assume that a 'path dictionary' is a dictionary that maps 'category' strings to 'value' strings, or to other path dictionaries. Write the function findCategoryPath(d, value) that takes a path dictionary, d, and attempts to find the given item as a value in one of the path dictionaries. If the item is found, the function returns a list of the categories (keys) that lead to the item; if it is not found, the function returns None.
   
   For example, consider the following path dictionary, which has dog breeds as categories and dog names as values:
   
   
   d = { "Sporting" : { "Spaniel" : { "English Springer" : "Betsy" }, "Weimaraner" : "Xeva", "Retriever" : { "Golden" : "Sammo", "Labrador" : "Nya" } }, "Working" : { "Husky" : "Stella", "Saint Bernard" : "Rutherfurd", "Boxer" : "Paximus" }, "Herding" : { "Corgi" : { "Welsh" : { "Cardigan" : "Geb", "Pembroke" : "Niinja" } }, "Sheepdog" : { "Bergamasco" : "Samur", "Old English" : "Duggy", "Shetland" : "Walker" } }, "Other" : "Kimchee" }
   
   If we called findCategoryPath on this dictionary with the value "Samur", it would return ["Herding", "Sheepdog", "Bergamasco"]. If we called it on the value "Weimaraner" (which is a key but not a value), it would return None.

---

---

Solo problems

---

---

4. Recursion-Only powersOf3ToN(n) [15pts]
   Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n. As an example, powersOf3ToN(10.5) returns [1, 3, 9]. If no such powers of 3 exist, you should return the empty list. You may not use loops/iterative functions in this problem.
   
   Hint: in the recursive case, consider using a partial result to construct a full result.


5. loadBalance(lst) [15pts]
   Imagine that you're helping a friend move, and you and your friend need to pack a group of items that have different weights into two boxes, which you'll then carry up several flights of stairs. You'd like to pack the boxes so that there is the smallest possible difference between the total weights, so that neither of you has to deal with an especially-heavy box.
   
   Write the function loadBalance(lst) which takes a list of integers (the item weights) and returns a tuple of two lists (the items in the two boxes). The two lists must contain all the elements of lst between them, and the difference between the two lists must be as small as possible. For example, loadBalance([3, 6, 1, 7, 9, 8, 22, 3]) could return ([3, 6, 1, 7, 9, 3], [8, 22]), since the sum of the first list is 29, while the sum of the second list is 30 (in this case, it is impossible to construct two lists of equal load).
   
   Note: there may be multiple correct answers for a given input; in the example above, the function could have returned ([3, 6, 9, 8, 3], [1, 7, 22]) instead. As long as all the numbers are contained and the difference between the two lists is the minimal possible distance, any answer is acceptable.


6. generateValidParentheses(n) [20pts]
   Write the function generateValidParentheses(n) that takes a non-negative int n and returns a set of all balanced strings that can be created using n parentheses and no other characters. We say that parentheses are balanced if each right parenthesis closes (matches) an open (unmatched) left parenthesis, and no left parentheses are left unclosed (unmatched) at the end of the text. So, for example, "((()())())" is balanced, but "())", "())(", and "(()()" are not balanced. Note that all balanced strings must therefore have an even number of characters; generateValidParentheses should return the empty set on an odd number.
   
   Example: generateValidParentheses(4) would return { "(())", "()()" }, generateValidParentheses(6) would return { "((()))", "()(())", "(())()", "(()())", "()()()" }, and generateValidParentheses(0) would return the empty set.

---

---

Bonus problems

---

---

7. Bonus/Optional: Towers of Hanoi Animation [3pts]
   Using our animation framework, write an animation that shows a step-by-step walkthrough of how Towers of Hanoi works. To get full credit, each disc movement must be shown, and the user must be able to modify the number of discs at the start state. There must also be some kind of visualization of the recursive function calls.
   
   IMPORTANT: If you attempt this bonus problem, look back at how we separated autograded and manually graded problems in the earlier homeworks. All autograded code and graphics/animation code must be separated by a line with the comment # ignore_rest, with autograded code above and animation code below.