Greedy method class 11

Jan 28, 2014Download as pptx, pdf6 likes4,260 views

The greedy method constructs solutions to optimization problems by making locally optimal choices at each step that are irrevocable. While it does not always yield an optimal solution, it provides fast approximations. It progresses top-down by expanding a partially constructed solution at each step until complete. Greedy algorithms are optimal if they exhibit the greedy choice property and optimal substructure - where the optimal solution to the overall problem contains optimal solutions to its subproblems.

Basic Idea
•

•

•

Construct a solution to an optimization
problem piece by piece through a sequence
of choices that are:
• feasible
• locally optimal
• Irrevocable
For some problems, they yield an optimal
solution for every instance.
For most, they don’t, but can be useful for
fast approximations.
2

Greedy Method
• Most straight forward design technique.
• Usually progresses in a top-down fashion.
• Solution is constructed through a sequence of
steps, each expanding a partially constructed
solution obtained so far, until a complete
solution to the problem is reached.
• Greedy Method Provides optimal solutions.

Feasible and Optimal Solutions
• Most of the problems have ‘n’ inputs and
require us to obtain a subset that satisfies
some constraints.
• Any subset that satisfies these constraints is
called a feasible solution.
• Greedy method finds a feasible solution that
either maximizes or minimizes a given
objective function.
• A feasible solution which meets the objective
function is called optimal solution.

Greedy Steps
• Select some solution from input domain.
• Then check the selected solution is feasible or
not.
• Select the Optimal Solution (solution that
satisfies or nearly satisfies the objective function)
from set of feasible solutions.
• Greedy method works in stages. At each stage only
one input is considered at each time. Based on this
input it is decided whether particular input gives the
optimal solution or not.

Greedy Algorithm
Greedy(D,n)
// In Greedy approach D is a domain
// from which solution is to be obtained of size n
// Initially assume
Solution<-0
for i<-1 to n do{
s<-select(D) //selection of solution from D
if(Feasible (Solution , s)) then
Solution<-Union(Solution, s)
}
return Solution

Greedy Algorithms are Optimal
• The following are the two key ingredients to
prove the Greedy Algorithms are optimal.
1. Greedy Choice Property
2. Optimal Substructure

Greedy Choice Property
• Global optimal solution will be made with
local optimal (greedy) choices.
• In a greedy algorithm, the best choice will be
selected at the moment to solve the sub
problem that remains.
• The choice of the greedy may depend on the
choices so far, but it can’t depend on the
future choices or on the solutions to the subproblems.

Optimal Substructure
• Optimal substructure is a property of Greedy
solution.
• A problem exhibits optimal substructure if an
optimal solution to the problem contains
within it optimal solutions to the subproblems.

Procedure to prove the Optimal
Greedy Algorithms
1. Consider globally-optimal solution
2. Show greedy choice at first step reduces problem
to the same but smaller problem. Greedy Choice
must be part of an optimal solution and made
first.
3. Use induction to show greedy choice is best at
each step i.e., optimal substructure

Applications of the Greedy Strategy
• Optimal solutions:
change making for “normal” coin denominations
minimum spanning tree (MST)
single-source shortest paths
scheduling problems
Huffman codes

• Approximations:
traveling salesman problem (TSP)
knapsack problem
11
other combinatorial optimization problems

1) The document describes the divide-and-conquer algorithm design paradigm. It can be applied to problems where the input can be divided into smaller subproblems, the subproblems can be solved independently, and the solutions combined to solve the original problem. 2) Binary search is provided as an example divide-and-conquer algorithm. It works by recursively dividing the search space in half and only searching the subspace containing the target value. 3) Finding the maximum and minimum elements in an array is also solved using divide-and-conquer. The array is divided into two halves, the max/min found for each subarray, and the overall max/min determined by comparing the subsolutions.

Graph coloring using backtrackingshashidharPapishetty

This document summarizes graph coloring using backtracking. It defines graph coloring as minimizing the number of colors used to color a graph. The chromatic number is the fewest colors needed. Graph coloring is NP-complete. The document outlines a backtracking algorithm that tries assigning colors to vertices, checks if the assignment is valid (no adjacent vertices have the same color), and backtracks if not. It provides pseudocode for the algorithm and lists applications like scheduling, Sudoku, and map coloring.

Contiguous Memory Allocation-R.D.SivakumarSivakumar R D .

The document discusses contiguous memory allocation and strategies for partition allocation such as first fit, best fit, and worst fit. It defines contiguous memory allocation as each process being contained in a single contiguous section of memory. It also describes fragmentation as either external, where total memory exists but is not contiguous, or internal, where allocated memory is slightly larger than requested. To reduce external fragmentation, it suggests compaction by shuffling memory contents to place all free memory together. Paging and segmentation are presented as two complementary techniques to non-contiguous allocation.

Performance analysis(Time & Space Complexity)swapnac12

The document discusses algorithms analysis and design. It covers time complexity and space complexity analysis using approaches like counting the number of basic operations like assignments, comparisons etc. and analyzing how they vary with the size of the input. Common complexities like constant, linear, quadratic and cubic are explained with examples. Frequency count method is presented to determine tight bounds of time and space complexity of algorithms.

System callshahadat hossain

System calls allow programs to request services from the operating system kernel. They are generally implemented as assembly instructions and can be invoked from C/C++. Parameters can be passed via registers, memory blocks, or pushing to the stack. System calls are categorized as process control, file management, device management, information maintenance, and communication. Examples provided include creating and terminating processes, opening and closing files, reading/writing devices, getting time/date, and sending/receiving messages.

N queen problemRidhima Chowdhury

This document presents an overview of the N-Queen problem and its solution using backtracking. It discusses how the N-Queen problem was originally proposed as a chess puzzle in 1848 and involved placing N queens on an N×N chessboard so that no two queens attack each other. It then explains how backtracking can be used to systematically place queens on the board one by one and remove placements that result in conflicts until all queens are placed or no more placements are possible. Examples are given showing the backtracking process and solution trees for 4x4 boards. The time complexity of this backtracking solution is analyzed to be O(N!).

RecurrencesDr Sandeep Kumar Poonia

Types of grammer - TOCAbhayDhupar

