Game:

Counter-Strike: Source (2004)

Duration: 0:00

12 views

1

What is Job scheduling algorithm? How job scheduling algorithm can be\nsolved using Greedy algorithmic approach? Explain your answer with\nrespect to Principle, control abstraction, time analysis of control\nabstraction, of greedy approach for the following instance of Knapsack\nproblem. [12]\nEach job is associated with a deadline and profit.\nJob J1 J2 J3 J4 J5\nDeadline 2 1 3 2 1\nProfit 60 100 20 40 20\nGreedy Algorithm

#undergraduates #cs #engineering #computerscience
____________________________________________
Show love pls like share and subscribe ❤️‍🔥
I'm doing my best for you peoples.................



A greedy algorithm makes the locally optimal choice at each stage with the hope of finding a global optimum. It doesn't consider the overall problem; it just focuses on the best immediate option.

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. 

An optimization problem can be solved using Greedy if the problem has the following property: 

At every step, we can make a choice that looks best at the moment, and we get the optimal solution to the complete problem. 

Some popular Greedy Algorithms areFractional Knapsack,Dijkstra’s algorithm,Kruskal’s algorithm,Huffman codingandPrim’s Algorithm

The greedy algorithms are sometimes also used to get an approximation for Hard optimization problems. For example, theTraveling Salesman Problemis an NP-Hard problem. A Greedy choice for this problem is to pick the nearest unvisited city from the current city at every step. These solutions don’t always produce the best optimal solution but can be used to get an approximately optimal solution.

However, it’s important to note that not all problems are suitable for greedy algorithms. They work best when the problem exhibits the following properties:

Greedy Choice Property: The optimal solution can be constructed by making the best local choice at each step.

Optimal Substructure: The optimal solution to the problem contains the optimal solutions to its subproblems.

Characteristics of Greedy Algorithm

Here are the characteristics of a greedy algorithm:

Greedy algorithms are simple and easy to implement.

They are efficient in terms of time complexity, often providing quick solutions. Greedy Algorithms are typically preferred over Dynamic Programming for the problems where both are applied. For example,Jump Gameproblem and Single Source Shortest Path Problem (Dijkstrais preferred overBellman Fordwhere we do not have negative weights).

These algorithms do not reconsider previous choices, as they make decisions based on current information without looking ahead.

These characteristics help to define the nature and usage of greedy algorithms in problem-solving.


How does the Greedy Algorithm works?

Greedy Algorithm solve optimization problems by making the best local choice at each step in the hope of finding the global optimum. It’s like taking the best option available at each moment, hoping it will lead to the best overall outcome.

Here’s how it works:

Start with the initial state of the problem. This is the starting point from where you begin making choices.

Evaluate all possible choices you can make from the current state. Consider all the options available at that specific moment.

Choose the option that seems best at that moment, regardless of future consequences. This is the “greedy” part – you take the best option available now, even if it might not be the best in the long run.

Move to the new state based on your chosen option. This becomes your new starting point for the next iteration.

Repeat steps 2-4 until you reach the goal state or no further progress is possible. Keep making the best local choices until you reach the end of the problem or get stuck.

Example:

Let’s say you have a set of coins with values [1, 2, 5, 10] and you need to give minimum number of coin to someone change for 39.

The greedy algorithm for making change would work as follows:

Step-1: Start with the largest coin value that is less than or equal to the amount to be changed. In this case, the largest coin less than or equal to 39 is 10.

Step- 2: Subtract the largest coin value from the amount to be changed, and add the coin to the solution. In this case, subtracting 10 from 39 gives 29, and we add one 10-coin to the solution.

Repeat steps 1 and 2 until the amount to be changed becomes 0.

Other Statistics