CMU 15-112 Spring 2017: Fundamentals of Programming and Computer Science
Homework 9 (Due Saturday 25-Mar, at 8pm)

This hw is SOLO. For this hw, do not even discuss any portion of it with anyone except TA's and faculty. Note that an earlier posting of this hw indicated that it was collaborative. Due to changes since then, this hw is not collaborative. It is solo. Please be sure to work alone on it.
Starter files: none this week.
This week you may use up to 5 submissions. Only your last submission counts.
Do not use recursion this week.
Do not hardcode the test cases in your solutions.
As usual, there are no late days this week (though you may use a grace day if you have one available).

f16-quiz7 [10 pts] [manually graded]
First, working solo, and working under quiz conditions (30 minutes, one sitting, no notes, no computer, etc) -- except that it is ok to type instead of handwrite answers -- complete all of f16-quiz7. Then, working as a group if you wish (and this is the only part of hw9 that is collaborative), review and correct your solutions. Include your corrected solutions in a triple-quoted string at the top of your hw9.py file. Do not worry about how you would show your work in that file, just provide your final answers.

invertDictionary(d) [35 pts] [autograded]
Write the function invertDictionary(d) that takes a dictionary d that maps keys to values and returns a dictionary of its inverse, that maps the original values back to their keys. One complication: there can be duplicate values in the original dictionary. That is, there can be keys k1 and k2 such that (d[k1] == v) and (d[k2] == v) for the same value v. For this reason, we will in fact map values back to the set of keys that originally mapped to them. So, for example:
```
assert(invertDictionary({1:2, 2:3, 3:4, 5:3}) == 
       {2:set([1]), 3:set([2,5]), 4:set([3])})
```
Also, you may assume that the values in the original dictionary are all immutable, so that they are legal keys in the resulting inverted dictionary.

friendsOfFriends(d) [35 pts] [autograded]
Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:
```
    d["fred"] = set(["wilma", "betty", "barney", "bam-bam"])
    d["wilma"] = set(["fred", "betty", "dino"])
```
With this in mind, write the function friendsOfFriends(d) that takes such a dictionary mapping people to sets of friends and returns a new dictionary mapping all the same people to sets of their friends of friends. For example, since wilma is a friend of fred, and dino is a friend of wilma, dino is a friend-of-friend of fred. This set should exclude any direct friends, so even though betty is also a friend of wilma, betty does not count as a friend-of-friend of fred (since she is simply a friend of fred). Thus, in this example, if fof = friendsOfFriends(d), then fof["fred"] is a set containing just "dino" and fof["wilma"] is a set containing both "barney" and "bam-bam". Also, do not include anyone either in their own set of friends or their own set of friends-of-friends.

Note: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary. Also, do not worry about friends-of-friends-of-friends.

getPairSum(a, target) in O(n) time, [20 pts] [manually graded]
Write the function getPairSum(a, target) that takes a list of numbers and a target value (also a number), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair, and otherwise returns an empty list. If there is more than one valid pair, you can return any of them. You should write two different versions, one that runs in O(n**2) and the other in O(n). For example:
```
getPairSum([1],1) == []
getPairSum([5,2],7) in [ [5,2], [2,5] ]
getPairSum([10,-1,1,-8,3,1], 2) in [ [10,-8], [-8,10] ] (can also return [-1,3] or [1,1])
getPairSum([10,-1,1,-8,3,1],10) == []
```
def getPairSum(a, target): return 42 # place your answer here! def testGetPairSum(): print("Testing getPairSum...", end="") assert(getPairSum([1],1) == []) assert(getPairSum([5, 2], 7) in [ [5, 2], [2, 5] ]) # (can return [10, -8] or [-1,3] or [1,1]) assert(getPairSum([10,-1,1,-8,3,1], 2) in [[10, -8], [-8, 10], [-1, 3], [3, -1], [1, 1]]) assert(getPairSum([10,-1,1,-8,3,1], 10) == []) assert(getPairSum([1, 4, 3], 2) == []) print("Passed!") testGetPairSum()

Bonus/Optional: threeWayMergesort [1 pt] [manually graded]
First, write the function threeWayMergesort(L) that takes a list L and does a modified version of mergesort on L, where instead of combining two sorted sublists at a time, you should combine three sorted sublists at a time (so after one pass, you have sublists of size 3, and after two passes, sublists of size 9, and so on). You may not assume that the size of the list is a power of 3.

Next, in a triple-quoted string just below your threeWayMergesort function, write a short proof that the function runs in O(nlogn) -- that is, in the same big-oh worst-case runtime as normal two-way mergesort. Then, write the function threeWayMergesortTiming() that empirically demonstrates that threeWayMergesort runs in the same big-oh as normal (two-way) mergesort (no more than a constant time faster or slower, even as n grows large). So all that extra work to write threeWayMergesort was for naught. Sigh. When you are done with this function, run it, get the timing data that proves your point, and include it with a very brief explanation at the end of that triple-quoted string just below threeWayMergesort.

Bonus/Optional: keplerPolygons [up to 3 pts] [manually graded]
Among his lesser-known exploits, the great German mathematician and astronomer Johannes Kepler studied how polygons can tile the plane or portions of the plane. Here you will write the function keplerPolygons() that takes no parameters and runs an animation that demonstrates one or more of these polygons (1 point each for up to 3 Kepler polygons):

For an additional half-point, bring at least one of these polygons to life so that they animate in an interesting way, such as rotating. And remember to use good style (no magic numbers!).
Enjoy!!!