CMU 15-112 Summer 2019: Fundamentals of Programming and Computer Science
Homework 5-1 (Due Wed 30-Jul, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. There is no starter file for this assignment! You should create a file, hw5-1.py, to start.
  2. Edit hw5-1.py using Pyzo
  3. When you are ready, submit hw5-1.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
• Do not hardcode to the test cases in your solutions.
• Remember to write your own test cases, and in general, follow the style guide!

1. Big-O Calculation [40pts] [manually graded]
   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:
   
   
   1. State in just a few words what it does in general.
   2. 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.
   3. 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).
   4. 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 def slow4(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


2. largestSumOfPairs(a) [20 pts] [autograded]
   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.


3. friendsOfFriends(d) [40 pts] [autogrded]
   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. =(