A simple discussion on greedy algorithms

The ‘Greedy paradigm’ or greedy algorithms are part of a programmers toolbox. The tools include the a.) divide and conquer algorithms, b.) randomized algorithms, c.) dynamic programming and d.) greedy algorithms. The term greedy algorithm is a misnomer, greedy is really a technique rather than an algorithm.

According to Hackearth, “[a] greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.” This is a very interesting definition, and what makes the greedy algorithm interesting is that it only gets one change to solve the optimal solution, in that it never goes back and reverses the decision.

Interesting advantages include the ease of which a greedy algorithm can be designed, and that analyzing the run time is generally easier than divide and conquer algorithms.

Disadvantages include that it is often more complicated to determine is the algorithm is fast or slow. Due to the recursive nature, the size gets smaller each time; however, the sub-problems increase. Additionally, it often requires more work to determine the ‘correctness’ of the algorithm and it can be very difficult to ‘prove’ correct.

Everything Computers states that, “[i]n general, greedy algorithms have five components:”

1. A candidate (set, list, etc), from which a solution is created
2. A selection function, which chooses the best candidate to be added to the solution
3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
4. An objective function, which assigns a value to a solution, or a partial solution, and
5. A solution function, which will indicate when we have discovered a complete solution

Two good examples of a greedy algorithm are Huffman Coding, which is used for data compression and Single-source Short Path using Dijkstra’s algorithm, which applies shortest path weights for all given sources and vertices.

A simple use case of a greedy algorithm is solving a problem where you have T time to complete a list of items, and you want maximum results. The greedy method would be to first create an Array of the integers, specifically the time required to do an task. Then, recursively you select the items with the minimum T while you have to variables, runningTime and numberOfTasks, then:

1. Sort A in non-decreasing order
2. select each task one-be-one
3. Add the task to the current runningTime
4. add 1 to the numberOfTasks
5. and repeat until the runningTime meets the overall time you are seeking to complete the most tasks in

References

Basics of greedy algorithms tutorials & notes | algorithms | hackerearth. (n.d.). Retrieved from https://www.hackerearth.com/practice/algorithms/gr eedy/basics-of-greedy-algorithms/tutorial/
Freak, C. (n.d.). Top 7 greedy algorithm problems. Retrieved from https://medium.com/@codingfreak/top-7-greedy-algor ithm-problems-3885feaf9430