daa-unit-3-greedy methodhodcsencet

The document discusses the greedy method algorithmic approach. It provides an overview of greedy algorithms including that they make locally optimal choices at each step to find a global optimal solution. The document also provides examples of problems that can be solved using greedy methods like job sequencing, the knapsack problem, finding minimum spanning trees, and single source shortest paths. It summarizes control flow and applications of greedy algorithms.

Deadlock ppt Sweetestangel Kochar

Randomized algorithms ver 1.0Dr. C.V. Suresh Babu

This document discusses randomized algorithms. It begins by listing different categories of algorithms, including randomized algorithms. Randomized algorithms introduce randomness into the algorithm to avoid worst-case behavior and find efficient approximate solutions. Quicksort is presented as an example randomized algorithm, where randomness improves its average runtime from quadratic to linear. The document also discusses the randomized closest pair algorithm and a randomized algorithm for primality testing. Both introduce randomness to improve efficiency compared to deterministic algorithms for the same problems.

The n Queen ProblemSukrit Gupta

This document summarizes the n-queen problem, which involves placing N queens on an N x N chessboard so that no queen can attack any other. It describes the problem's inputs and tasks, provides examples of solutions for different board sizes, and outlines the backtracking algorithm commonly used to solve this problem. The backtracking approach guarantees a solution but can be slow, with complexity rising exponentially with problem size. It is a good benchmark for testing parallel computing systems due to its iterative nature.

02 order of growthHira Gul

Time complexity analysis specifies how the running time of an algorithm depends on the size of its input. It is determined by identifying the basic operation of the algorithm and counting how many times it is executed as the input size increases. The time complexity of an algorithm can be expressed as a function T(n) relating the input size n to the running time. Common time complexities include constant O(1), linear O(n), logarithmic O(log n), and quadratic O(n^2). The order of growth indicates how fast the running time grows as n increases and is used to compare the efficiency of algorithms.

OpenMP Tutorial for BeginnersDhanashree Prasad

OpenMP is an API used for multi-threaded parallel programming on shared memory machines. It uses compiler directives, runtime libraries and environment variables. OpenMP supports C/C++ and Fortran. The programming model uses a fork-join execution model with explicit parallelism defined by the programmer. Compiler directives like #pragma omp parallel are used to define parallel regions. Work is shared between threads using constructs like for, sections and tasks. Synchronization is implemented using barriers, critical sections and locks.

Ai lecture 7(unit02)vikas dhakane

Backtracking & branch and boundVipul Chauhan

The document discusses backtracking and branch and bound algorithms. Backtracking incrementally builds candidates and abandons them (backtracks) when they cannot lead to a valid solution. Branch and bound systematically enumerates solutions and discards branches that cannot produce a better solution than the best found so far based on upper bounds. Examples provided are the N-Queens problem solved with backtracking and the knapsack problem solved with branch and bound. Pseudocode is given for both algorithms.

Computability - Tractable, Intractable and Non-computable FunctionReggie Niccolo Santos

DeadlockRajandeep Gill

The document discusses deadlocks in computer systems. It defines deadlock, presents examples, and describes four conditions required for deadlock to occur. Several methods for handling deadlocks are discussed, including prevention, avoidance, detection, and recovery. Prevention methods aim to ensure deadlocks never occur, while avoidance allows the system to dynamically prevent unsafe states. Detection identifies when the system is in a deadlocked state.

Answers computer networks 159334 assignment_2_2010Lakshmi Gupta

Bruteforce algorithmRezwan Siam

Critical section problem in operating system.MOHIT DADU

The critical section problem refers to ensuring that at most one process can execute its critical section, a code segment that accesses shared resources, at any given time. There are three requirements for a correct solution: mutual exclusion, meaning no two processes can be in their critical section simultaneously; progress, ensuring a process can enter its critical section if it wants; and bounded waiting, placing a limit on how long a process may wait to enter the critical section. Early attempts to solve this using flags or a turn variable were incorrect as they did not guarantee all three requirements.

AI - Local Search - Hill ClimbingAndrew Ferlitsch

State space searchchauhankapil

This document discusses state space search in artificial intelligence. It defines state space search as consisting of a tree of symbolic states generated by iteratively applying operations to represent a problem. It discusses the initial, intermediate, and final states in state space search. As an example, it describes the water jug problem and its state representation. It also outlines different types of state space search algorithms, including heuristic search algorithms like A* and uninformed search algorithms like breadth-first search.

Lecture 24 iterative improvement algorithmHema Kashyap

Iterative improvement algorithms are suitable for optimization problems where the path to a solution is irrelevant and the goal state itself is the solution. These algorithms maintain a single current state and try to iteratively improve it. Some key advantages are that they only require tracking the current state, saving memory, and are suitable for both online and offline search. Examples of problems that can use iterative improvement algorithms include the traveling salesman problem and N-Queens problem.

Intermediate code generation (Compiler Design) Tasif Tanzim

Page replacement algorithmssangrampatil81

This document discusses different page replacement algorithms used in operating systems. It begins by explaining the basic concept of page replacement that occurs when memory is full and a page fault happens. It then describes several common page replacement algorithms: FIFO, Optimal, LRU, LRU approximations using reference bits, and Second Chance. The key aspects of each algorithm are summarized, such as FIFO replacing the oldest page, Optimal replacing the page not used for longest time, and LRU approximating this by tracking recently used pages. The document provides an overview of page replacement techniques in computer systems.

Single source Shortest path algorithm with exampleVINITACHAUHAN21

The document discusses greedy algorithms and their application to solving optimization problems. It provides an overview of greedy algorithms and explains that they make locally optimal choices at each step in the hope of finding a globally optimal solution. One application discussed is the single source shortest path problem, which can be solved using Dijkstra's algorithm. Dijkstra's algorithm is presented as a greedy approach that runs in O(V2) time for a graph with V vertices. An example of applying Dijkstra's algorithm to find shortest paths from a source node in a graph is provided.

AI Lecture 3 (solving problems by searching)Tajim Md. Niamat Ullah Akhund

The document discusses problem solving by searching. It describes problem solving agents and how they formulate goals and problems, search for solutions, and execute solutions. Tree search algorithms like breadth-first search, uniform-cost search, and depth-first search are described. Example problems discussed include the 8-puzzle, 8-queens, and route finding problems. The strategies of different uninformed search algorithms are explained.

