CMU 15-112: Fundamentals of Programming and Computer Science
Homework 10 (Due Friday 29-Jul at 8pm EDT)

• Hw10 bonus will be submitted separately in Autolab, in hw10-bonus (in the etc category).
• There is no starter file for hw10-bonus.
• With that, have fun!!! >>( o u o )<<

• As usual, this homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
• To start, download all of these to a folder named hw10:
  • hw10.py
  • cs112_n22_week4_linter.py
• Edit hw10.py using VSCode
• When you have completed and fully tested hw10, submit your hw10 file to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
• Do not use recursion.
• Do not hardcode the test cases in your solutions.

1. getPairSum(L, target) [20 pts]
2. containsPythagoreanTriple(L) [20 pts]
3. movieAwards(oscarResults) [30 pts]
4. friendsOfFriends(d) [30 pts]
5. bonus: Sorting animation [3 pts]

1. getPairSum(L, target) [20 pts: 10 pts autograded for correctness, 10 pts manually graded for efficiency (only if also correct)]
   Write the function getPairSum(L, target) that takes a list of integers (possibly empty) 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:
   
   
   assert(getPairSum([1], 1) == None) assert(getPairSum([5, 2], 7) in [ (5, 2), (2, 5) ]) #Your function just needs to # return ONE of these tuples! assert(getPairSum([10, -1, 1, -8, 3, 1], 2) in [ (10, -8), (-8, 10), (-1, 3), (3, -1), (1, 1) ] assert(getPairSum([10, -1, 1, -8, 3, 1], 10) == None assert(getPairSum([1, 4, 3], 2) == None) # catches reusing values! 1+1...
   
   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.


2. containsPythagoreanTriple(L) [20 pts: 10 pts autograded for correctness, 10 pts manually graded for efficiency (only if also correct)]
   Write the function containsPythagoreanTriple(L) that takes a list of positive integers (possibly empty) 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.


3. movieAwards(oscarResults) [30 pts: 20 pts autograded for correctness, 10 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.


4. friendsOfFriends(d) [30 pts: 30 pts autograded for correctness, though we will manually deduct most of the points if your solution uses lists]
   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. We'll grade this problem primarily on correctness but will manually deduct most of the points if you use any lists.


5. Bonus/Optional: Sorting animation [3 pts] [manually graded]
   Note: this will be submitted separately from hw10, in hw10-bonus. As such, do not include this in your hw10.py submission!
   
   Write an animation function for your favorite sorting algorithm! You must use the animation framework, 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
   • You must use cmu_112_graphics, you may not use additional modules/libraries/etc. beyond those in the course notes.
   
   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.
   
   The number of bonus points you receive will depend on how extraordinary your animation is. A minimally impressive animation will get 1 point, especially creative and useful ones will get 2 points, and only the very best of the best will get 3. As usual, the points are minimal, so you should only do this for fun and learning.
   
   Reminder: If you attempt this bonus problem, do not include it in your hw10.py submission, and submit it separately to hw10-bonus.