//Input is (h1,d1), ... , (hn-1,dn-1)  
                                    // di is the distance of house hi from the first house

                                    dmax= max(d1, ... ,dn-1)

                                    d=0 //Assuming the first house is at mile 0
                                    while( d < dmax)
                                        Place a tower at mile d
                                        d += 100
                                        

Part (b)

We would like to point out two things:

1. The algorithm above for part (a) does not work for part (b). The basic idea is that the algorithm from part (a) can place a cell tower at a mile where there is no house but for part (b) the cell towers have to be at a house. See the sample input/output above for a concrete example.
2. Think how you could modify the algorithm for part (a) could be modified to handle the extra restriction that the cell towers have to placed next to a house.

   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.

   Note

   The proof idea for part (a) does not work for part (b): you are encouraged to use greedy stays ahead technique we have seen in class to prove correctness of a greedy algorithm.

Greedy Stays Ahead

We briefly (re)state the greedy stays ahead technique in a generic way (and illustrate it with the proof of the greedy algorithm for the interval scheduling problem that we saw in class).

Roughly speaking the greedy stays ahead technique has the following steps:

1. Sync up partial greedy and optimal solution Greedy algorithms almost always build up the final solution iteratively. In other words, at the end of iteration $\ell$, the algorithm has computed a `partial' solution $\texttt{Greedy}(\ell)$. The trick is to somehow `order' the optimal solution so that one can have a corresponding `partial' optimal solution $\texttt{Opt}(\ell)$ as well.
2. Define a 'progress' measure For each iteration $\ell$ (as defined above), we pick a 'progress' measure $P(\cdot)$ so that $P\left(\texttt{Greedy}(\ell)\right)$ and $P\left(\texttt{Opt}(\ell)\right)$ are well-defined. This is the step that is probably most vague but that is by necessity-- the definition of the progress measure has to be specific to the problem so it is hard to specify generically.
3. Argue 'Greedy Stays Ahead' (as per the progress measure) Now prove that for every iteration $\ell$, we have \[P\left(\texttt{Greedy}(\ell)\right) \ge P\left(\texttt{Opt}(\ell)\right).\]
4. Connect 'Greedy Stays Ahead' to showing the greedy algorithm is optimal. Finally, prove that with the specific interpretation of 'Greedy Stays Ahead' as above, at the end of the run of the greedy algorithm the final output is 'just as good' as the optimal solution. Note that the progress measure $P(\cdot)$ need not be the objective function that the greedy algorithm is trying to minimize (indeed this will not be true in most cases) so you will still have to argue another step to show that greedy stays ahead indeed implies that the greedy solution is no worse than the optimal one.

Next, we illustrate the above framework with the proof we saw in class that showed that the greedy algorithm for the interval scheduling problem was optimal:

1. Sync up partial greedy and optimal solution We did this by ordering the intervals in both the greedy and optimal solution in non-decreasing order of their finish time. Specifically, recall that we defined the greedy solution as \[S^*=\left\{i_1,\dots,i_k\right\}\] and an optimal solution as \[\mathcal O=\left\{j_1,\dots,j_m\right\},\] where $f(i_1)\le \cdots \le f_(i_k)$ and $f(j_1)\le \cdots f(j_m)$. With this understanding, the 'partial' solutions are defined as follows for every $1\le \ell\le k$: \[\texttt{Greedy}(\ell)=\left\{i_1,\dots,i_\ell\right\}\] and \[\texttt{Opt}(\ell)=\left\{j_1,\dots,j_\ell\right\}.\]
2. Define a 'progress' measure. We define the progress measure as the (negation of) finish time of the last element in the partial solution, i.e. \[P\left(\texttt{Greedy}(\ell)\right) = -f\left(i_\ell\right)\] and \[P\left(\texttt{Opt}(\ell)\right) = - f\left(j_\ell\right).\] Two comments:
   • If the "$-$" sign in the definition of $P(\cdot)$ is throwing you off-- it's for a syntactic reason (and it'll become clear in the next step why this makes sense).
   • Note that the progress measure above has nothing (directly) to do with the objective function of the problem (which is to maximize the number of intervals picked).
3. Argue 'Greedy Stays Ahead' (as per the progress measure). In class, we proved a lemma that stays that for every $1\le \ell\le k$, we have \[f\left(i_\ell\right)\le f\left(j_\ell\right).\] Note that this implies that for our progress measure (and this is why we had the negative sign when defining the progress measure), for every $1\le \ell\le k$, \[P\left(\texttt{Greedy}(\ell)\right) \ge P\left(\texttt{Opt}(\ell)\right),\] as desired.
4. Connect 'Greedy Stays Ahead' to showing the greedy algorithm is optimal. For this step, we have a separate proof that assumed that if the 'Greedy Stays Ahead' lemma is true then $\left|S^*\right|\ge \left|\mathcal{O}\right|$.

HW 4, Question 2

Part (a)

Here we have to argue that there is always an optimal solution with no idle time: i.e. there should be no gap between when a skater finishes their skate and when the next skater starts their skate.

Part (b)

In this part you have to come up with an efficient (i.e. polynomial time) algorithm to come up with an optimal schedule for the skaters that minimizes the completion time. We repeat the following note and hint from the problem statement:

Exchange Argument for Minimizing Max Lateness

Given the schedule below where the deadline of $j$ comes before the deadline of $i$ (the top schedule has an inversion):

Let us consider what happens when we go from top schedule to the bottom schedule. Obviously $j$ will finish earlier so it will not increase the max lateness, but what about $i$? Now $i$ is super late.

However, note that $i$’s lateness is $f(j) - d(i)$ where $f(j)$ is the finish time of $j$ in the top schedule. Now note that \[f(j) - d(i) < f(j) - d(j),\] so the swap does not increase maximum lateness.