Knapsack ProblemJenny Galino

The document discusses the knapsack problem, which involves selecting a subset of items that fit within a knapsack of limited capacity to maximize the total value. There are two versions - the 0-1 knapsack problem where items can only be selected entirely or not at all, and the fractional knapsack problem where items can be partially selected. Solutions include brute force, greedy algorithms, and dynamic programming. Dynamic programming builds up the optimal solution by considering all sub-problems.

Greedy AlgorihmMuhammad Amjad Rana

This document outlines greedy algorithms, their characteristics, and examples of their use. Greedy algorithms make locally optimal choices at each step in the hopes of finding a global optimum. They are simple to implement and fast, but may not always reach the true optimal solution. Examples discussed include coin changing, traveling salesman, minimum spanning trees using Kruskal's and Prim's algorithms, and Huffman coding.

More Related Content

What's hot (20)

daa-unit-3-greedy methodhodcsencet

Deadlock ppt Sweetestangel Kochar

Randomized algorithms ver 1.0Dr. C.V. Suresh Babu

The n Queen ProblemSukrit Gupta

02 order of growthHira Gul

OpenMP Tutorial for BeginnersDhanashree Prasad

Ai lecture 7(unit02)vikas dhakane

Backtracking & branch and boundVipul Chauhan

Computability - Tractable, Intractable and Non-computable FunctionReggie Niccolo Santos

DeadlockRajandeep Gill

Answers computer networks 159334 assignment_2_2010Lakshmi Gupta

Bruteforce algorithmRezwan Siam

Critical section problem in operating system.MOHIT DADU

AI - Local Search - Hill ClimbingAndrew Ferlitsch

State space searchchauhankapil

Lecture 24 iterative improvement algorithmHema Kashyap

Intermediate code generation (Compiler Design) Tasif Tanzim

Page replacement algorithmssangrampatil81

Single source Shortest path algorithm with exampleVINITACHAUHAN21

AI Lecture 3 (solving problems by searching)Tajim Md. Niamat Ullah Akhund

daa-unit-3-greedy methodhodcsencet

Deadlock ppt Sweetestangel Kochar

Randomized algorithms ver 1.0Dr. C.V. Suresh Babu

The n Queen ProblemSukrit Gupta

02 order of growthHira Gul

OpenMP Tutorial for BeginnersDhanashree Prasad

Ai lecture 7(unit02)vikas dhakane

Backtracking & branch and boundVipul Chauhan

Computability - Tractable, Intractable and Non-computable FunctionReggie Niccolo Santos

DeadlockRajandeep Gill

Answers computer networks 159334 assignment_2_2010Lakshmi Gupta

Bruteforce algorithmRezwan Siam

Critical section problem in operating system.MOHIT DADU

AI - Local Search - Hill ClimbingAndrew Ferlitsch

State space searchchauhankapil

Lecture 24 iterative improvement algorithmHema Kashyap

Intermediate code generation (Compiler Design) Tasif Tanzim

Page replacement algorithmssangrampatil81

Single source Shortest path algorithm with exampleVINITACHAUHAN21

AI Lecture 3 (solving problems by searching)Tajim Md. Niamat Ullah Akhund

Viewers also liked (20)

Knapsack ProblemJenny Galino

Greedy AlgorihmMuhammad Amjad Rana

Greedy algorithmCaisar Oentoro

Greedy algorithms make locally optimal choices at each step to try to find a global optimum. They choose the best option available at each state. For the travelling salesman problem, the greedy approach is to always choose the nearest unvisited city from the current city to build the route. While greedy algorithms are simple to implement, they do not always find the true optimal solution, especially for large complex problems, as they only consider the best choice at each step rather than the overall route.

LCS ProblemHoang Nguyen

Longest Common SubsequenceSwati Swati

The document discusses the longest common subsequence (LCS) problem and how to solve it using dynamic programming. It begins by defining LCS as the longest sequence of characters that appear left-to-right in two given strings. It then describes solving LCS using a brute force method with exponential time complexity and using dynamic programming with polynomial time complexity. Finally, it provides an example of finding the LCS of two strings and discusses applications and references.

Activity selection problemSumita Das

The document describes an activity selection problem where a set of activities must share a single resource. Each activity has a start and finish time, and activities are mutually compatible if one activity finishes before another starts. The problem is to find the maximum subset of mutually compatible activities. A recursive greedy algorithm is presented that takes the activities sorted by finish time and recursively selects the next compatible activity to build the subset. Pseudocode for the algorithm is provided and stepped through on a sample activity set to produce the optimal subset.

lecture 24sajinsc

The document discusses dynamic programming and its application to solving the longest common subsequence (LCS) problem. It presents the LCS algorithm, which uses dynamic programming to find the length and sequence of the longest subsequence common to two strings X and Y in O(mn) time, where m and n are the lengths of X and Y, respectively. It provides an example running the LCS algorithm on strings X="ABCB" and Y="BDCAB" to determine their longest common subsequence is "BCB".

Longest common subsequence lcsShahariar Rabby

Activity selection problem class 12Kumar

The activity selection problem involves scheduling a shared resource among competing activities. Activities have start and finish times, and only one activity can use the resource at a time. A greedy algorithm finds a maximum set of compatible activities by sorting by finish time and sequentially selecting activities that do not overlap in time. The algorithm runs in O(n log n) time to sort activities and Θ(n) time to select activities, for a total runtime of O(n log n).

Activity selection problemQAU ISLAMABAD,PAKISTAN

A greedy algorithm is a problem-solving technique that follows the problem-solving heuristic of making locally optimal choices at each step to find a global optimum. While this may find an optimal solution, it does not guarantee to do so as it does not consider the overall problem. The document discusses applying a greedy algorithm to solve the activity selection problem by always selecting the next activity that finishes earliest without conflicting with previously selected activities. It provides recursive and iterative implementations of the greedy algorithm to solve this problem in O(n log n) time by first sorting activities by finish time.

Design & Analysis Of AlgorithmComputer Hardware & Trouble shooting

Dynamic programming class 16Kumar

