Homework 6

Due Tuesday 10-March, at 11:59pm

To start

1. Create a folder named hw6
2. Create a new file hw6.py in that folder
3. Edit hw6.py and add the functions and some testcases as required

4. When you have completed and fully tested hw6, submit hw6.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

5. This homework is individual. You are expected to write your own code and submit work that reflects your own understanding. You may discuss concepts with other students in the course, and you may use permitted resources, but you must follow the collaboration policy:
   • Do not copy code from any source.
   • If you look at code that you did not write, you must follow the 5-Minute Rule.
   • You are responsible for protecting your own work so others cannot copy it. See the academic honesty policy for more details.
6. 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.
7. There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
8. 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…
9. Do not hardcode the test cases in your solutions.
10. Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

Limitations

Do not use try/except, classes, or 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 assignment, 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!

A Note About Testing

There is no skeleton file provided this week, meaning that we also are not providing testcases. You should write testcases for the autograded function. (You can find some nice ways to test in the write-up below, but you will need to translate those to actual testcases.)

Problems

1. 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.


2. 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.


3. 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.


4. 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.


5. Big-O Calculation [25 pts (Manually graded)]
   This problem has multiple steps. Read it carefully to make sure you complete it. Paste the following four functions into your hw6.py file. Then, for each function, do the following:
   1. Determine the Big-O efficiency of the function with respect to N, the length of the list or string passed in as an argument. Write that efficiency in a string that is the first line of the function. (See the example below.) Note that the equation for the efficiency should be a valid Python math expression. For example, if you intend an efficiency of \(O(N^2)\) then you would write O(N**2)
   2. For each function, write 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). Name each function fast1 (the faster version of slow1), fast2 (the faster version of slow2), etc.
   3. Determine the Big-O efficiency of the new, faster function with respect to N, the length of the list or string passed in as an argument. Write that efficiency in a string that is the first line of the function.
   
   Consider the following example. Imagine that you are given the function slow0:
   def slow0(lst, idx): i = 0 for item in lst: if i == idx: return item i += 1 return None
   
   You would put the following inside of your submission:
   def slow0(lst, idx): "O(N)" i = 0 for item in lst: if i == idx: return item i += 1 return None def fast0(lst, idx): "O(1)" if idx < 0 or idx >= len(lst): return None return lst[idx]
   Here are the four functions for you to analyze in this assignment:
   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(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 def slow3(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 slow4(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


6. (BONUS) friendsOfFriends(d) [15 pts]
   Complete the problem friendsOfFriends(d) from CS Academy. You must solve the problem directly on the website, doing all of your testing there. Do not write the solution in Thonny (or a different IDE) and copy/paste it into the website.