CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Homework 7 (Due Saturday 15-Oct, at 8pm)

• This hw is SOLO. See the syllabus for details.
• Starter file: cs112_f16_wk7.py
• This week you may use up to 6 submissions. Only your last submission counts. Some of the problems are autograded, others are manually graded.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.
• As usual, there is no Late Day this week.

0. Friday optional OH [0 pts]
   Same as last week. Attendance is optional, and you can stop by for any or all recitations, which run from 10:30am to 5:30pm all day!


1. TA meetings [10 pts] [manually graded]
   By the hw7 deadline, you need to meet with one of your recitation TA's for 10-15 minutes for two purposes: (1) to discuss your term project ideas; and (2) to get in-person grading of your style on hw6. If you have this meeting before hw6 is due, then your TA may use your lab6 for the style grading. To get the most out of these short meetings, please show up with some really good ideas for your term projects. You also have nothing to submit for this part of the hw -- your TA will record attendance and enter grades accordingly. Note that to receive credit, you must be on time and stay the whole time, and show at least some evidence of some sincere thought to your term project.


2. 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.


3. 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.


4. mergeSortWithOneAuxList(a) [20 pts] [manually graded]
   Write the function mergeSortWithOneAuxList(a) that works just like mergeSort from the notes, only here you can only create a single aux list just one time, rather than once for each call to merge. To do this, you will need to create the aux list in the outer function (mergeSortWithOneAuxList) and then pass it as a parameter into the merge function. The rest is left to you. In a comment at the top of this function, include some timing measurements comparing this function to the original mergeSort, and a brief reflection on whether or not this change was worthwhile.


5. 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.


6. Bonus/Optional: huffmanCodingVisualization [up to 2.5 pts] [manually graded]
   As we discussed in this week's optional lecture, Huffman coding is one way to compress a block of text. It takes advantage of the fact that different letters have different frequencies, and we can use shorter codes for more-frequent letters and longer codes for less-frequent letters. Marvelous! In any case, your task here is to write the function huffmanCodingVisualization() that takes no parameters and creates a simple animation using our animation framework that visualizes how Huffman coding works. The design is entirely up to you. Have fun!


7. Bonus/Optional: keplerPolygons [up to 2.5 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 for the first polygon, 0.5 point for each of the next 2):
   
   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!!!