Homework5_Solutions

Homework Assignment #5: October 6, 2023 (11:59pm) 3 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 x ’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. Consider 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 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 ? Solution This tree has a root node, which has n-1 leaf children. In this tree, it takes O ( k ( n − 1)) = O ( kn ) time to notify everyone. (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 ? Solution This tree is just a linear graph. Again, it takes O ( kn ) time to notify everyone. 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? Solution insert tree 1 https://pubmed.ncbi.nlm.nih.gov/30379128/

Homework Assignment #5: October 6, 2023 (11:59pm) 6 Problem 6: Create [20 points] The SXSW festival is coming up. The City of Austin is finalizing its plans. One problem they noticed last year was that the placement of trash and recycle bins along 6 th street was not optimal last year. This year they want to more strategically place bins to keep trash off the street by making sure trash bins are placed along the sidewalk on each side of the street in such a way that they are within 20ft of the entrance to any establishment that serves take-away food. (a) Give an efficient greedy algorithm that finds a set of locations along one side of 6 th street for placing bins that achieves the city’s goal while minimizing the number of bins they have to place. State and briefly justify the runtime of your algorithm. (Hint: this is a one-dimensional problem, consider the sidewalk as a line and determine the locations along that line to place bins.) Start at one end of the road and begin moving along the sidewalk until the first eating establishment. Go another 20ft then place a bin. “Delete” all of the eating establishments within 20ft of this bin, then iterate on the remaining eating establishments. The running time of this algorithm: sorting the input by location O ( n log n ), and then going through the input 1 time O ( n ); thus O ( n log n ). If you assume the input is already sorted along the sidewalk since that’s how location works, O(n) is the runtime. (b) Prove that the greedy choice that your algorithm makes is the optimal choice. Let C = { c 1 , . . . , c k } denote the full set of bin locations that our greedy algorithm places, and let T = { t 1 , . . . , t m } denote the set of bin locations in an optimal solution, sorted in increasing order along the street. We must show that k = m . We do this by showing a sense in which our greedy solution C “stays ahead” of the optimal solution T . Specifically, we claim that c i ≥ t i for each i , and prove this by induction. The claim is true for i = 1 since we go as far as possible along the street before placing the first bin. Assume now that it is true for some value i ≥ 1; this means that our algorithm’s first i trash bins { c 1 , . . . , c i } cover all of the eating establishments covered by the first i trash bins { t 1 , . . . , t i } in the greedy solution. As a result, if we add t i +1 to { c 1 , . . . , c i } , we will not leave any eating establishment between c i and t i +1 uncovered. But the ( i + 1) st step of the greedy algorithm chooses c i +1 to be as large as possible subject to the condition of covering all eating establishments between c i and c i +1 , so we have c i +1 ≥ t i +1 . This proves the claim by induction. Finally if k > m , then { c 1 , . . . , c m } fails to cover all eating establishments. But s m ≥ t m , and so { t 1 , . . . , t m } also fails to cover all eating establishments—a contradiction to it being the optimal solution.