Dynamic programming is an algorithm design technique that solves problems by breaking them down into smaller overlapping subproblems and storing the results of already solved subproblems, rather than recomputing them. It is applicable to problems exhibiting optimal substructure and overlapping subproblems. The key steps are to define the optimal substructure, recursively define the optimal solution value, compute values bottom-up, and optionally reconstruct the optimal solution. Common examples that can be solved with dynamic programming include knapsack, shortest paths, matrix chain multiplication, and longest common subsequence.

Dynamic Programming - Matrix Chain MultiplicationPecha Inc.

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. Matrix chain multiplication is an example where a chain of matrices can be multiplied together in different orders, and dynamic programming can be used to find the most efficient order that minimizes the number of scalar multiplications needed. The algorithm works by defining the problem recursively as calculating the minimum number of multiplications needed to multiply matrices Mi to Mj for all relevant ranges of i and j, filling a table with these values before returning the overall optimal solution.

Greedy AlgorithmWaqar Akram

This document provides an introduction to greedy algorithms. It defines greedy algorithms as algorithms that make locally optimal choices at each step in the hope of finding a global optimum. The document then provides examples of problems that can be solved using greedy algorithms, including counting money, scheduling jobs, finding minimum spanning trees, and the traveling salesman problem. It also provides pseudocode for a general greedy algorithm and discusses some properties of greedy algorithms.

GreedymethodMeenakshi Devi

The document discusses greedy algorithms, their characteristics, and an example problem. Greedy algorithms make locally optimal choices at each step in the hope of finding a global optimum. They are simpler and faster than dynamic programming but may not always find the true optimal solution. The coin changing problem is used to illustrate a greedy approach of always selecting the largest valid coin denomination at each step.

Greedykoralverma

The document discusses the greedy method algorithm design paradigm. It can be used to solve optimization problems with the greedy-choice property, where choosing locally optimal decisions at each step leads to a globally optimal solution. Examples discussed include fractional knapsack problem, task scheduling, and making change problem. The greedy algorithm works by always making the choice that looks best at the moment, without considering future implications of that choice.

Dynamic programmingShakil Ahmed

The document discusses dynamic programming and provides examples of problems that can be solved using dynamic programming including unidirectional traveling salesman problem, coin change, longest common subsequence, and longest increasing subsequence. Source code is presented for solving these problems using dynamic programming including dynamic programming tables, tracing optimal solutions, and time complexity analysis. Various online judges are listed that contain sample problems relating to these dynamic programming techniques.

Back tracking and branch and bound class 20Kumar

Backtracking and branch and bound are algorithms used to solve problems with large search spaces. Backtracking uses depth-first search and prunes subtrees that don't lead to viable solutions. Branch and bound uses breadth-first search and pruning, maintaining partial solutions in a priority queue. Both techniques systematically eliminate possibilities to find optimal solutions faster than exhaustive search. Examples where they can be applied include maze pathfinding, the eight queens problem, sudoku, and the traveling salesman problem.

Longest Common Subsequence (LCS) AlgorithmDarshit Metaliya

Greedy AlgorithmsAmrinder Arora

Knapsack ProblemJenny Galino

Greedy AlgorihmMuhammad Amjad Rana

Greedy algorithmCaisar Oentoro

LCS ProblemHoang Nguyen

Longest Common SubsequenceSwati Swati

Activity selection problemSumita Das

lecture 24sajinsc

Longest common subsequence lcsShahariar Rabby

Activity selection problem class 12Kumar

Activity selection problemQAU ISLAMABAD,PAKISTAN

Design & Analysis Of AlgorithmComputer Hardware & Trouble shooting

Dynamic programming class 16Kumar

Dynamic Programming - Matrix Chain MultiplicationPecha Inc.

Greedy AlgorithmWaqar Akram

GreedymethodMeenakshi Devi

Greedykoralverma

Dynamic programmingShakil Ahmed

Back tracking and branch and bound class 20Kumar

Longest Common Subsequence (LCS) AlgorithmDarshit Metaliya

Greedy AlgorithmsAmrinder Arora

Similar to Greedy method class 11 (20)

Greedy algorithmCHANDAN KUMAR

Lec07-Greedy Algorithms.pdf Lec07-Greedy Algorithms.pdfMAJDABDALLAH3

This document provides an outline for a course on algorithms and analysis of algorithms. It discusses greedy algorithms as one topic that will be covered in the course. Greedy algorithms make locally optimal choices at each step in the hope of finding a globally optimal solution. The document provides examples of problems that can be solved using greedy algorithms, such as coin changing, fractional knapsack, and minimum spanning trees. Common greedy algorithms like Kruskal's algorithm and Prim's algorithm are described for finding minimum spanning trees in graphs.

Daa chapter4B.Kirron Reddi

The document discusses greedy algorithms and matroids. It provides examples of problems that can be solved using greedy approaches, including sorting an array, the coin change problem, and activity selection. It defines key aspects of greedy algorithms like the greedy choice property and optimal substructure. Huffman coding is presented as an application that constructs optimal prefix codes. Finally, it introduces matroids as an abstract structure related to problems solvable by greedy methods.

7. Algorithm Design and analysis ppt.pptxdeivasigamani9

GreedymethodBansari Shah

Bansari Shah's document discusses greedy algorithms. It defines greedy algorithms as making locally optimal choices at each step to find a global optimum. The document outlines the characteristics, optimization problems, pseudo-code for greedy algorithms, and provides an example of Prim's algorithm. It also compares greedy algorithms to dynamic programming and discusses pros and cons, such as greedy algorithms being faster but not always reaching the global optimum.

Greedy method by Dr. B. J. MohiteZeal Education Society, Pune

The document describes the greedy method algorithm design technique. It works in steps, selecting the best available option at each step until all options are exhausted. Many problems can be formulated as finding a feasible subset that optimizes an objective function. A greedy algorithm works in stages, making locally optimal choices at each stage to arrive at a global optimal solution. Several examples are provided to illustrate greedy algorithms for problems like change making, machine scheduling, container loading, knapsack problem, job sequencing with deadlines, and single-source shortest paths. Pseudocode is given for some of the greedy algorithms.

Greedy algorithms -Making change-Knapsack-Prim's-Kruskal'sJay Patel

