Greedy Algorithms and Dynamic Programming

These flashcards cover key terms and concepts related to greedy algorithms and dynamic programming, based on provided lecture notes.

Greedy Algorithm

An algorithm that makes the best possible choice at the current step and then moves forward without reconsidering previous decisions.

Local Optimal Choice

The best choice at the current step in a greedy algorithm.

Global Optimum

The best overall solution for the entire problem across all choices.

Greedy Choice Property

A property where a locally optimal choice can be made without affecting the final optimal solution.

Optimal Substructure

A characteristic of a problem where an optimal solution to the problem can be constructed from optimal solutions to its subproblems.

Dynamic Programming

A method that explores all possibilities to guarantee the optimal solution, rather than making decisions step-by-step.

Minimum Coin Change Problem

An optimization problem to find the minimum number of coins needed to make a target amount.

Coin Denominations

The different values of coins available for use in the minimum coin change problem.

Activity Selection Problem

An optimization problem where the goal is to select the maximum number of non-overlapping activities.

Time Complexity of Greedy Algorithms

The measure of the time taken by an algorithm to run, often determined by sorting activities or making selections.