While you may submit to Gradescope as often as you like for this assignment,
some questions are not autograded, so you will be responsible for testing your code
and making sure it meets the problem requirements.
Do not use recursion this week.
The autograder (or a manual CA review later) will reject your submission entirely if you do.
Like in the previous assignments, we will be grading your code based on whether
it follows the 15-112 style guide. We
may deduct up to 10 points from your overall grade for style errors. We highly
recommend that you try to write clean code with good style all along, rather
than fixing your style issues at the end. Good style helps you code faster and
with fewer bugs. It is totally worth it. In any case, style grading already
started, so please use good style from now on!
-
invertDictionary(d) [15 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.
-
friendsOfFriends(d) [15 pts]
Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:
d = { }
d["jon"] = set(["arya", "tyrion"])
d["tyrion"] = set(["jon", "jaime", "pod"])
d["arya"] = set(["jon"])
d["jaime"] = set(["tyrion", "brienne"])
d["brienne"] = set(["jaime", "pod"])
d["pod"] = set(["tyrion", "brienne", "jaime"])
d["ramsay"] = set()
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 Tyrion is a friend of Pod, and Jon is a friend of Tyrion, Jon is a friend-of-friend of Pod. This set should exclude any direct friends, so Jaime does not count as a friend-of-friend of Pod (since he is simply a friend of Pod) despite also being a friend of Tyrion's.
Thus, in this example, friendsOfFriends should return:
{
'tyrion': {'arya', 'brienne'},
'pod': {'jon'},
'brienne': {'tyrion'},
'arya': {'tyrion'},
'jon': {'pod', 'jaime'},
'jaime': {'pod', 'jon'},
'ramsay': set()
}
Note 1: your function should not modify the initial provided dictionary!
Note 2: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.
Note 3: you may assume that a person will never be included in their own friend set. You should also not include people in their own friends-of-friends sets!
Note 4: you may not assume that if Person1 lists Person2 as a friend, Person2 will list Person1 as a friend! Sometimes friendships are only one-way.
Hint: How is this different or similar to the facebook friends problem?
-
groupAnagrams(S) [15 pts]
Given a list of strings S, group the anagrams together.
Two strings are anagrams if each can be reordered into the other. Treat "a" and
"A" as the same letters (so "Aba" and "BAA" are anagrams).
The function should return a list of groups, in any order. Each group is a set
of strings where all the strings are anagrams of each other.
Some examples:
S = ["eat","tea","tan","ate","nat","bat"]
groupAnagrams(S) will group the strings in the following way:
[{"bat"},{"nat","tan"},{"ate","eat","tea"}]
S = ["own", "read", "dare", "eat", "now", "stop", "now", "spot", "15112", "tea"]
groupAnagrams(S) will group the strings in the following way:
[{"own", "now"}, {"read","dare"}, {"eat","tea"}, {"stop", "spot"}, {"15112"}]
The order of the groups in the returned list is not important. The size
of S will be large, therefore you should avoid using lists
operations as much as possible, otherwise your solution will be too slow and
will timeout. We expect that your code processes an input of 30K words in less
than a minute.
-
largestSumOfPairs(a) [15 pts]
Write the function largestSumOfPairs(a) that takes a list of integers, and returns the largest sum of any two elements in that list, or None if the list is of size 1 or smaller. So, largestSumOfPairs([8,4,2,8]) returns the largest of (8+4), (8+2), (8+8), (4+2), (4+8), and (2+8), or 16.
The naive solution is to try every possible pair of numbers in the list. This runs in O(n**2) time and is much too slow. Your solution should be more efficient.
-
containsPythagoreanTriple(a) [15 pts]
Write the function containsPythagoreanTriple(a) that takes a list of positive integers and returns True if there are 3 values (a,b,c) anywhere in the list such that (a,b,c) form a Pythagorean Triple (where a**2 + b**2 == c**2). So [1,3,6,2,5,1,4] returns True because of (3,4,5).
A naive solution would be to check every possible triple (a,b,c) in the list. That runs in O(n**3). You'll have to do better than that.
-
Big-O Calculation (Manually graded) [25 pts]
In a triple-quoted string at the top of your file (just below your name), include solutions to this exercise. For each of the following functions:
- State in just a few words what it does in general.
- Write the Big-O time or number of loops for each line of the program, then state the resulting Big-O of the whole program.
- Provide an equivalent Python function that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family). The better your solution's Big-O runtime, the more points you get!
- Write the Big-O time or number of loops for each line of the new program, then state the resulting Big-O of the whole program.
def slow1(lst): # N is the length of the list lst
assert(len(lst) >= 2)
a = lst.pop()
b = lst.pop(0)
lst.insert(0, a)
lst.append(b)
def slow2(lst): # N is the length of the list lst
counter = 0
for i in range(len(lst)):
if lst[i] not in lst[:i]:
counter += 1
return counter
import string
def slow3(s): # N is the length of the string s
maxLetter = ""
maxCount = 0
for c in s:
for letter in string.ascii_lowercase:
if c == letter:
if s.count(c) > maxCount or \
s.count(c) == maxCount and c < maxLetter:
maxCount = s.count(c)
maxLetter = c
return maxLetter
def slow4(a, b): # a and b are lists with 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