Homework 04

Due: Friday, 10/28 at 11:59 pm

Download this assignment in pdf format or .tex source.

Exercise 1 (adapted from a technical interview question). Imagine you are working on a long-term building project that lasts \(N\) consecutive days. Each day, the project must be staffed by a contractor. You receive a large number of bids from contractors to staff the project, where each bid consists of:

  • a start date \(s\) satisfying \(1 \leq s \leq N\) when the contractor is available to start working,

  • a termination date \(t\) satisfying \(s \leq t \leq N\) which is the last date the contractor is available to work, and

  • a cost \(w\) for the contractor to work all days in the range \([s, t]\)

That is, a contractor’s bid consists of an interval \([s, t]\) and the associated cost \(w\) to hire the contractor for that interval. If a contractor is hired at all, they must work for the entire bid interval \([s, t]\). Your goal is to choose a set of contractors to hire according to the following criteria:

  1. Every day \(i = 1, 2, \ldots, N\) must be staffed by some contractor.
  2. No day can be staffed by more than one contractor.
  3. You wish to minimize the total cost to hire the contractors subject to satisfying constraints 1 and 2.

For example, suppose \(N = 10\) and you receive the following bids:

  1. cover days \([1, 2]\) for a cost of \(240\)
  2. cover days \([9, 10]\) for a cost of \(320\)
  3. cover days \([3, 8]\) for a cost of \(600\)
  4. cover days \([3, 5]\) for a cost \(300\)
  5. cover days \([6, 8]\) for a cost of \(280\)

Then there are two ways of satisfying the constraints above:

  • hire contractors \(1, 3, 2\) for a total cost of \(1160\), or
  • hire contractors \(1, 4, 5, 2\) for a total cost of \(1140\).

The second option is cheaper, so you should hire those contractors.

Given \(N\) and a set \(B\) of bids, define a (directed) graph \(G = (B, E)\) with vertex set \(B\) as follows: given two bids \(u, v \in B\) there is an edge from \(u\) to \(v\) if \(u\)’s termination date is the day before \(v\)’s start date.

  1. Draw the graph \(G\) corresponding to the example above with \(5\) bids.
  2. Given a graph \(G\) constructed as above, how could you determine if there is any feasible assignment of contractors that satisfy constraints 1 and 2 above. (You do not need to devise an explicit algorithm. It is enough to describe what features of \(G\) determine whether or not a feasible assignment exists.)
  3. Suppose you receive \(n\) bids so that \(G\) has \(n\) vertices. Devise an algorithm that finds a minimum cost assignment of contractors, or reports that no feasible assignment exists. The running time of your algorithm should be at most \(n^3 \log n\). You may use any algorithm described so far in class as subroutines, so long as you accurately state its running time.

Exercise 2. The bucolic town of Tashmer consists of one long highway dotted with farmhouses, a few storefronts, and civic buildings. A single water main stretches the length the highway, and provides water to the entire town. The county fire code requires that a fire hydrant be placed along the water main within 150 meters of every occupied building. Installing fire hydrants is expensive, so the town would like to minimize the number of hydrants installed. Devise an algorithm that determines the placement of fire hydrants that minimizes the total number of hydrants subject to the constraint that every occupied building is within 150 meters of a hydrant.

Specifically, your algorithm should take as input an array \(a\) of locations of occupied buildings. That is, \(a[i]\) is the distance (in meters) of the \(i\)th occupied building from the town line along the highway. Your algorithm should output a list of locations \(h_1 < h_2 < \cdots < h_k\) of fire hydrants such that for every building location \(a[i]\) there is a fire hydrant location \(h_j\) satisfying \(\vert a[i] - h_j\vert \leq 150\). In addition to a precise description of your procedure (i.e., through pseudocode), you should include an argument as to why your algorithm produces the minumum number of hydrants. Be sure to include the running time of your procedure as well.