High Speed Internet

Greedy algorithm problem.

Here are some extra notes that can be used in a recitation

Material Developed by: Atri Rudra

Context of this assignment

This problem is part of a series of assignments in an UG algorithms course that are all related to access to high speed Internet.

Here are some slides from a talk that gives an overview of these assignments.

The Problem

We come back to the issue of many USA regions not having high speed internet. In this question, you will consider an algorithmic problem that you would need to solve to help out a (fictional) place get high speed Internet.

You are the algorithms whiz in the effort to bring high speed Internet to SomePlaceInUSA. After lots of rounds of discussions and public feedback, it was decided that the most cost-effective way to bring high speed internet to SomePlaceInUSA was to install high speed cell towers to connect all houses in SomePlaceInUSA to high speed internet. There are two things in your favor:

  1. It just so happens that all of the $n$ houses in SomePlaceInUSA are on the side of a straight road that runs through the town.
  2. The above implies that you only need cell towers that only need to broadcast their signal in a narrow range, which means one cell tower can provide high speed internet access to all houses within $100$ miles ahead (rather than the usual 45 mile range ) on the road from its location (we are assuming that these cell towers will be on the side of the road). These cell towers are unidirectional so they can provide connection to only houses that are ahead of it.
Due to various logistical reasons, the cell towers have to be on the side of the straight road and right next to a house.

None of your team-mates attended the class on greedy algorithms, so in this problem you will design an efficient algorithm for them, which your team can use to figure out which houses should have cell towers installed next to them so as to use the minimum number of cell towers.

With an eye on the future, the cell towers have to be placed so that there is continuous cell coverage on the road from the first and the last house on the road. I.e. it should never be the case that you are on the road (between the first and the last house) such that you are strictly more than $100$ miles ahead of the closest cell tower. You can assume that you have to put a cell tower at the first house on the road in SomePlaceInUSA.

Note

You should assume the following for your algorithm:

  • No two consecutive houses are more than $99$ miles apart. Note that this implies there always exists a feasible way to assign cell towers to houses. Further, note that houses can be much closer than $99$ miles to each other.
  • The input to your algorithm is a list of houses along with their distance (in miles) from the very first house. You cannot assume that this list is sorted in any way.

Here are the two two parts of the problem:

  • Part (a): Assume that we relax the condition that the cell towers have to be next to house: i.e. you can place a cell tower anywhere on the road (the $100$ mile coverage restriction on the cell towers still applies). Design an $O(n)$ time algorithm to solve this related problem.

  • Part (b): Design an $O(n\log{n})$ time algorithm to solve the original problem (i.e. where the cell towers have to be next to a house). Prove the correctness of your algorithm and analyze its running time.

Hint

Think of a greedy way to decide on which houses to pick for cell tower installation. It might help to forget about the scheduling algorithms we have seen in class and just think of a greedy algorithm from "scratch." Then try to analyze the algorithm using similar arguments to one we have seen in class.

Common Mistake

One common mistake is to present a correct greedy algorithm to solve this problem but then not proving that their algorithm is optimal, i.e. among all feasible assignments of cell towers to houses (i.e. all allocations that result in high speed internet in all houses in SomePlaceInUSA) the algorithms output should have the fewest number of cell towers in them.

Walkthrough video

Here is the walkthrough video (thanks to Iman Abdul-Rashed for the video):