CMU 15-112: Fundamentals of Programming and Computer Science
Homework 8 (Due Thursday 22-Oct at 11:59pm EDT)
- Create a folder named 'week8'
- Download all of these to that folder:
- Edit hw8.py
- When you have completed and fully tested hw8, submit hw8.py to Autolab. For this hw, you may submit up to 4 times, but only your last submission counts.
Also note:
- There is no spicy portion of this hw, so that everyone has plenty of time to enjoy mid-semester break.
- This hw is devoted to practice using sets and dictionaries. You should use them properly throughout the hw. If you use lists where you should use sets, then you may write a solution that "works" but still does not get points by the autograder, because it will not work fast enough. Use sets wherever you can on this hw (and in general).
Required Problems
- Midsemester Survey [10 pts] [manually graded]
This will be posted soon to piazza. We said you would get some points on hw8 for filling out the midsemester survey. Well, here are those points! - friendsOfFriends(friends) [90 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(friends) 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.