CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 7 (Due Sunday 3-Mar, at 5pm)

• Do you need new collaborator(s) for hw7? Fill out this form and we'll try to pair you up with other students in the class. We'll stop checking for new entries on Friday at 9am, so fill it out before then!


• To start:
  1. Create a folder named 'week7'
  2. Create a file hw7.py in that folder using Pyzo
  3. When you have completed hw7, submit hw7.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.


• Do not hardcode the test cases in your solutions.

---

---

0. Style [0 pts]
   As usual, write your code with good style, and following the 15-112 style guidelines.

---

---

Collaborative problems

---

---

1. containsPythagoreanTriple(lst) [15 pts]
   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.


2. getPairSum(lst, target) [15 pts]
   Write the function getPairSum(lst, target) that takes a list of numbers and a target value (also a number), 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.


3. instrumentedSelectionSort(lst) and instrumentedBubbleSort(lst) [10 pts]
   Write the functions instrumentedSelectionSort(a) and instrumentedBubbleSort(a). Each of these should start with the code from the course notes and modify it so that instead of returning None, it returns a tuple of three values: the number of comparisons, the number of swaps, and the time it takes in seconds to run the sort.


4. selectionSortVersusBubbleSort() [10 pts] [manually graded]
   Write the function selectionSortVersusBubbleSort() which takes no parameters and calls the instrumented functions you just wrote above, perhaps several times each, then uses the results to automatically generate a report with the following information:
   • Empirically confirm that both selectionSort and bubbleSort are quadratic (O(N**2)). You can do this by testing whether the time taken by the function grows at the expected rate as the size of the input grows.
   • Show which sort runs in less time
   • Show which sort uses fewer comparisons
   • Show which sort makes fewer swaps
   This function returns nothing -- all the information is printed to the console.

---

---

Solo problems

---

---

5. 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. 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).
   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(?) # 1B: 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(?) # 2B: 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(?) # 3B: 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(?) # 4B: def fast4(a, b): pass # 4D:


6. movieAwards(oscarResults) [10 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", "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: 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.


7. friendsOfFriends(d) [20 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 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. =(

---

---

Bonus problems

---

---

8. Bonus/Optional: Sorting animation [3 pts] [manually graded]
   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.
   
   IMPORTANT: If you attempt this bonus problem, look back at how we separated autograded and manually graded problems in the earlier homeworks. All autograded code and graphics/animation code must be separated by a line with the comment # ignore_rest, with autograded code above and animation code below.