The document discusses greedy algorithms, which attempt to find optimal solutions to optimization problems by making locally optimal choices at each step that are also globally optimal. It provides examples of problems that greedy algorithms can solve optimally, such as minimum spanning trees and change making, as well as problems they can provide approximations for, like the knapsack problem. Specific greedy algorithms covered include Kruskal's and Prim's for minimum spanning trees.

Greedy with Task Scheduling Algorithm.pptRuchika Sinha

Greedy technique.mohanrathod18

The greedy technique constructs solutions to problems in a step-by-step manner, choosing the best local option at each step to arrive at a complete solution. It aims to find a feasible solution that satisfies all constraints and also provides an optimal solution with minimum cost. The algorithm selects the best option from the available choices at each step until a full solution is reached. For example, in traveling from city A to B, the greedy approach may select taking a train then plane to arrive within a 10 hour time constraint, providing a feasible and optimal solution.

Unit 3- Greedy Method.pptxMaryJacob24

The document discusses various greedy algorithms including knapsack problems, minimum spanning trees, shortest path algorithms, and job sequencing. It provides descriptions of greedy algorithms, examples to illustrate how they work, and pseudocode for algorithms like fractional knapsack, Prim's, Kruskal's, Dijkstra's, and job sequencing. Key aspects covered include choosing the best option at each step and building up an optimal solution incrementally using greedy choices.

Greedy Method unit-2(Design and analysis of algorithms).pptxshivani366010

Unit 3 - Greedy MethodMaryJacob24

Unit 3 greedy methodMaryJacob24

Module 3_DAA (2).pptxAnkitaVerma776806

The document discusses greedy algorithms and provides examples of how they can be applied to solve optimization problems like the knapsack problem. It defines greedy techniques as making locally optimal choices at each step to arrive at a global solution. Examples where greedy algorithms are used include finding the shortest path, minimum spanning tree (using Prim's and Kruskal's algorithms), job sequencing with deadlines, and the fractional knapsack problem. Pseudocode and examples are provided to demonstrate how greedy algorithms work for the knapsack problem and job sequencing problem.

Greedy algorithmsMd. Shafiuzzaman Hira

This document discusses greedy algorithms and provides an example of the activity selection problem. It can be summarized as: 1. Greedy algorithms make locally optimal choices at each step in the hope that it will lead to a globally optimal solution. They are easier to code but do not always produce an optimal solution. 2. The activity selection problem involves scheduling a maximum number of non-overlapping activities given their start and finish times. The greedy algorithm selects the activity with the earliest finish time at each step. 3. For a problem to be solvable by a greedy approach, it must exhibit the greedy-choice property and optimal substructures - where optimal solutions to sub-problems are contained within an optimal solution to the

Data structure notesanujab5

The greedy method constructs an optimal solution in stages by making locally optimal choices at each stage without reconsidering past decisions. It selects the choice that appears best at the current time without regard for its long-term consequences. The general greedy algorithm procedure selects the best choice from available inputs at each stage until a complete solution is reached. Examples demonstrate both when the greedy method succeeds in finding an optimal solution and when it fails to do so compared to alternative methods like dynamic programming.

Greedy Algorithms WITH Activity Selection Problem.pptRuchika Sinha

5.1 greedyyy 02Krish_ver2

The document discusses greedy algorithms and provides examples of problems that can be solved using greedy techniques. It introduces the coin changing problem and activity selection problem. For activity selection, it demonstrates that a greedy approach of always selecting the activity with the earliest finish time results in an optimal solution. It provides pseudo-code for a greedy algorithm and proves that the greedy solution is optimal for the activity selection problem by showing there is always an optimal solution that makes the greedy choice and combining the greedy choice with the optimal solution to the remaining subproblem yields an optimal solution to the original problem.

Greedy Algorithms project presentation ppt.pptxParasBhoite1

Greedy algorithmCHANDAN KUMAR

Lec07-Greedy Algorithms.pdf Lec07-Greedy Algorithms.pdfMAJDABDALLAH3

Daa chapter4B.Kirron Reddi

7. Algorithm Design and analysis ppt.pptxdeivasigamani9

GreedymethodBansari Shah

Greedy method by Dr. B. J. MohiteZeal Education Society, Pune

Greedy algorithms -Making change-Knapsack-Prim's-Kruskal'sJay Patel

Greedy with Task Scheduling Algorithm.pptRuchika Sinha

Greedy technique.mohanrathod18

Unit 3- Greedy Method.pptxMaryJacob24

Greedy Method unit-2(Design and analysis of algorithms).pptxshivani366010

Unit 3 - Greedy MethodMaryJacob24

Unit 3 greedy methodMaryJacob24

Module 3_DAA (2).pptxAnkitaVerma776806

Greedy algorithmsMd. Shafiuzzaman Hira

Data structure notesanujab5

Greedy Algorithms WITH Activity Selection Problem.pptRuchika Sinha

5.1 greedyyy 02Krish_ver2

Greedy Algorithms project presentation ppt.pptxParasBhoite1

More from Kumar (20)

Graphics devicesKumar

This document discusses graphics hardware components. It describes various graphics input devices like the mouse, joystick, light pen etc. and how they are either analog or digital. It then covers common graphics output devices such as CRT displays, plasma displays, LCDs and 3D viewing systems. It provides details on the internal components and working of CRT displays. It also discusses graphics storage formats and the architecture of raster and random graphics systems.

Fill area algorithmsKumar

The document describes different algorithms for filling polygon and area shapes, including scanline fill, boundary fill, and flood fill algorithms. The scanline fill algorithm works by determining intersections of boundaries with scanlines and filling color between intersections. Boundary fill works by starting from an interior point and recursively "painting" neighboring points until the boundary is reached. Flood fill replaces a specified interior color. Both can be 4-connected or 8-connected. The document also discusses problems that can occur and more efficient span-based approaches.

region-fillingKumar

This document discusses techniques for filling 2D shapes and regions in raster graphics. It covers seed fill algorithms that start with an interior seed point and grow outward, filling neighboring pixels. Boundary fill and flood fill are described as variations. The document also discusses raster-based filling that processes shapes one scanline at a time. Methods for filling polygons are presented, including using the even-odd rule or winding number rule to determine if a point is inside the polygon boundary.

