Introduction to Greedy Approach in Data Structures and Algorithms

A greedy algorithm always makes the choice that looks best at the moment. Greedy algorithms can be characterized as being ‘short sighted’, and also as ‘non-recoverable’. It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. A greedy algorithm obtains an optimal solution to a problem by making a sequence of choices.

To better understand this let’s think of two games Chess and Badminton. In Badminton, one gives his/her best at each shot and that is exactly how GREEDY works- to be the best at present because you cannot predict the next move unlike in Chess where the future moves can be predicted.

Let’s suppose a teacher is asked to make a team of 10 most intelligent students from a given class. So the teacher will start by picking up the most intelligent student first. The teacher is therefore being GREEDY by picking up the best choice for him/her at that moment.

The process to develop a Greedy Algorithm involves the following steps-

1. Determine the optimal substructure of the problem.

2. Develop a recursive solution.

3. Prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice.

4. Show that all but one of the subproblems induced by having made the greedy choice are empty.

5. Develop a recursive algorithm that implements the greedy strategy.

6. Convert the recursive algorithm to an iterative algorithm.

PROBLEMS TO PRACTICE-

1) Fractional Knapsack Problem:

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

2) Minimum cost to connect all cities:

There are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road. Find out the minimum cost to connect all the cities by repairing roads

3) Huffman coding

It is a lossless data compression algorithm, to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.

4) K Centres Problem

Given n cities and distances between every pair of cities, select k cities to place warehouses (or ATMs or Cloud Server) such that the maximum distance of a city to a warehouse (or ATM or Cloud Server) is minimized.