- Midsemester Course Survey [10pts]
Take the midsemester course survey here!
We want your feedback on how the course is going, so we can keep trying to make it better.
Note: this survey will be anonymous. When you complete the survey, you'll get a link to a different form where you can enter your andrewID to receive the homework credit. We will not be able to map your survey response to your andrewID.
If you want to give additional feedback, you can also give specific TAs feedback using the Midsemester TA Survey. This is not required and not worth any points, but is highly appreciated.
- Big-O Calculation [15pts]
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
- instrumentedLinearSearch(lst, item) and instrumentedBinarySearch(lst, item) [20pts]
Write the functions instrumentedLinearSearch(lst, item) and instrumentedBinarySearch(lst, item). Each of these functions should work just like the functions we went over in class, except that instead of returning the index of an element, they should return a list of all the indicies that were checked. For example, instrumentedLinearSearch([2, 4, 6, 8, 10, 12], 8) would return [0, 1, 2, 3], since it has to check each element in order until it reaches 8. On the other hand, instrumentedBinarySearch([2, 4, 6, 8, 10, 12, 14], 12) would return [3, 5] since it starts at the middle, narrows the search down to the top half, then immediately finds 12.
Note 1: Binary Search should round down when choosing a mid-index over an even number of elements. Otherwise, you won't pass the test cases!
Note 2: Any list passed into instrumentedBinarySearch must be sorted, but lists passed into instrumentedLinearSearch don't need to be sorted.
- containsPythagoreanTriple(a) [20pts]
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!
- movieAwards(oscarResults) [15pts]
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 a set 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")
}
the program should return:
{
"Darkest Hour" : { "Best Actor" },
"Three Billboards Outside Ebbing, Missouri" : { "Best Actress" },
"The Shape of Water" : { "Best Director", "Best Picture" }
}
- friendsOfFriends(d) [20pts]
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. =(
- Bonus/Optional: threeWayMergesort [1pt]
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 done 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.