Given the list [5, 2, 7, 3], what will the list be after exactly 2 swaps are made in selectionSort, as demonstrated in lecture (where we selected the minimum value on each pass through the list)?

State and explain the Big-O of selectionSort with no more than two short sentences. You may make claims like "we need X comparisons on the first pass" without justification.

Put the following function families in order, from the slowest runtime to the fastest:

O(logn), O(2**n), O(n), O(n**0.5), O(n**3)

Indicate what the following code prints. Place your answers (and nothing else) in the box below. Note that you may not run this code.

def ct1(L):
    s = set()
    d = dict()
    for v in L:
        s.add(v)
        if (v in d):
            d[v] += len(s)
        else:
            d[v] = v
    print(f's = {s}')
    print(f'd = {d}')

ct1([1,2,1,1,5,2])

Write the function hasSquarePair(L) that takes a list of positive integers and returns True if the list contains an integer whose square is also in the list, and False otherwise. So [4,3,6,12,9] returns True because 3**2 is 9, which is also present in the list. Likewise, the list [4,7,5,22,30] returns False because the list contains no integer whose squared value is also in the list.

Your function must have an efficiency of O(N) to receive full credit!

Recall that friendsOfFriends(d) takes a dictionary d like this, which indicates the friends of Fred and the friends of Wilma and the friends of Barney:

d = dict()
d["fred"] = {"wilma", "betty", "barney"}
d["wilma"] = {"fred", "betty", "dino"}
d["barney"] = {"fred", "betty"}

Write the function popularityScores(d) that takes a dictionary of that form and returns a new dictionary which indicates for each person how many people consider that person a friend. For example, given d above:

popularityScores(d) == {"wilma" : 1,
                        "betty" : 3,
                        "barney" : 1,
                        "fred" : 2,
                        "dino" : 1}

Note: You should not include anyone who is no one's friend. They forgive you.