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.