Greedy Algorithm

Coin Change Problem: Select the minimum number of coins to make change for a given amount.

Fractional Knapsack Problem: Choose items to maximize the value of the knapsack without exceeding its capacity.

Huffman Coding: Build a variable-length prefix-free code to compress data with the minimum average code length.

Interval Scheduling: Select a maximum number of non-overlapping intervals.

Prim's Algorithm: Build a minimum spanning tree of a connected, undirected graph.

Dijkstra's Algorithm: Find the shortest path from a source node to all other nodes in a weighted graph.

Activity Selection: Select the maximum number of non-overlapping activities.

Travelling Salesman Problem

Kruskal’s algorithm for minimum spanning tree.

Graph – Map coloring

Job Scheduling Problem.

A type of optimization algorithm that makes locally optimal choices at each step with the hope of finding a global optimum.

It chooses the best available option at each step without considering the overall effect of the decision.

It works well when there is a clear set of rules for making decisions and the problem can be broken down into smaller subproblems.

The key idea behind the greedy algorithm is to iteratively build a solution by making a series of choices. 

At each step, the algorithm makes the choice that appears to be the best at that particular moment, without worrying about the consequences of that choice on future steps.

Define the problem as a set of subproblems.

• Determine the objective function.

• Determine the constraints.

Create a set of rules for making decisions.

Iterate through the subproblems, making the best decision at each step according to the rules.

Repeat until the object function is optimized.

Advantages: Greedy algorithms are often easy to understand and implement. They work well for optimization problems where finding an exact solution is time-consuming or not feasible.

Disadvantages: Greedy algorithms do not always guarantee optimal solutions globally. They might miss out on a better overall solution due to making locally optimal choices at each step.