15-112 Fall 2015 Homework 6
Due Sunday, 11-Oct, at 10pm

Read these instructions first!

This hw is SOLO. See the syllabus for details.
Starting this week, you may use sets and maps, but (as usual) you may not use constructs we have not yet covered (recursion, lambda functions, etc), unless explicitly allowed below.
This week you may only make up to 5 submissions max to Autolab. As usual, only your last one counts. Also, as usual, we will add 50% more submissions (3 this week) for late/grace days. We will not, however, provide any additional submissons, even with an additional deduction (that was a one-time deal last week, as there was no late/grace day last week).

s15 quiz1 and quiz2 [20 pts]
In a triple-quoted string at the top of your hw6.py file that you submit to autolab, include solutions to s15-quiz1 and s15-quiz2. To do this, you'll have to convert the code from Python2 to Python3, which mainly means to change / to // everywhere, and to change print x to print(x). Also, skip these parts:
- s15-quiz1-2K+L (we did not do boolean arithmetic)
- s15-quiz2-3b (we did not do nthEmirp)
- s15-quiz2-3d (we did not do play112)
- the bonus problems

Better Big Oh [20 pts]
In a triple-quoted string just below your quiz1 and quiz2 solutions, include solutions to this exercise. For each of the following functions:

State in just a few words what it does in general.
State and prove (in a few words) its worst-case big-oh runtime.
Provide an equivalent Python function that is more than a constant-factor faster (so it's worst-case big-oh runtime is in a different function family). The better your solution's big-oh runtime, the more points you get!
State and prove (in a few words) your better solution's worst-case big-oh runtime.

You should assume that lists all contain at least 5 values, and only integer values. Also, if a function takes two lists, you should assume they are the same length n.

import copy

def slow1(a):
    (b, c) = (copy.copy(a), 0)
    while (b != [ ]):
        b.pop()
        c += 1
    return c

def slow2(a):
    n = len(a)
    count = 0
    for i in range(n):
        for j in range(n):
            if (a[i] == a[j]):
                count += 1
    return (count == n)

def slow3(a, b):
    # assume a and b are the same length n
    n = len(a)
    assert(n == len(b))
    result = 0
    for c in b:
        if c not in a:
            result += 1
    return result 

def slow4(a, b):
    # assume a and b are the same length n
    n = len(a)
    assert(n == len(b))
    result = abs(a[0] - b[0])
    for c in a:
        for d in b:
            delta = abs(c - d)
            if (delta > result):
                result = delta
    return result

def slow5(a, b):
    # Hint: this is a tricky one!  Even though it looks syntactically
    # almost identical to the previous problem, in fact the solution
    # is very different and more complicated.
    # You'll want to sort one of the lists,
    # and then use binary search over that sorted list (for each value in
    # the other list).  In fact, you should use bisect.bisect for this
    # (you can read about this function in the online Python documentation).
    # The bisect function returns the index i at which you would insert the
    # value to keep the list sorted (with a couple edge cases to consider, such
    # as if the value is less than or greater than all the values in the list, 
    # or if the value actually occurs in the list).
    # The rest is left to you...
    #
    # assume a and b are the same length n
    n = len(a)
    assert(n == len(b))
    result = abs(a[0] - b[0])
    for c in a:
        for d in b:
            delta = abs(c - d)
            if (delta < result):
                result = delta
    return result

invertDictionary(d) [20 pts]
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.

sparseMatrixAdd(sm1, sm2) [20 pts]
Background: what we call a "matrix" in math can be represented by a 2d list of numbers in Python. To add two matrices, we add each corresponding element of the two matrices. So, for example, given the matrices m1 and m2, if their sum is m3, then m3[0][0] is simply m1[0][0] + m2[0][0]. Fine. A "sparse" matrix is a matrix that is mostly 0's, with just a few non-zero values. Instead of a 2d list, we will represent a sparse matrix using a dictionary, that maps (row, col) tuples to the value at that position. We will also store the dimensions explicitly in the keys "rows" and "cols". So, this matrix:
```
m = [ [ 0, 0, 0 ],
      [ 0, 5, 0 ]
    ]
```
can be represented as this sparse matrix:
```
sm = { "rows":2, "cols":3, (1,1):5 }
```
With this in mind, write the function sparseMatrixAdd(sm1, sm2) that takes two sparse matrices as just defined and returns the sparse matrix that results from adding them. If the input matrices are not the same size, use the larger size in each dimension for your result. For example:
```
assert(sparseMatrixAdd({"rows":5, "cols":4, (1,1):2, (1,2):3},
                       {"rows":3, "cols":6, (1,1):5, (2,2):6}) ==
                       {"rows":5, "cols":6, (1,1):7, (1,2):3, (2,2):6})
```

friendsOfFriends(d) [20 pts]
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.

Bonus/Optional: 3-Way Mergesort [1.5 pts] [manually graded (not autograded)]
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 doing 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.

15-112 Fall 2015 Homework 6 Due Sunday, 11-Oct, at 10pm

15-112 Fall 2015 Homework 6
Due Sunday, 11-Oct, at 10pm