The first algorithm design paradigm that we'll look at is the greedy algorithm. Greedy algorithms are called such because they are greedy with respect to some simple rule or property. To see this, let's start with a simple example.
Suppose you're being asked to make change. How do you find the least number of coins to give back? There is an obvious way that we deal with this: just pick the largest coin until we can't and go to the next largest. Eventually, we'll end up with the right amount. This is an example of a greedy algorithm, because we're optimizing around the rule "choose the largest coin denomination". An interesting question is: does this always give us the optimal outcome?
We can formalize this a bit more. Given a positive integer $n$, we want to find $a,b,c,d$ such that $n = 25a + 10b + 5c + d$ with $a+b+c+d$ minimized.
To see that this is true for American coins, we can argue about what we'd need to replace the largest coins with:
To prove this formally, we just need to wrap this up in an inductive argument and essentially argue that if I don't take the largest coin at each step, I end up with more coins than necessary.
We can play around with this for other countries' coin denominations. For example, in Canada, we'd be given $n$ and we'd want to find $n = 200a + 100b + 25c + 10d + 5e$ while minimizing $a+b+c+d+e$. But does our greedy algorithm work for every set of coin denominations?
The answer turns out to be no! Here's one example: suppose we bamboozled someone important into adding a 6-cent coin. Then we have the following set of coins $\{1,5,6,10,25\}$. Now, suppose I need 18 cents in change. Following the greedy algorithm gets us one dime, one six cent coin, and two pennies. However, I can use three 6-cent coins instead.
There are some other interesting questions that you can come up with for this kind of problem. For a given set of coin denominations, what is the average number of coins that you can expect to get from a transaction? And as a followup to this question, is there a new coin that we can introduce to a set of coin denominations to make the expected number of coins we get lower?
Suppose we have resource to which we need to schedule some activities. For instance,
Some of the activities in the list are in conflict, in that their times overlap. We want to be able to schedule these activities to complete the most we can. If two activities don't overlap, we say that they are compatible.
The interval scheduling problem is: Given a list of $n$ jobs $j_1, j_2, \dots, j_n$, and each job $j_i$ has a start time $s(i)$ and a finish time $f(i)$, find the largest subset of mutually compatible jobs.
Consider the following list of jobs, arranged on a timeline.
We need to choose as large a compatible subset of these jobs as possible. We list a few possibilities below.
What are some possible greedy strategies we can use to schedule the largest number of compatible jobs?
It turns out (2) is the strategy that is guaranteed to give us the maximum number of jobs, and none of the other strategies do. A nice exercise is to come up with instances where strategies 1, 3, and 4 fail.
First, let $J = \{(s_i,f_i) \mid 1 \leq i \leq n\}$ be a list of start and finish time for jobs 1 through $n$. Then, we have the following algorithm.
\begin{algorithmic}
\PROCEDURE{Earliest}{J}
\STATE Sort jobs by finish times and renumber the jobs so that $f_1 \leq f_2 \leq \cdots \leq f_n$.
\STATE Initialize $S = \emptyset$ to be the set of selected jobs
\FOR{$j$ from 1 to $n$}
\IF{job $j$ is compatible with $S$}
\STATE add $j$ to $S$
\ENDIF
\ENDFOR
\RETURN{$S$}
\ENDPROCEDURE
\end{algorithmic}
First, we can do a quick efficiency proof, since the algorithm is quite simple (as most greedy algorithms are).
The earliest finish time first algorithm has running time $O(n \log n)$.
The first step of sorting our list of jobs takes $O(n \log n)$ time. Then we have a loop where we look at each job and check whether it is compatible with our selected jobs $S$. At first glance, this sounds like we might need to check our current job $j$ against every job in $S$, but because we only add jobs in order of finish time, all we need to do is check against the last job $j'$ that was added to $S$. That means, we only need to remember this job and perform one comparison with it, which takes $O(1)$ time and space. This means that our algorithm is dominated by the sorting step, giving it a running time of $O(n \log n)$.
Note that we take advantage of the fact that sorting a list can be performed in $O(n \log n)$ time. If you haven't seen this result yet, we will be seeing how to do this later in the course.
Now let's show that this algorithm actually works. That is, we want to show that this algorithm is guaranteed to give us the optimal solution, and we can schedule the largest number of jobs.
Let $S = \{j_1, \dots, j_k\}$ be the set of jobs that we get from our greedy algorithm and let $S^* = \{j_1^*, \dots, j_\ell^*\}$ be an optimal solution. We want to show that $S = S^*$. First, we'll make the following observation.
For all $i \leq k$, $f(j_i) \leq f(j_i^*)$.
We will prove this by induction. First, we have the base case, $i = 1$, which is obvious.
Now, for $i \gt 1$, we assume that $f(j_{i-1}) \leq f(j_{i-1}^*)$ and we want to show that $f(j_i) \leq f(j_i^*)$. Since $S^*$ is an optimal solution, we know that the jobs in $S^*$ are all compatible. Thus, we have $f(j_{i-1}^*) \leq s(j_i^*)$. Then by the inductive hypothesis, we have $f(j_{i-1}) \leq s(j_i^*)$.
This means that $j_i^*$ is a job that's compatible with jobs $j_1, \dots, j_{i-1}$ and could have been chosen by the greedy algorithm. Since the greedy algorithm chooses the job with the earliest finish time, we have $f(j_i) \leq f(j_i^*)$.
This will come in handy to show that $S$ is optimal.
The earliest finish time first algorithm is optimal.
We will prove this by contradiction. Suppose the greedy strategy is not optimal and so $|S^*| = \ell \gt k = |S|$.
By Lemma 3.5, we have $f(j_k) \leq f(j_k^*)$. Now, consider $j_{k+1}^*$, which must exist, since there are more jobs in $S^*$ than $S$. Since the jobs in $S^*$ must be compatible, we have $s(j_{k+1}^*) \geq f(j_k^*) \geq f(j_k)$.
But this means that $j_{k+1}^*$ is a job that is available and compatible with $S$, so it should have been chosen by the greedy algorithm. This contradicts the fact that $S$ is the set of jobs obtained via our greedy algorithm.
This proof gives us one way to show that greedy algorithms are optimal, which is that "greedy stays ahead". We've essentially showed that for each step of the greedy algorithm, when we could've chosen a different job, we always end up getting the best result if we take the greedy option. In this case, the key result was Lemma 3.5.
Because scheduling is such a general problem, we can come up with many different variants of the problem. Let's consider the following variant.
Suppose that instead of being given a start and finish time for jobs, we're simply given how long each job takes and a due date that we're trying to aim for. This would be like if you have four assignments due this week and you're really good at predicting how much time you'd need. Unfortunately, it may not be possible to meet all the due dates, but we should try our best to do so. What we would like is to schedule our jobs to minimize how late we are across all jobs.
The scheduling to minimize lateness problem is: Given a list of $n$ jobs $j_1, j_2, \dots, j_n$, where,
schedule all jobs to minimize maximum lateness $L = \max_{1 \leq i \leq n} \ell(i)$.
Below, we have a list of jobs together with their deadlines and a possible arrangement of these jobs.
The lateness of jobs (which are late) are denoted in yellow. We take the largest of these to be the maximum lateness $L$ as defined in the problem.
Again, we have a number of metrics to choose from to attempt a greedy strategy.
The correct choice is strategy (2). Let $J = \{(t_n,d_n) \mid 1 \leq i \leq n\}$ be our list of jobs' processing times and deadlines. We have the following algorithm.
\begin{algorithmic}
\PROCEDURE{Earliest}{J}
\STATE Sort jobs by deadlines and renumber jobs so that $d_1 \leq d_2 \leq \cdots \leq d_n$.
\STATE $t = 0$
\FOR{$j$ from 1 to $n$}
\STATE $s_j = t$
\STATE $f_j = t+t_j$
\STATE $t = t+t_j$
\ENDFOR
\RETURN{$\{(s_i,f_i) \mid 1 \leq i \leq n\}$}
\ENDPROCEDURE
\end{algorithmic}
This algorithm is due to Jackson in 1955, which makes it one of the earliest examples of a greedy algorithm for an optimization problem. Now, you might be wondering what the heck they were trying to schedule back in 1955, and the answer is factory production lines.
Much like the earliest finish time algorithm, we can get a pretty simple running time analysis for the earliest deadline algorithm.
The earliest deadline first algorithm has running time $O(n \log n)$.
Our first step is sorting the deadlines, which takes $O(n \log n)$ time. Then we have a for loop which goes through each job and computes the start and finish times. These operations take $O(1)$ time, so the loop has running time $O(n)$ in total. So the algorithm is dominated by the sorting step, giving it $O(n \log n)$ running time.
One of the things we might notice about this algorithm is that there's no downtime between jobs. In fact, it's not too hard to convince yourself that you can take any optimal schedule that minimizes lateness and just get rid of any idle time in it and you would still have a schedule that minimizes lateness.
What this means is that we can just take every schedule and jam all the jobs together and to get a different schedule, we just start swapping jobs.
Consider our earliest-deadline schedule that is created by our algorithm. The jobs have been renumbered so that they are listed in order from 1 through $n$.
Given a schedule $S$, an inversion is a pair of jobs $i,j$ such that
The idea of an inversion is more general than just schedules; we can apply it to permutations of lists. If we have a list $1, \dots, n$, then an inversion in a permutation $\pi$ is a pair $i,j$ with $i \lt j$ and $j$ appearing before $i$ in the permutation.
Here, we would like to consider inversions in schedules with respect to our earliest deadline schedule, which is the only idle-free schedule that contains no inversions.
Suppose an idle-free schedule has an inversion. Then it contains two adjacent inverted jobs.
Let $(i,j)$ be an inversion that is closest together and let $k$ be the element to the right of $j$. If $j \gt k$, then $(j,k)$ is an inversion that is closer. If $j \lt k$, then $(i,k)$ is an inversion that is closer together, since $i \lt j \lt k$.
Exchanging two adjacent inverted jobs $i$ and $j$ reduces the number of inversions by 1 and does not increase maximum lateness.
We denote $\ell(i)$ to be the lateness for job $i$ in the schedule with the inversion and $\ell'(i)$ the lateness in the schedule after swapping the inversion.
For every job $k \neq i,j$, the lateness stays the same and for job $i$, we have $\ell'(i) \leq \ell(i)$, since $i$ gets moved to before $j$.
Now, consider job $j$. If $j$ is late, then \begin{align} \ell'(j) &= f'(j) - d(j) \\ &= f(i) - d(j) \\ &\leq f(i) - d(i) \\ &\leq \ell(i) \end{align} In other words, once swapped, $j$ is no later than $i$ was before the swap. To get this calculation, we observe that once we swap $i$ and $j$, the finish time for $j$ after the swap, $f'(j)$, is the old finish time for $i$. Then to get the inequality, we recall that $i \lt j$ means that $d(i) \leq d(j)$. Ultimtely, maximum lateness does not increase.
The earliest deadline first schedule $S$ is optimal.
Let $S^*$ be an optimal schedule with the fewest inversions. We assume $S^*$ has no downtime. If $S^*$ has no inversions, then $S^* = S$.
So suppose that $S^*$ has an inversion. Then by Lemma 3.12, there exists two adjacent inverted jobs, say $i$ and $j$. By Lemma 3.13, we can exchange these two jobs to reduce the number of inversions by 1 without increasing the maximum lateness.
But this new schedule is an optimal schedule with fewer inversions, contradicting our assumption that $S^*$ contained the fewest number of inversions.
This proof takes a slightly different argument than "greedy stays ahead". Here, we show that we can transform our solution into the one found by following the greedy strategy, by swapping pieces. This is called an exchange argument.