Problem 1. (10 points)

We are given a simple connected undirected graph G = (V, E). Every vertex v has a distinct positive integer pv  associated with it.  We define a monotone spanning tree as a spanning tree where every root to leaf path in the tree encounters a non- decreasing sequence of integers. We want to compute such a monotone spanning

tree T of graph G, if one exists (return null otherwise).

Example:

1                                  42                                  1                                  42

u v                       u v

w x                      w x

5                                   7                                  5                                   7

In the example above, the graph on the left is the input graph.  The numbers next to the vertices are their associated integers. The tree on the right, rooted at u, is one of the possible monotone spanning trees of the graph. It contains two root to leaf paths: u, v (1, 42) and u, w, x (1, 5, 7). Both of these paths visit non-decreasing integers and are thus monotone.

We are given two algorithms for this problem:

modifiedPrim works similar to Prim’s MST algorithm: we maintain a set S of vertices that are already part of our tree and in every iteration of the algorithm, we add the vertex (adjacent to a vertex in S) with smallest integer to our tree. Initially, our set S consists of only the vertex s that has the smallest integer associated with it. Of course, before adding a vertex to S, we need to check whether its integer is at least as large as that of its parent in the tree. If this isn’t the case, we report that the graph has no monotone spanning tree.

modifiedDFS runs DFS starting from the vertex with the smallest integer asso- ciated with it.  Every time it processes a vertex, it visits its neighbors that haven’t been visited yet and have an integer that’s at least as large as its own. If at the end we have visited all vertices of the graph, we return the tree, and null otherwise.

a) Argue whether modifiedPrim always returns the correct answer by either arguing its correctness (if you think it’s correct) or by providing a counterex- ample (if you think it’s incorrect).

b) Argue whether modifiedDFS always returns the correct answer by either ar- guing its correctness (if you think it’s correct) or by providing a counterexam- ple (if you think it’s incorrect).

Problem 2. (25 points)

You’ve been hired by Telstra to set up mobile phone towers along a straight road in a rural area. There are n customers. Each customer’s mobile device has a specific range in which it can send and receive signals to and from a tower. The goal is to ensure that each customer is within range of a tower while using as few towers as possible. More formally, each customer has an associated interval [ℓi, ri], where ℓi and ri are positive integers (li  ≤ ri). The interval of a customer specifies the range of their mobile device. Serving customer i requires us to place a tower at a location x satisfying ℓi  ≤ x ≤ ri . A solution is a set L of tower locations and is feasible if for each customer i, there exists a location x ∈ L satisfying ℓi  ≤ x ≤ ri . We’re interested in constructing the smallest set L that is feasible.

Example:

1

2

3

4

0      1      2      3      4      5      6      7      8      9     10

Suppose we have 4 customers with intervals [5, 8], [1, 7], [2, 4], [1, 9] (see the above figure). In this case, L = {2, 6} is an optimal solution. L = {3} isn’t a solution, as we customer 1 doesn’t have any tower in their range. L = {2, 3, 6} is a solution, but it isn’t the smallest one, as it contains three towers, while having two would have sufficed.

Your task is to design a greedy algorithm that returns the smallest set of tower locations that is feasible.  For full marks, your algorithm should run in O(n log n) time. Remember to:

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.

Problem 3. (25 points)

Alice and Bob want to split a log cake between the two of them. The log cake is n centimeters long and they want to make one slice with the left part going to Alice and the right part going to Bob. Both Alice and Bob have different values for dif- ferent parts of the cake. In particular, if the slice is made at the i-th centimeter of the cake, Alice receives a value A[i] for the first i centimeters of the cake and Bob receives a value B[i] for the remaining n − i centimeters of the cake. Alice and Bob receives strictly higher values for larger cuts of the cake: A[0] < A[1] < . . . < A[n] and B[0] > B[1] . . . > B[n]. Ideally, they would like to cut the cake fairly, at a loca- tion i such that A[i] = B[i], if it exists. Such a location is said to be envy-free.

Example:

When A = [1, 4, 6, 10] and B = [20, 10, 6, 4] then 2 is the envy-free location, since A[2] = B[2] = 6.

Your task is to design a divide and conquer algorithm that returns an envy-free location if it exists and otherwise, to report that no such location exists.  For full marks, your algorithm should run in O(log n) time. Remember to:

a) Describe your algorithm in plain English.

b) Prove the correctness of your algorithm.

c) Analyze the time complexity of your algorithm.