Homework 8
Due Tuesday 15Mar, at 10:00pm
To start
 Create a folder named ‘hw8’
 Create a new file
hw8.py
in that folder
 Edit hw8.py and add the functions and some testcases as required
 When you have completed and fully tested hw8, submit hw8.py to Gradescope.
For this hw, you may submit up to 15 times, but only your last submission counts.
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.
Some important notes
 This homework is solo. You may not collaborate or discuss it with anyone outside of the course,
and your options for discussing with other students currently taking the course are limited.
See the academic honesty policy for more details.
 After you submit to Gradescope, make sure you check your score. If you aren’t sure
how to do this, then ask a CA or Professor.
 There is no partial credit on Gradescope testcases for autograded problems. Your Gradescope score is your Gradescope
score.
 Read the last bullet point again. Seriously, we won’t go back later and increase
your Gradescope score for any reason. Even if you worked really hard and it was only a
minor error…
 Do not hardcode the test cases in your solutions.
 We are not giving you any starter code this week. That means you need to
create your file from scratch and include your own testcases. For writing
testcases, follow the style of testcases uses in the previous homeworks.
 Remember the course’s academic integrity policy. Solving the homework yourself is
your best preparation for exams and quizzes; cheating or shortcutting your learning
process in order to improve your homework score will actually hurt your course grade
longterm.
Limitations
Do not use recursion this week.
The autograder (or a manual CA review later) will reject your submission entirely if you do.
A Note About Style Grading
Like in the previous assignments, we will be grading your code based on whether
it follows the 15112 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!
A Note About Testing
You will notice that the skeleton file only includes testcases for some of the functions you are writing. You should write testcases for the others. (You can find some nice ways to test in the writeup below, but you will need to translate those to actual testcases.)
Problems

movieAwards(oscarResults) [15 pts]
Write the function movieAwards(oscarResults)
that takes a set of tuples, where each tuple holds the name of a category and the name of the winning movie, then returns a dictionary mapping each movie to the number of the awards that it won. For example, if we provide the set:
{
("Best Picture", "The Shape of Water"),
("Best Actor", "Darkest Hour"),
("Best Actress", "Three Billboards Outside Ebbing, Missouri"),
("Best Director", "The Shape of Water"),
("Best Supporting Actor", "Three Billboards Outside Ebbing, Missouri"),
("Best Supporting Actress", "I, Tonya"),
("Best Original Score", "The Shape of Water")
}
the program should return:
{
"Darkest Hour" : 1,
"Three Billboards Outside Ebbing, Missouri" : 2,
"The Shape of Water" : 3,
"I, Tonya" : 1
}
Note: Remember that sets and dictionaries are unordered! For the example above, the returned set may be in a different order than what we have shown, and that is ok.

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 friendoffriend of Pod. This set should exclude any direct friends, so Jaime
does not count as a friendoffriend 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 friendsoffriends 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 oneway.

largestSumOfPairs(a) [20 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) [20 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.

BigO Calculation (Manually graded) [30 pts]
In a triplequoted 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 BigO time or number of loops for each line of the program, then state the resulting BigO of the whole program.
 Provide an equivalent Python function that is more than a constantfactor faster (so its worstcase BigO runtime is in a different function family). The better your solution's BigO runtime, the more points you get!
 Write the BigO time or number of loops for each line of the new program, then state the resulting BigO 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