Greedy Algorithm

These flashcards cover the key terms and concepts related to greedy algorithms, their properties, applications, and challenges.

Greedy Algorithm

An approach for solving a problem by selecting the best option available at the moment without worrying about the future consequences.

Greedy Choice Property

An optimal solution can be found by choosing the best choice at each step without reconsidering previous steps.

Optimal Substructure

The optimal overall solution corresponds to the optimal solution of its subproblems.

Advantages of Greedy Algorithm

Easier to describe and can perform better than other algorithms in certain cases.

Disadvantage of Greedy Algorithm

Does not always produce the optimal solution.

Activity Selection Problem

A problem where the goal is to select the maximum number of non-overlapping activities based on their start and finish times.

Job Sequencing Problem

A problem that involves scheduling jobs with deadlines to maximize profit.

Fractional Knapsack Problem

A problem where items can be broken into smaller parts, solved by calculating the profit-to-weight ratio.

Graph Coloring Problem

A way of coloring vertices of a graph so that no two adjacent vertices share the same color.

K-colorable Graph

A coloring using at most k colors.

Greedy Coloring Algorithm

An algorithm that colors the vertices of a graph in sequence, assigning each vertex the smallest available color not used by its neighbors.