Hello World! What are Greedy Algorithms?

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!

Greedy Algorithms

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:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s