Greedy Algorithms Explanation and Problems and Solutions

Greedy algorithm is one of the mathematical processes that look simple, easy to implement, a solution to the complex and multi-step problem by deciding the next step that provides an obvious benefit. Such algorithms are known as greed, while the optimal solution of a small instance will provide an immediate output. These algorithms do not consider as a large problem, at once the decisions are made and never be reconsidered.

Greedy algorithm works by constructing a set of an object from the small possible constituent part. Recursion approaches problem solving method in which the solution is particularly depending on the solution to a smaller instance for the same problem. The freelance designer often uses an ad-hoc mobile network, which efficiently routes their packets with a few numbers of hops and short delay possible. They are used in business intelligence (BI), programming, artificial intelligence (AI) and machine learning.

Structure of Greedy algorithm

• Initially, a set of chosen items are empty that is the solution set.
• At each step:
• Item will add a set of solutions by using only selection function.
• If set would no longer be feasible, then reject the items under consideration.
• Else if a set is now feasible, then add a current item.

Characteristics and features of the solving problem:

The freelance designer gives a solution of constructing in an optimal manner. An algorithm is maintained 2 sets in which one set has chosen an item and another set contains rejected the item. Greedy algorithm consists of four functions. They are:

• The function checks whether chosen item provides a solution.
• The function checks a set of feasibility.
• Selection function says in which candidates one of the most is promising.
• An objective function does not appear to give a solution value.

Standard Greedy algorithms:

Prim’s Minimum Spanning Tree: In this algorithm, create a minimum spanning tree by choosing edge one after one. It maintains two sets: the first set is a set of vertices that are already included in a minimum spanning tree and the second set is a set of vertices that are not included in a minimum spanning tree. This Greedy choice is to select the smallest weight edge that is connected to two sets.

Kruskal’s Minimum Spanning Tree: This algorithm creates a minimum spanning tree by choosing edges one after the other process. This Greedy choice is chosen from the smallest weight edge, but it does not cause a chain reaction in a minimum spanning tree that is constructed so far. The freelance web designer helps you for providing tricks and tips of Kruskal’s MST.

Huffman coding: Huffman coding is a lossless compression technique. It is assigned to a variable of length bit code to the much different character. The Greedy choice assigns at least bit length code to a frequent character.

Dijkstra’s Shortest Path: This algorithm is very similar to the Prim’s algorithm. The shortest path tree is built to edge by edge. This algorithm also maintains two sets: the first one is set of vertices including tree while another one is not yet to include the tree. The Greedy choice is chosen by the edge that is connected to the two sets. Then it is a source set of the smallest weight path that is not yet included in vertices.

Greedy algorithm problem and solution:

1. Method of activity selection problem in C++:

// C++ program for activity selection problem

// the following implementation is assumed that activities

// are already sorted in according to the finish time

#include<stdio.h>

// print a maximum set of activities that can be done in single opration

// person, one at the time

// n — > total number of activities

// s [ ] — > an array contains start time of all activities

// f [ ] — > an array contains finish time of all activities

Void print max activities (int s [ ], int f [ ], int n)

{

int i, j;

print f (“ following activities are selected \n”);

// the first activity always gets selected

i = 0;

print f (“%d”, i);

// consider rest of the activities

for (j = 1; j < n; j++)

{

// if this activity has start time greater than or

// equal to the finish time of previous selected

// activity, then select it

if (s [ j ] > = f [ i ])

{

Print f (“%d” , j);

i = j;

}

}

}

// driver program to test above function

int main ( )

{

int s [ ] = {1, 3, 0, 5, 8, 5};

int f [ ] = {2, 4, 6, 7, 9, 9};

int n = size of ( s ) / size of (s [0]);

print max activities (s, f, n);

return 0;

}

Output of the program:

Following activities are selected: 0 1 3 4

2. Alternative method of activity selection problem in C:

GREEDY – ACTIVITY – SELECTOR ( s, f )

N ß length [ s ]

A ß { a1 }

i ß 1

for m ß 2 to n

do if sm >= fi

then A ß A U { am }

i ß m

return A

Example:

Selected activities are: A1, A4, A8, A11

Program in C:

#include <stdio.h>

#include <conio.h>

Void activities (int s [ ], int f [ ], int n);

{

int i, j;

print f (“ selected activities are:  \n”);

i = 1;

print f (“a % d”, i);

for (j = 1; j < n; j++)

{

if ( s [ j ] . = f [ i ])

{

print f (“a % d”, j + 1);

i = j:

}

}

}

void main ( )

{

int s [ ] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};

int f [ ] = { 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16};

int n = size of ( s ) / size of (s [0]);

clrscr ( );

activities (s, f, n);

getchar ( );

getch ( );

}

Output of the program:

Selected activities are: A1, A4, A8, and A11

In the above case, a Greedy algorithm did consider a pretty job. An interesting thing is that the freelance web designer can prove a Greedy algorithm produces the right answer.