Bresenham derivationKumar

The document derives Bresenham's line algorithm for drawing lines on a discrete grid. It starts with the line equation and defines variables for the slope and intercept. It then calculates the distance d1 and d2 from the line to two possible pixel locations and expresses their difference in terms of the slope and intercept. By multiplying this difference by the change in x, it removes the floating point slope value, resulting in an integer comparison expression. This is defined recursively to draw each subsequent pixel, using pre-computed constants. The initial p0 value is also derived from the line endpoint coordinates.

Bresenham circles and polygons dericationKumar

The document discusses algorithms for drawing lines and circles on a discrete pixel display. It begins by describing what characteristics an "ideal line" would have on such a display. It then introduces several algorithms for drawing lines, including the simple line algorithm, digital differential analyzer (DDA) algorithm, and Bresenham's line algorithm. The Bresenham algorithm is described in detail, as it uses only integer calculations. Next, a simple potential circle drawing algorithm is presented and its shortcomings discussed. Finally, the more accurate and efficient mid-point circle algorithm is described. This algorithm exploits the eight-way symmetry of circles and uses incremental calculations to determine the next pixel point.

Introductionto xsltKumar

The document provides an introduction to XSLT (Extensible Stylesheet Language Transformations), including: 1) It discusses XSLT basics like using templates to extract values from XML and output them, using for-each loops to process multiple elements, and if/choose for decisions. 2) It covers XPath for addressing parts of an XML document, and functions like contains() and position(). 3) The document gives examples of transforming sample XML data using XSLT templates, value-of, and apply-templates.

Extracting data from xmlKumar

XML documents can be represented and stored in memory as tree structures using models like DOM and XDM. XPath is an expression language used to navigate and select parts of an XML tree. It allows traversing elements and their attributes, filtering nodes by properties or position, and evaluating paths relative to a context node. While XPath expressions cannot modify the document, they are commonly used with languages like XSLT and XQuery which can transform or extract data from XML trees.

Xml basicsKumar

This document provides an overview of XML programming and XML documents. It discusses the physical and logical views of an XML document, document structure including the root element, and how XML documents are commonly stored as text files. It also summarizes how an XML parser reads and validates an XML document by checking its syntax and structure. The document then covers various XML components in more detail, such as elements, attributes, character encoding, entities, processing instructions, well-formedness, validation via DTDs, and document modeling.

XML SchemaKumar

XML Schema provides a way to formally define and validate the structure and content of XML documents. It allows defining elements, attributes, and data types, as well as restrictions like length, pattern, and value ranges. DTD is more limited and cannot validate data types. XML Schema is written in XML syntax, uses XML namespaces, and provides stronger typing capabilities compared to DTD. It allows defining simple and complex element types, attributes, and restrictions to precisely describe the expected structure and values within XML documents.

Publishing xmlKumar

This document discusses style sheet languages like CSS that are used to control the presentation of XML documents. CSS allows one to specify things like fonts, colors, spacing etc. for different elements in an XML file. A single XML file can then be formatted in multiple ways just by changing the associated CSS stylesheet without modifying the XML content. The document provides examples of using CSS selectors, rules and properties to style elements in an XML file and controlling presentation aspects like layout of elements on a page. It also discusses how to link the CSS stylesheet to an XML file using processing instructions.

DTDKumar

An attribute declaration specifies attributes for elements in a DTD. It defines the attribute name, data type or permissible values, and required behavior. For example, an attribute may have a default value if not provided, be optional, or require a value. Notations can label non-XML data types and unparsed entities can import binary files. Together DTDs and entities provide a schema to describe document structure and relationships.

Applying xmlKumar

This document discusses XML web services and their components. It defines XML web services as software services exposed on the web through the SOAP protocol and described with WSDL and registered in UDDI. It describes how SOAP is used for communication, WSDL describes service interfaces, and UDDI allows for service discovery. Examples of web services are provided. The architecture of web services is shown involving clients, services, and standards. Finally, it discusses how XML data can be transformed to HTML for display in web pages using XSLT transformation rules.

Introduction to XMLKumar

This document provides an introduction and overview of XML. It explains that XML stands for Extensible Markup Language and is used for data transportation and storage in a platform and language neutral way. XML plays an important role in data exchange on the web. The document discusses the history of XML and how it was developed as an improvement over SGML and HTML by allowing users to define their own tags to structure data for storage and interchange. It also provides details on the pros and cons of XML compared to other markup languages.

How to deploy a j2ee applicationKumar

This document provides instructions for packaging and deploying a J2EE application that was developed in IBM Rational Application Developer. It describes resetting the database to its original state, exporting the application as an EAR file, using the WebSphere administrative console to install the EAR file on the application server, and testing the application in a web browser. The goal is to simulate taking an application developed in a development environment and deploying it to a production server.

JNDI, JMS, JPA, XMLKumar

This document provides an overview of key Java enterprise technologies including JNDI, JMS, JPA and XML. It discusses the architecture and usage of JNDI for accessing naming and directory services. It also covers the point-to-point and publish/subscribe messaging models of JMS, the core JMS programming elements like connection factories, connections and destinations, and how applications use these elements to send and receive messages. Finally, it briefly introduces JPA for object-relational mapping and the role of XML.

EJB FundmentalsKumar

The document discusses the benefits of using Enterprise JavaBeans (EJBs) for developing Java EE applications. It explains that EJBs provide infrastructure for developing and deploying mission-critical, enterprise applications by handling common tasks like database connectivity and transaction management. The three types of EJBs - session, entity, and message-driven beans - are described as well as how they are contained in EJB containers.

JSP and struts programmingKumar

java servlet and servlet programmingKumar

This document provides lecture notes on servlet programming. It covers topics like the introduction to servlets, GET and POST methods, the lifecycle of a servlet, servlet interfaces like Servlet, GenericServlet and HttpServlet. It also discusses request dispatching in servlets, session management techniques and servlet filters. Code examples are provided to demonstrate servlet implementation and request dispatching.

Introduction to JDBC and JDBC DriversKumar

