Problem 1(a) (10 points)
-----------
(a) [4.4, 'Rocky', 4.9, 'Fargo', 3.5, 'Congo', 5.1, 'Argo', 3, 'Jaws', 5, 'Hamlet']
(b) [('Argo', 5.1), ('Hamlet', 5), ('Fargo', 4.9), ('Rocky', 4.4), ('Congo', 3.5), ('Jaws', 3)]
(c) {3.5: 'Congo', 3: 'Jaws', 4.4: 'Rocky', 4.9: 'Fargo', 5.1: 'Argo', 5: 'Hamlet'}
(d) [4.9, 3.5, 5.1]
(e) [(3.5, 'Congo'), (3, 'Jaws')]
 
Problem 1(b) (20 points)
------------
def evaluateExpression(expr, varList, valueList):
    L = [x.strip() for x in expr.split("+")]
    sum = 0
    for x in L:
        if x[0].isalpha():
            sum = sum + valueList[varList.index(x)]
        else:
            sum = sum + int(x)
    return sum

Problem 2(a) (10 points)
-----------
(a) {1: 8, 8: 17, 12: 1, 15: 2, 17: 1}
(b) {1: 17, 2: 17, 8: 17, 12: 1, 15: 2, 17: 1}
(c) {1: 17, 2: 1, 8: 17, 12: 1, 15: 2, 17: 1}
(d) {1: 8, 2: 17, 8: 17, 12: 1, 15: 15, 17: 1}
(e) {}

Problem 2(b) (15 points)
-----------
def twoHopNeighbors(w, D):
    twoHopsList = []
    for neighbor in D[w]:
        for twoNeighbor in D[neighbor]:
            if twoNeighbor not in D[w] and twoNeighbor not in twoHopsList:
                twoHopsList.append(twoNeighbor)

    return twoHopsList

Problem 2(c) (15 points)
-----------
def invert(D):
    newD = {0:[], 1:[], 2:[], 3:[], 4:[], 5:[], 6:[], 7:[], 8:[], 9:[], 10:[]}
    for k in D.keys():
        newD[D[k]/10].append(k)

    return newD

Problem 3(a) (15 points)
-----------
def generalSelection(L, k, first, last):
    p = partition(L, first, last)

    numSmaller = p-first

    if numSmaller+1 == k:
        return L[p]

    elif numSmaller+1 < k:
        return generalSelection(L, k-(numSmaller+1), p+1, last)

    elif numSmaller+1 > k:
        return generalSelection(L, k, first, p-1)

Problem 3(b) (10 points)
-----------
[9]
[]
[1, 9]
[]
[1, 4, 9]
[8]
[]
[2]

Problem 3(c) (15 points)
-----------
def maximum(L):
    if len(L) == 1:
        return L[0]

    m = maximum(L[1:])
    if L[0] >= m:
        return L[0]
    else:
        return m

Problem 4(a)  (10 points)
------------
    def remove(self, ssn):
        del self.D[ssn]

Problem 4(b) (15 points)
-----------
    def __repr__(self):
        L = []
        for key in self.D.keys():
            L.append([key, self.D[key]])

        L = sorted(L)

        s = ""
        for x in L:
            s = s + str(x[1][0]) + " " + str(x[0]) + " " + str(x[1][1]) + " " + str(x[1][2]) + "\n"

        return s.strip()

Problem 4(c) (15 points)
-----------
    def add(self, name, ssn, salary, start):
        i = 0
        while i < len(self.L):
            if self.L[i][1] > ssn:
                break
            i = i + 1

        if i >= len(self.L):
            self.L.append([name, ssn, salary, start])
        else:
            self.L.insert(i, [name, ssn, salary, start])