# Greedy Algorithms

Greedy Algorithms follow a problem solving approach wherein they make the locally optimal choice at each stage, with the hope of finding a global optimum.

The focus is, however, on finding the local optimums at each step, regardless of whether a global optimum is ever obtained.

The image below depicts the result of a greedy algorithm that needed to find the largest possible sum, starting from the root. It focused on choosing the maximum value at each step, leading to a solution that wasn't globally optimal.

![](https://3948333774-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGUlk-QSaYojNDb%2F-M5-0Rj4EGfG_XkWurSp%2F-M5-0Vdhv95ASE7OMw6J%2FGreedy_Solution.PNG?generation=1586990816732874\&alt=media)

The image below depicts the globally optimal solution (in green).

![](https://3948333774-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5-0RGUlk-QSaYojNDb%2F-M5-0Rj4EGfG_XkWurSp%2F-M5-0Vdj9oFA-bRxgDAe%2FActual_Solution.PNG?generation=1586990817719642\&alt=media)

**Pros of Greedy Algorithms**:

* simple
* easy to implement
* reasonable complexity

**Cons of Greedy Algorithms**:

* may not result in a globally optimal solution for any given problem

**Where do we use Greedy Algorithms?**

Problems that can be solved using Greedy Algorithms satisfy the following properties:

* **Greedy choice property**: from a local optimum we can reach a global optimum, without having to reconsider the decisions already taken
* **Optimal Substructure**: an optimal solution can be constructed efficiently from the optimal solutions of its subproblems

*A Greedy Algorithm never reconsiders its choices!*

Some common problems solved using the greedy approach include:

* Activity Selection problem
* Fractional Knapsack Problem
* Minimum Number of Coins
* Huffman Coding
* Job Sequencing problem
* Kruskal's Minimum Spanning Tree
* Prim's Minimum Spanning Tree
* Dijkstra's Shortest Path problem


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/main/chapter1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.