#greedy algos

[coding-quark]

Flow Chart for Greedy Algos

[coding-quark]

Greedy Solution for Jump game - 2

Greedy choice: Similiar to Jump Game 1, I am trying to reach the furthest point possible from a give range, with the (correct) hope that it'll help me reach the end with minimum number of steps.

Step 1 : Backtracking

At step 1, we thought of a recursive backtracking solution where we try out all the possibilities.

Step 2 : Convert to Greedy

From this we realized there is a range of values we can traverse from any given i. The range is (l, r) = (i + 1, farthest range).

Then based on this, we try to locally maximize the farthest possible we can reach from a given indx, since reaching the maximum at any point means we will have to make less jumps in the future

3. As seen in drawing 1, we had a tree, but since we only care for maxium at the range, what we do is we convert the tree into a range and then try to jump to the next range with the maximum reach so we can reduce the minimum jumps.

Thoughts:

1. The greedy choice property says that making the locally optimal choice (choosing the farthest reach) leads to the globally optimal solution (minimum jumps). So, in this case, each time we choose the farthest possible reach, we are making the best possible decision for the current step, which leads to the minimal total jumps. 2. By picking from the entire range at each step, we are considering all possibilities within a range in one iteration and picking (greedily) the maximum one.

[coding-quark]

Greedy Choice for problems solved

Assign Cookies based on size and greed factor - Greedy choice: Give each child the minimum size cookie so larger size cookies are present for future children - Optimal Substructure: the same locally optimal choice made for n children, then n-1 children and so on.

Fractional Knapsack Problem - Greedy Choice: Pick the maximum value/wt at each step to maximise the elements that can be held in the knapsack - Optimal Substructure: same applied for 1,2...n item to be polaced in bag.

Greedy algorithm to find minimum number of coins - Greedy Choice: Since we want to minimize the number of coins, we can start with the maximum currency value that can be provided

Lemonade Change Greedy Choice Property: - Using larger denominations (e.g., $10) for $20 change is better than using smaller ones because it preserves $5 bills for future $10 transactions - For example, if you use three $5s for a $20 bill, you might not have enough $5s to serve a later customer who pays with a $10. Optimal Substructure: - The problem can be decomposed into steps where each decision (giving back $5 or $10) affects the availability of bills for future customers. - The greedy choice of using larger bills first ensures that the solution is globally optimal.

Valid Paranthesis checker:

This approach satisfies the greedy choice property because each decision (treat '' as ')' or '(') is made based on the current state, and the algorithm proceeds step by step, trying to make the best possible choice at each step. The optimal substructure here is that the decision to use a '' as a ')' or '(' at each step affects the remaining possibilities, and the greedy choice leads to the correct overall solution.

So the problem satisfies the greedy property because the algorithm makes choices that are locally optimal (using '' as a closing bracket first) and these choices lead to a globally optimal solution (valid string). The key is that the greedy choice of using '' as a closing bracket first ensures that we have the best chance of meeting the required number of closing brackets, and if that's not possible, using it as an opening bracket allows for more flexibility.

6. N meeting room: - Greedy Choice: We pick the meeting with the minimum ending time, as it leaves the maximum possible time for future meetings to be held.

7. Jump Game:

1. In the greedy approach, maybe the algorithm is not about choosing the maximum possible step each time, but rather keeping track of the maximum reachable index 2. The greedy choice is to always track the farthest you can reach. The key is that at each step, you don't need to look ahead to choose the best path, but rather just keep track of the maximum reach. Because if you can reach a certain index, you can take the maximum possible step from there, which would be the optimal choice. 3. Greedy Choice: At each index i, the best choice is to jump to the farthest reachable index from i. This ensures that we maximize the range of reachable positions, increasing the chance of reaching the end. 4. Optimal Substructure: The problem can be broken down into subproblems where the optimal solution is determined by the farthest reachable index at each step. If the current index is beyond the farthest reachable index, it's impossible to proceed further. 5. No Need for Backtracking: The greedy approach doesn't require checking all possible paths, as it only tracks the farthest reachable index

8. Jump Game - 2

1. Greedy choice: Similiar to Jump Game 1, I am trying to reach the furthest point possible from a give range, with the (correct) hope that it'll help me reach the end with minimum number of steps. 2. See Separate approach post for this under approach.,

