19.4.1. Formal representation of the Algorithm

So, we are looking at algorithms where we need to achieve a global optimum by making a sequence of choices. So, in a greedy strategy what we do is we make the next choice based on some local criteria. So, there maybe a number of choices we could make, but we just pick one of them based on something which looks good at the moment and now we never go back and revise an earlier decision.

In this chunk, we see that greedy algorithms aim to find the best overall solution (global optimum) by making a series of choices based on what seems best at the current stage. Essentially, at each step, the algorithm picks the option that appears most beneficial at that moment without considering the overall picture or future consequences. This is a key characteristic of greedy algorithms: they do not backtrack to revise choices once they are made.

Imagine you are at a buffet with a wide variety of foods. At each table, you choose the dish that looks the most appealing at that moment without thinking about how it fits with what you've picked before or what you might be missing out on. This is similar to how a greedy algorithm works.

So, we have seen three algorithms so far which follow this 3D paradigm. The first was Dijkstra’s algorithm for the single source shortest path problem. So, recall that in this algorithm we kept burning vertices and at each stage we froze the distance to the nearest unburnt vertex and claim that this would in fact be the shortest distance to that vertex from the source.

Dijkstra's algorithm is an example of a greedy algorithm that solves the single-source shortest path problem. The algorithm works by selecting the closest unvisited vertex, updating the distances to its neighboring vertices, and 'freezing' the shortest distance to that vertex once it has been visited. This continues until all vertices have been visited. The result is that the algorithm guarantees finding the shortest path from the starting vertex to all other vertices.

Think of it like navigating through a city using a map. You constantly check the distance to your next stop and choose the closest one to visit first. Once you visit that stop, you note how far you are from it to the next stop and move on. This ensures that you always travel the shortest route to each location.

A closely related algorithm is Prim’s algorithm for the minimum cost spanning tree. So, here we incrementally build up a tree and at each stage we add to this spanning tree, the nearest vertex that is not yet in the tree.

Prim's algorithm constructs a minimum spanning tree by starting with a single vertex and repeatedly adding the shortest edge that connects the existing tree to a new vertex. By always choosing the shortest edge that grows the tree without forming cycles, the algorithm guarantees that the resulting tree has the minimum possible total edge weight.

Imagine you are building a network of roads between various towns. You start with one town and gradually add roads to connect it to the nearest town. By always choosing the shortest available road, you ensure that the total distance of all roads (the total cost) is minimized.

Another algorithm for a minimum cost spanning tree is Kruskal’s algorithm. Here, we do not build up a tree directly, but rather we keep collecting edges and form a connected component overall which becomes a tree.

Kruskal's algorithm works by sorting all the edges of the graph in non-decreasing order based on their weight. It then adds edges one by one, starting with the lightest, to construct a minimum spanning tree, ensuring that no cycles are formed. This continues until we have included enough edges to connect all vertices.

It's like laying down cables for internet connectivity between houses in a neighborhood. You would want to connect the homes using the least amount of cable possible. By starting with the shortest cables (cheapest edges) and ensuring not to loop back, you efficiently create a connected network.

So, now let us look at a completely different problem, a problem called interval scheduling. So, suppose we have a special video classroom, where we can deliver online lectures. Now, different teachers want to book the classroom to deliver classes and each instructor has a slot that he would like to deliver this lecture in.

In the interval scheduling problem, the objective is to schedule a maximum number of non-overlapping classes given various time slots that instructors wish to book. The challenge is that some of these slots may overlap, making it impossible to accommodate all requests. The greedy approach involves selecting slots based on certain criteria to maximize the number of teachers who can deliver their lectures.

Imagine you're organizing a theater schedule. You have several actors wanting to perform their plays, but some plays are at the same time. Your goal is to choose plays that allow the maximum number of different actors to perform without overlapping their time slots.

So, broadly if we follow a greedy approach, this is what we would do. Among all the bookings that are not yet allocated and which are still available to allocate, we will pick one based on some local strategy, then we would remove all conflicting bookings.

In a greedy strategy to solve the interval scheduling problem, after selecting a booking, the algorithm will remove any bookings that conflict with the chosen one (i.e., those that overlap in time). This step is critical, as it simplifies the remaining choices. However, it’s important to choose wisely to maximize the total bookings allowed.

Going back to our theater analogy, after you select a play for one slot, you immediately take note of any overlapping plays. By not selecting those, you're ensuring that you have more options for the next slot and can fit in as many performances as possible.

So, one strategy might be to choose the booking whose start time is earliest, but it is not difficult to come up with the counter example.

Choosing the booking that starts the earliest might seem like a good strategy, but it could lead to selecting a slot that eliminates too many other potential bookings. For instance, if a booking is very long and starts first, it could block out many other shorter bookings that collectively could accommodate more teachers. Therefore, this greedy strategy is often flawed.

Think of selecting the first ride in an amusement park. It may be the shortest line, but if it takes so long, you could miss out on riding several other rides that have shorter waiting times. Hence, while it looks good early on, it doesn't yield the best overall experience.

So, here is a fourth strategy, instead of choosing the one like we begin with whose start time is earliest, let us choose the one whose finished time is earliest.

The winning strategy for the interval scheduling problem is to always pick the booking that finishes the earliest. This minimizes the occupied time in the classroom, allowing for more opportunities to schedule additional bookings thereafter. By consistently selecting the earliest finishing time, the algorithm can prove to be optimal in maximizing the number of classes.

Returning to our classroom example, imagine if a teacher finishes their lecture quickly, this allows other teachers to take their slots right after. By continuously selecting those who finish earliest, we can get the maximum usage of the classroom, accommodating the most number of teachers.

--