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:

 

Problem: Given set of intervals with starting time and end time, give the set of intervals with maximum cardinality such that no intervals overlap.
Algorithm:
* Initially let R be the set of all requests.
* While R is not empty:
* Choose a request i with earliest finish time
* add to queue A
* delete all incompatible from R.
* EndWhile
* Return A
Analysis:
* A is compatible
* A is optimal with the "Stays Ahead" argument.
* Running Time : O(n logn)

Interval Partitioning Problem:

Problem: Given intervals with finish and end times, partition the intervals into labels with minimum amount of labels so that no two intervals in any label overlap.
Algorithm:
* Sort Intervals w.r.t. starting time, breaking tries arbitrarily.
* Let them be I1, I2, … , In
* For j = 1:n
* For each (i<j && Ii,Ij overlap)
* Exclude the label of Ii from considering for Ij
* EndFor
* If (there exists any label not assigned from 1 to d) Assign that to Ij
* Else Leave Ij unlabeled
* EndFor
Analysis:
* None remained unlabeled if d is the maximum number of intervals that overlap together, proof by contradiction
* Hence d is the depth
* no algorithm can have better no. of labels than depth
* hence optimal
* O(n2)

 

Minimize maximum Lateness:

Problem: Variation of Interval Scheduling, with deadlines and duration given, all must be performed on a single resource, find the ordering with minimum maximum lateness of any interval.
Algorithm:
* Sort Jobs w.r.t the deadlines
* Let them be d1, d2, … ,dn
* Initially f=s
* For (i=1:n)
* Assign s(i) f, f(i) = s(i) + t(i)
* f=f(i)
* EndFor
* Return <s,f>
Analysis:
* There is an optimal solution with no idle time.
* Proof of optimality by "Exchange Argument"

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s