So hello world.. This would be the first post on this blog.
The posts here would be of the kind that are easy to read, objective oriented, and food for thought.
So this one goes for the beginners… don’t worry, after reading this you will not be a one!
Definition: An algorithm which makes locally optimum choices with a hope to make the whole outcome optimum.
Points to remember:
- Greedy Algorithms are most commonly proved using two different approaches
- First proving approach is “Stays Ahead” where you prove that your algorithm stays ahead in terms of the underlying criteria w.r.t. to any other approach.
- Second proving approach is called “Exchange Argument”, where you start with the optimal solution and exchange it with the greedy approach using some number of steps so that at each step you prove that you are not decreasing the outcome.
Some Basic Pseudocodes:
Interval Scheduling Problem:
Interval Partitioning Problem:
Minimize maximum Lateness: