CMU 15-112 Summer 2020: Fundamentals of Programming and Computer Science
Homework 11 (Due Fri 12-Jun, at 5:00pm)

  1. powersOf3ToN(n int) []int [30pts]
    Write the function powersOf3ToN(n int) []int that takes a possibly-negative int n, and returns a list of the positive powers of 3 up to and including n, or the empty list if no such values exist. As an example, powersOf3ToN(10) returns []int{1, 3, 9}. You must use recursion for this problem, following the same rules as collab11.

  2. friendsOfFriends(friends map[string]cs112.StringSet) (map[string]cs112.StringSet) [30pts]
    Background: we can create a map mapping people to sets of their friends. For example, we might say:
    mkSet := cs112.StringSetFromSlice friends1 := map[string]cs112.StringSet{ "jon": mkSet([]string{"tyrion","arya"}), "tyrion": mkSet([]string{"pod","jaime","jon"}), "arya": mkSet([]string{"jon"}), "jaime": mkSet([]string{"brienne","tyrion"}), "brienne": mkSet([]string{"jaime","pod"}), "pod": mkSet([]string{"brienne","tyrion","jaime"}), "ramsay": mkSet([]string{}), }

    With this in mind, write the function friendsOfFriends that takes such a map 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:
    mkSet := cs112.StringSetFromSlice map[string]cs112.StringSet{ "tyrion": mkSet([]string{"brienne","arya"}), "pod": mkSet([]string{"jon"}), "brienne": mkSet([]string{"tyrion"}), "arya": mkSet([]string{"tyrion"}), "jon": mkSet([]string{"jaime","pod"}), "jaime": mkSet([]string{"jon","pod"}), "ramsay": mkSet([]string{}), }

    Note 0: you may use iteration for this problem

    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. =(