CMU 15-112: Fundamentals of Programming and Computer Science
Homework 8 (Due Saturday 26-Oct at 8pm)

1. Because of mid-semester break, this hw's deadline is a week later than usual.
2. However, we strongly recommend that you complete it as early as possible, since quiz8 still covers all of week8's material and since hw9 is a full hw.
3. To promote this, all submissions through Monday night (11:59pm) will receive a +2.5-point early-bird bonus. Free points (woohoo)!
4. Also, since you may wish to work on the bonus after the early-bird deadline, all the bonus problems that would be on hw8 will instead be submitted as part of hw9.

• 15-112-f19 Extension Request Form
• Note: this week's booster sessions are on a special schedule. See the piazza post for details.

1. Create a folder named 'week8'
2. Download all of these to that folder:
   • hw8.py
   • cs112_f19_week8_linter.py
3. Edit hw8.py
4. Note: this file has less starter code than previous weeks. In particular, you have to add your own test functions. Be sure to do this, and then to add a call to each test function inside the testAll function, as usual.
5. When you have completed and fully tested hw8, submit hw8.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.

• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.
• Even though we have split writing-sessions into their own separate category, and even though there is no writing session this week, homeworks will continue to be out of 75 points instead of 100 points so that each hw is equally weighted.

1. Mid-Semester Survey [5 pts] [manually graded]
   So we can best serve you, and so you can get 5 points, please fill out this survey. We highly value your constructive feedback. Thanks!!!
   
   In addition, we ask that you please fill out the Mid-Semester TA Review form, once per TA you wish to review. Your thoughtful and constructive opinions are very important to us, and they help us continue to improve this course for you and for all future 112 students. Please take a look at the course staff photo roster to make sure you are reviewing the correct TA. Thanks!!!


2. Big-O Calculation [20 pts] [manually graded]
   In a triple-quoted string at the top of your file (just below your name), copy the text below and write in solutions to this exercise. For each of the following functions:
   
   
   1. State in just a few words what it does in general.
   2. Modify the comments on the side of the program to include the Big-O time or number of loops of each line, then state the resulting Big-O of the whole program.
   3. Outside of the triple-quoted string, so as runnable code, write an equivalent Python function (fast#) that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family).
      • Again, your fast functions must be top-level runnable code.
      • Also, for each fast function, write a test function that confirms that the fast function works the same as the slow function over a few well-chosen example inputs.
   4. Add comments with 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.
   
   
   # 1A: def slow1(lst): # N is the length of the list lst assert(len(lst) >= 2) a = lst.pop() # O(?) b = lst.pop(0) # O(?) lst.insert(0, a) # O(?) lst.append(b) # O(?) # 1C: def fast1(lst): pass # 1D: # 2A: def slow2(lst): # N is the length of the list lst counter = 0 # O(?) for i in range(len(lst)): # ? Loops if lst[i] not in lst[:i]: # O(?) counter += 1 # O(?) return counter # O(?) # 2C: def fast2(lst): pass # 2D: # 3A: import string def slow3(s): # N is the length of the string s maxLetter = "" # O(?) maxCount = 0 # O(?) for c in s: # ? Loops for letter in string.ascii_lowercase: # ? Loops if c == letter: # O(?) if s.count(c) > maxCount or \ s.count(c) == maxCount and \ c < maxLetter: # O(?) maxCount = s.count(c) # O(?) maxLetter = c # O(?) return maxLetter # O(?) # 3C: def fast3(s): pass # 3D: # 4A: def slow4(a, b): # a and b are lists with the same length N assert(len(a) == len(b)) result = abs(a[0] - b[0]) # O(?) for c in a: # ? Loops for d in b: # ? Loops delta = abs(c - d) # O(?) if (delta > result): # O(?) result = delta # O(?) return result # O(?) # 4C: def fast4(a, b): pass # 4D:


3. getPairSum(lst, target) [10 pts: 5 pts autograded for correctness, 5 pts manually graded for efficiency (only if also correct)]
   Write the function getPairSum(lst, target) that takes a list of integers and a target value (also an integer), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair as a tuple; otherwise, it returns None. If there is more than one valid pair, you can return any of them. For example:
   
   
   getPairSum([1], 1) == None getPairSum([5, 2], 7) in [ (5, 2), (2, 5) ] getPairSum([10, -1, 1, -8, 3, 1], 2) in [ (10, -8), (-8, 10), (-1, 3), (3, -1), (1, 1) ] getPairSum([10, -1, 1, -8, 3, 1], 10) == None
   
   A naive solution would be to check every possible pair in the list. That runs in O(N**2). To get full credit for the problem, your solution must run in no worse than O(N) time.


4. containsPythagoreanTriple(lst) [15 pts: 7.5 pts autograded for correctness, 7.5 pts manually graded for efficiency (only if also correct)]
   Write the function containsPythagoreanTriple(lst) 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): 3**2 + 4**2 == 5**2. [1, 3, 6, 2, 1, 4] returns False, because it contains no triple.
   
   A naive solution would be to check every possible triple (a, b, c) in the list. That runs in O(N**3). To get full credit for the problem, your solution must run in no worse than O(N**2) time.


5. movieAwards(oscarResults) [10 pts: 5 pts autograded for correctness, 5 pts manually graded for efficiency (only if also correct)]
   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", "Green Book"), 
       ("Best Actor", "Bohemian Rhapsody"),
       ("Best Actress", "The Favourite"),
       ("Film Editing", "Bohemian Rhapsody"),
       ("Best Original Score", "Black Panther"),
       ("Costume Design", "Black Panther"),
       ("Sound Editing", "Bohemian Rhapsody"),
       ("Best Director", "Roma")
     }
   

   the program should return:

     { 
       "Black Panther" : 2,
       "Bohemian Rhapsody" : 3,
       "The Favourite" : 1,
       "Green Book" : 1,
       "Roma" : 1
     }
   

   
   Note 1: Remember that sets are unordered! For the example above, the returned set may be in a different order than what we have shown, and that is ok.
   
   Note 2: Regarding efficiency, your solution needs to run faster than the naive solution using lists instead of some other appropriate, more-efficient data structures.


6. friendsOfFriends(d) [15 pts: 7.5 pts autograded for correctness, 7.5 pts manually graded for efficiency (only if also correct)]
   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 nondestructive 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. Additionally, a person cannot be a friend or a friend-of-friend of themself.
   
   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: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.
   
   Note 2: 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. =(
   
   Note 3: regarding efficiency, your solution needs to run faster than the naive solution using lists instead of some other appropriate, more-efficient data structures.


7. Bonus/Optional: Sorting animation [3 pts] [manually graded in hw9]
   Note: this is not part of hw8. It will be submitted with hw9. This allows you to submit hw8 by Monday night for the early-bird bonus and still continue to work on this bonus problem afterwards. As such, do not include this in your hw8.py submission!
   
   Write an animation function for your favorite sorting algorithm! You'll want to use the animation starter code, but you can be creative regarding how you visualize the sorting process. The only requirements are the following features:
   
   
   • Clearly indicate the name of the sorting algorithm being demonstrated
   • Demonstrate using a randomly-generated shuffled list of the numbers from 0 to 20
   • Clearly demonstrate each comparison, move, swap, etc.
   • Use the right arrow key to move the sort a step forward, and the left key to move a step back
   • Type the "r" key to reset the animation to a new shuffled list
   
   Feel free to look at the sorting links in the efficiency course notes for inspiration! There's lots of cool visualizations and sorting algorithms out there.
   
   Reminder: If you attempt this bonus problem, do not include it in your hw8.py submission. Instead, it belongs in your hw9.py submission!