The document discusses Java Database Connectivity (JDBC) and provides details about its core components and usage. It covers: 1) The four core components of JDBC - drivers, connections, statements, and result sets. 2) The four types of JDBC drivers and examples of each. 3) How to use JDBC to connect to a database, execute queries using statements, iterate through result sets, and update data. Prepared statements are also discussed.

Introduction to J2EEKumar

The document is a set of lecture notes on Enterprise Java from January to June 2014 prepared by Mr. Hitesh Kumar Sharma and Mr. Ravi Tomar. It covers core J2EE technologies, enterprise application architectures like 2-tier, 3-tier and n-tier, advantages and disadvantages of architectures, J2EE application servers, web containers and EJB containers. The notes are to be submitted by B.Tech CS VI semester students specializing in MFT, O&G, OSS and CCVT.

Graphics devicesKumar

Fill area algorithmsKumar

region-fillingKumar

Bresenham derivationKumar

Bresenham circles and polygons dericationKumar

Introductionto xsltKumar

Extracting data from xmlKumar

Xml basicsKumar

XML SchemaKumar

Publishing xmlKumar

DTDKumar

Applying xmlKumar

Introduction to XMLKumar

How to deploy a j2ee applicationKumar

JNDI, JMS, JPA, XMLKumar

EJB FundmentalsKumar

JSP and struts programmingKumar

java servlet and servlet programmingKumar

Introduction to JDBC and JDBC DriversKumar

Introduction to J2EEKumar

Recently uploaded (20)

YSPH VMOC Special Report - Measles Outbreak Southwest US 5-14-2025 .pptxYale School of Public Health - The Virtual Medical Operations Center (VMOC)

As of 5/14/25, the Southwestern outbreak has 860 cases, including confirmed and pending cases across Texas, New Mexico, Oklahoma, and Kansas. Experts warn this is likely a severe undercount. The situation remains fluid, with case numbers expected to rise. Experts project the outbreak could last up to a year. CURRENT CASE COUNT: 860 (As of 5/14/2025) Texas: 718 (+6) (62% of cases are in Gaines County) New Mexico: 71 (92.4% of cases are from Lea County) Oklahoma: 17 Kansas: 54 (+6) (38.89% of the cases are from Gray County) HOSPITALIZATIONS: 102 (+2) Texas: 93 (+1) - This accounts for 13% of all cases in Texas. New Mexico: 7 – This accounts for 9.86% of all cases in New Mexico. Kansas: 2 (+1) - This accounts for 3.7% of all cases in Kansas. DEATHS: 3 Texas: 2 – This is 0.28% of all cases New Mexico: 1 – This is 1.41% of all cases US NATIONAL CASE COUNT: 1,033 (Confirmed and suspected) INTERNATIONAL SPREAD (As of 5/14/2025) Mexico: 1,220 (+155) Chihuahua, Mexico: 1,192 (+151) cases, 1 fatality Canada: 1,960 (+93) (Includes Ontario’s outbreak, which began November 2024) Ontario, Canada – 1,440 cases, 101 hospitalizations

Peer Assessment_ Unit 2 Skills Development for Live Performance - for Libby.docx19lburrell

Letter to Secretary Linda McMahon from U.S. SenatorsMebane Rash

Antepartum fetal surveillance---Dr. H.K.Cheema pdf.pdfDr H.K. Cheema

The History of Kashmir Lohar Dynasty NEP.pptArya Mahila P. G. College, Banaras Hindu University, Varanasi, India.

This presentation has been made keeping in mind the students of undergraduate and postgraduate level. To keep the facts in a natural form and to display the material in more detail, the help of various books, websites and online medium has been taken. Whatever medium the material or facts have been taken from, an attempt has been made by the presenter to give their reference at the end. The Lohar dynasty of Kashmir is a new chapter in the history of ancient India. We get to see an ancient example of a woman ruling a dynasty in the Lohar dynasty.

PUBH1000 Slides - Module 12: Advocacy for HealthJonathanHallett4

Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...parmarjuli1412

Dastur_ul_Amal under Jahangir Key Features.pptxomorfaruqkazi

Dastur_ul_Amal under Jahangir Key Features The Dastur-ul-Amal (or Dasturu’l Amal) of Emperor Jahangir is a key administrative document from the Mughal period, particularly relevant during Jahangir’s reign (1605–1627). The term "Dastur-ul-Amal" broadly translates to "manual of procedures" or "regulations for administration", and in Jahangir’s context, it refers to his set of governance principles, administrative norms, and regulations for court officials and provincial administration.

ITI COPA Question Paper PDF 2017 Theory MCQSONU HEETSON

materi 3D Augmented Reality dengan assemblrfatikhatunnajikhah1

Conditions for Boltzmann Law – Biophysics Lecture SlidePKLI-Institute of Nursing and Allied Health Sciences Lahore , Pakistan.

This presentation covers the conditions required for the application of Boltzmann Law, aimed at undergraduate nursing and allied health science students studying Biophysics. It explains the prerequisites for the validity of the law, including assumptions related to thermodynamic equilibrium, distinguishability of particles, and energy state distribution. Ideal for students learning about molecular motion, statistical mechanics, and energy distribution in biological systems.

Search Matching Applicants in Odoo 18 - Odoo SlidesCeline George

MCQ PHYSIOLOGY II (DR. NASIR MUSTAFA) MCQS)Dr. Nasir Mustafa

"Bridging Cultures Through Holiday Cards: 39 Students Celebrate Global Tradit...AlionaBujoreanu

PUBH1000 Slides - Module 11: Governance for HealthJonathanHallett4

EUPHORIA GENERAL QUIZ PRELIMS | QUIZ CLUB OF PSGCAS | 21 MARCH 2025Quiz Club of PSG College of Arts & Science

The Quiz Club of PSGCAS brings to you a battle... Get ready to unleash your inner know-it-all! 🧠💥 We're diving headfirst into a quiz so epic, it makes Mount Everest look like a molehill! From chart-topping pop sensations that defined generations and legendary sports moments that still give us goosebumps, to ancient history that shaped the world and, well, literally EVERYTHING in between! Prepare for a whirlwind tour of trivia that will stretch your brain cells to their absolute limits and crown the ultimate quiz champion. This isn't just a quiz; it's a battle of wits, a test of trivia titans! Are you ready to conquer it all? QM: VIKASHINI G THE QUIZ CLUB OF PSGCAS(2022-25)

