Problem 3: Apply [20 points] A common approach to notifying people of what to do during an emergency situation (like an inclement weather event) is using a phone tree. It's simple - the tree has a root-a person who kicks off a series of phone calls - and when each person receives a call, they have additional designated individuals (their children in the tree) that they call. It sounds old-fashioned, but research has shown that people are more likely to take action in response to a call tree in comparison to an SMS or other passive notification 1. - We'll investigate the creation of a phone tree based on a social network. 'We assume that each participant has a set of "social connections" (i.e., people whose phone numbers they have handy). Given this, we need to create a tree with a simple rule: a participant x can be a child of another participant y in the tree only if y has s's number. Note that social connections are not necessarily. bidirectional, but for simplicity, we will assume that they are. We will formulate the creation of a call tree as a graph search problem. We are given a graph, where participants in the phone tree are nodes, and two nodes have an edge between them if the corresponding participants have each others' phone numbers. Cohsider first a fully connected network, i.e., everyone has everyone else's phone number. (a) Assume we use the tree that results from executing breadth first search as our phone tree. Describe this tree in the abstract. Assuming there are n participants, a single phone call takesy. minutes, and a person can only make one call at a time, how long does it take to notify all participants of the situation using this tree? (b) Now assume we use the tree that results from executing depth first search as our phone tree. Describe this tree in the abstract. Assuming there are n participants, a single phone call takes k minutes, and a person can only make one call at a time, how long does it take to notify all participants of the situation using this tree? Now consider a social network with the following social connections: (c) Draw the tree that results from running breadth first search on the graph that results from the social connections in the table above. If each call takes k minutes, and each participant can only make one call at a time, how long does it take to notify everyone? (d) Draw the tree that results from running a depth first search on the graph that results from the social connections in the table above. If each call takes k minutes, and each participant can only make one call at a time, how long does it take to notify everyone? (c) Which approsch is better? Use words that describe the structure of the phone tree to explain why this result is likely to generalize