Greedy Algorithms

Greedy algorithms are a class of algorithms that make the locally optimal choice at each step with the hope of finding a global optimum. The key idea behind greedy algorithms is to solve a problem by making the best choice at each step and never reconsidering these choices.



Some common examples of greedy algorithms include:


Huffman Coding: A compression algorithm that creates a prefix-free code for representing a set of symbols with variable length code words.

Kruskal's Algorithm: A graph algorithm that finds the minimum spanning tree in a connected, undirected graph by iteratively adding edges with the minimum weight that do not form a cycle.

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

Prim's Algorithm: A graph algorithm that finds the minimum spanning tree in a connected, undirected graph by maintaining a set of vertices that are connected to the tree and adding the smallest-weight edge that connects a vertex outside the set to a vertex inside the set.

Activity Selection Problem: A scheduling problem that selects a maximum-size subset of mutually compatible activities from a set of activities with given start and end times.

Fractional Knapsack Problem: A optimization problem that selects items to include in a knapsack with limited capacity to maximize the total value of the items.

Coin Change Problem: A optimization problem that finds the minimum number of coins required to make a given amount of change.

Job Sequencing Problem: A scheduling problem that assigns jobs to resources such as machines in a way that maximizes some objective, such as the total profit earned.