[coding-quark]

Greedy Algorithm

A greedy algorithm is a problem-solving approach that makes the locally optimal choice at each step, with the hope that these choices will lead to a globally optimal solution. Unlike brute-force or dynamic programming methods, greedy algorithms do not explore all possible options but instead make decisions based on the best immediate choice. This approach is efficient but may not always yield the optimal result, depending on the problem's structure.

How Greedy Algorithms Work

Step-by-Step Decision-Making:

At each step, the algorithm selects the best possible option based on the current state of the problem.

This decision is made without considering future consequences, which can sometimes lead to suboptimal results.

No Backtracking:

Once a choice is made, the algorithm does not revisit earlier decisions. This makes greedy algorithms efficient but potentially limited in scope.

Local vs. Global Optimality:

A greedy algorithm relies on the greedy choice property: the locally optimal choice at each step leads to a globally optimal solution.

This is not always guaranteed, but when it holds, the algorithm is effective.

Key Characteristics of Problems Solved by Greedy Algorithms

A problem can be solved using a greedy algorithm if it satisfies the following two properties:

1. Greedy Choice Property

The optimal solution can be constructed incrementally by making the locally optimal choice at each step.

Example: In the activity selection problem, selecting the activity that ends the earliest ensures maximum flexibility for future choices.

2. Optimal Substructure

The optimal solution to the problem can be decomposed into subproblems that also have optimal solutions.

Example: In Huffman coding, the optimal encoding tree is built by repeatedly combining the two nodes with the smallest frequencies.

How to Identify a Problem for a Greedy Algorithm

To determine if a problem is suitable for a greedy algorithm, ask:

Can the problem be broken into steps where each step makes a locally optimal choice?

Does the choice at each step affect the remaining problem in a predictable way?

Is the problem structured such that the greedy choice leads to the global solution?

Examples of Problems Solved by Greedy Algorithms:

Activity Selection Problem:

Goal: Select the maximum number of non-overlapping activities.

Greedy Strategy: Always pick the activity that ends earliest.

Huffman Coding:

Goal: Compress data with minimum total encoded length.

Greedy Strategy: Combine the two nodes with the smallest frequencies.

Dijkstra’s Algorithm:

Goal: Find the shortest path in a graph.

Greedy Strategy: Always select the node with the smallest tentative distance.

Prim’s/Kruskal’s Algorithm:

Goal: Find the minimum spanning tree (MST) of a graph.

Greedy Strategy: Add edges or nodes that minimize the total weight.

Job Scheduling:

Goal: Schedule jobs to minimize lateness.

Greedy Strategy: Sort jobs by deadlines or processing times.

Steps to Apply a Greedy Algorithm

Define the Problem:

Identify the objective and constraints (e.g., maximize profit, minimize cost, etc.).

Identify the Greedy Choice:

Determine the rule for making the locally optimal choice (e.g., "always pick the smallest element").

Implement the Greedy Strategy:

Use a loop or recursive function to apply the greedy choice step-by-step.

Verify the Solution:

Check if the greedy choice leads to the global optimal solution (using examples or proofs).

When Greedy Algorithms Fail

Greedy algorithms may fail if:

The locally optimal choice does not lead to the global solution (e.g., the Traveling Salesman Problem).

The problem requires considering future choices (e.g., scheduling with dependencies).

Comparison with Dynamic Programming

How do I differentiate between greedy and dynamic programming? Because both use optimal substructure. But greedy algorithms make decisions without looking ahead, while dynamic programming considers all possibilities. So the key is that for a problem with the greedy choice property, you can make a choice that leads to the optimal solution without needing to check all possibilities. Greedy Algorithm : 1. Approach : Makes one choice at a time 2. Efficiency : Fast (O(n)) 3. Optimality: May not always be optimal 4. Use Case: Problems with clear greedy choice property

Dynamic Programming: 1. Approach : Explores all possibilities 2. Efficiency Slower (O(n²) 3. Optimality: Always optimal (for problems with optimal substructure) 4. Use Case Problems requiring exploration of all subproblems

Summary

Greedy algorithms are efficient but not always optimal.

They work best when the greedy choice property and optimal substructure hold.

Use them for problems where local choices directly lead to global solutions (e.g., activity selection, Huffman coding).

Always validate the solution with examples or proofs to ensure correctness.