Mark As Completed Discussion

In this tutorial, we'll look at yet another technique for finding an optimal solution to a problem. Dynamic programming considers all the solutions of a problem and selects the best or optimal one. But despite finding the most efficient solution, the problem is still speed and memory. For a large problem, it could take a long time to solve, and in some cases, may consume too much memory.

Greedy algorithms are designed for speed. When given a sub-problem, a greedy algorithm chooses the local best solution and moves towards the final goal, hoping this strategy would closely approximate the "global" optimal solution.

This sounds great, but one thing to keep in mind is that greedy algorithms do not always get us the most optimal solution for some problems. They may give a sub-optimal solution in such cases. However, there are problems for which it is proven that greedy algorithms do provide the best solution, which makes them awesome fits of strategy in certain situations.

Introduction

In this tutorial, I will give examples of problems, where the greedy algorithm gives a sub-optimal solution, along with problems for which it gives an optimal answer.