PUBH1000 Slides - Module 10: Health PromotionJonathanHallett4

How to Change Sequence Number in Odoo 18 Sale OrderCeline George

LDMMIA 2024 Crystal Gold Lecture 1 BonusLDM & Mia eStudios

LDMMIA: 2024 Crystal Gold Lecture 1 (L1). A Bonus Workshop Lesson. We also have a Fam Bday. My Next Session (7) is late. Make sure to catch our new series. The last one was Money Part 2. ♥LDMMIA & Depts: are fusing the fan clubs so do welcome. Welcome all fan groups and visitors. We are timeless and a safe haven / Cyber Space. That’s the design of our Fan/Reader/Loyal Blog. I hope to continue that rule for all fan groups. You are loved / appreciated always.♥ LDMMIA CORP, LDM YOGA BRAND PRESENTS ‘SEXY YOGA’ Studio Media/Artist: Yogi Goddess TEACHER: REV LEZ MICHELLE, YOGA ND, REIKI MASTER, & (Decades) METAPHYSICIAN This is both LDM Yoga brand with Yogi Goddess. No grades, No Signups needed. This is a Public vs Private Class attendance. No communications Needed. All students have privacy. Theres no reporting in, uncomfortable introductions to the public.

Launch of The State of Global Teenage Career Preparation - Andreas Schleicher...EduSkills OECD

YSPH VMOC Special Report - Measles Outbreak Southwest US 5-14-2025 .pptxYale School of Public Health - The Virtual Medical Operations Center (VMOC)

Peer Assessment_ Unit 2 Skills Development for Live Performance - for Libby.docx19lburrell

Letter to Secretary Linda McMahon from U.S. SenatorsMebane Rash

Antepartum fetal surveillance---Dr. H.K.Cheema pdf.pdfDr H.K. Cheema

The History of Kashmir Lohar Dynasty NEP.pptArya Mahila P. G. College, Banaras Hindu University, Varanasi, India.

PUBH1000 Slides - Module 12: Advocacy for HealthJonathanHallett4

Mental Health Assessment in 5th semester bsc. nursing and also used in 2nd ye...parmarjuli1412

Dastur_ul_Amal under Jahangir Key Features.pptxomorfaruqkazi

ITI COPA Question Paper PDF 2017 Theory MCQSONU HEETSON

materi 3D Augmented Reality dengan assemblrfatikhatunnajikhah1

Conditions for Boltzmann Law – Biophysics Lecture SlidePKLI-Institute of Nursing and Allied Health Sciences Lahore , Pakistan.

Search Matching Applicants in Odoo 18 - Odoo SlidesCeline George

MCQ PHYSIOLOGY II (DR. NASIR MUSTAFA) MCQS)Dr. Nasir Mustafa

"Bridging Cultures Through Holiday Cards: 39 Students Celebrate Global Tradit...AlionaBujoreanu

PUBH1000 Slides - Module 11: Governance for HealthJonathanHallett4

EUPHORIA GENERAL QUIZ PRELIMS | QUIZ CLUB OF PSGCAS | 21 MARCH 2025Quiz Club of PSG College of Arts & Science

PUBH1000 Slides - Module 10: Health PromotionJonathanHallett4

How to Change Sequence Number in Odoo 18 Sale OrderCeline George

LDMMIA 2024 Crystal Gold Lecture 1 BonusLDM & Mia eStudios

Launch of The State of Global Teenage Career Preparation - Andreas Schleicher...EduSkills OECD

Greedy method class 11

1. Greedy Method

2. Basic Idea • • • Construct a solution to an optimization problem piece by piece through a sequence of choices that are: • feasible • locally optimal • Irrevocable For some problems, they yield an optimal solution for every instance. For most, they don’t, but can be useful for fast approximations. 2

3. Greedy Method • Most straight forward design technique. • Usually progresses in a top-down fashion. • Solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. • Greedy Method Provides optimal solutions.

4. Feasible and Optimal Solutions • Most of the problems have ‘n’ inputs and require us to obtain a subset that satisfies some constraints. • Any subset that satisfies these constraints is called a feasible solution. • Greedy method finds a feasible solution that either maximizes or minimizes a given objective function. • A feasible solution which meets the objective function is called optimal solution.

5. Greedy Steps • Select some solution from input domain. • Then check the selected solution is feasible or not. • Select the Optimal Solution (solution that satisfies or nearly satisfies the objective function) from set of feasible solutions. • Greedy method works in stages. At each stage only one input is considered at each time. Based on this input it is decided whether particular input gives the optimal solution or not.

6. Greedy Algorithm Greedy(D,n) // In Greedy approach D is a domain // from which solution is to be obtained of size n // Initially assume Solution<-0 for i<-1 to n do{ s<-select(D) //selection of solution from D if(Feasible (Solution , s)) then Solution<-Union(Solution, s) } return Solution

7. Greedy Algorithms are Optimal • The following are the two key ingredients to prove the Greedy Algorithms are optimal. 1. Greedy Choice Property 2. Optimal Substructure

8. Greedy Choice Property • Global optimal solution will be made with local optimal (greedy) choices. • In a greedy algorithm, the best choice will be selected at the moment to solve the sub problem that remains. • The choice of the greedy may depend on the choices so far, but it can’t depend on the future choices or on the solutions to the subproblems.

9. Optimal Substructure • Optimal substructure is a property of Greedy solution. • A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to the subproblems.

10. Procedure to prove the Optimal Greedy Algorithms 1. Consider globally-optimal solution 2. Show greedy choice at first step reduces problem to the same but smaller problem. Greedy Choice must be part of an optimal solution and made first. 3. Use induction to show greedy choice is best at each step i.e., optimal substructure

11. Applications of the Greedy Strategy • Optimal solutions: change making for “normal” coin denominations minimum spanning tree (MST) single-source shortest paths scheduling problems Huffman codes • Approximations: traveling salesman problem (TSP) knapsack problem 11 other combinatorial optimization problems

Greedy method class 11

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to Greedy method class 11 (20)

More from Kumar (20)

Recently uploaded (20)

Greedy method class 11