Greedy Lab

Learning objectives:

• identify a greedy choice for a given problem
• propose an exchange argument that proves the greedy approach is correct
• propose a small modification to the problem so that the greedy approach no longer works

Problem 1 - Where to Charge my Car?

You have a new a new electric car! To help recoup the cost, you have taken a job delivering n burritos. Being a new electric car owner, you know you need to plan which charging stations to stop at along your route and want to stop at the fewest stations.

Formally, you are given \(n\) points along a line \((p_1, p_2, \ldots, p_n)\). There are a set of charging stations, \(C_1, C_2, \ldots , C_k\) that are available directly adjacent to this line. Your electric car has an electrical capacity of R miles (capacity is really measured in watts, but that does not matter for this problem). Select a subset S of the charging stations \((S \in C)\) such that the number of elements in S is minimized. S is null when no solution is possible.. If no stops are required, S is the empty set.

1. Specify at least two greedy choices for this problem and specify why you believe one of them will work and while you think the other will not work.
   
   
   
   
   

2. Create an exchange argument to show that the problem is correct
   
   
   
   
   
   
   
   

3. Change the problem slightly so that you believe a greedy solution is not possible. Explain why you think it is not possible.
   
   
   
   
   
   
   
   
   
   

Problem 2 - Antenna Placement

You are now an engineer at a cell phone tower company. Your job is provide 100% coverage to existing customers for whom you know there locations. In fact, they all amazingly live on a line (in a single dimensional world). Your goal is to place the minimum number of towers to provide 100% coverage.

Formally, you are given a set of single dimensional points \(C=c_1, c_2, \ldots , c_n\) which specify the locations of the homes. All of the towers have the same broadcasting radius which is r. A house has full coverage if its distance to some tower is less than or equal to r. Compute the minimal set of towers \(T=t_1, t_2, \ldots , t_k\) such that \(\forall i \in C (\exists t \in T ~~dist(i,t) \le r)\).

1. Specify at least two greedy choices for this problem and which one you think will lead to the optimal answer.
   
   
   
   
   

2. Create an exchange argument to show that the problem is correct
   
   
   
   
   
   
   
   

3. Change the problem slightly so that you believe a greedy solution is not possible. Explain why you think it is not possible.