### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

# Greedy Algorithm

No description

by

Tweet## mohammad alamin

on 25 February 2013#### Transcript of Greedy Algorithm

Let's Start... What is Greedy Algorithm? Elements of greedy algorithm Properties of Greedy A greedy algorithm is an algorithm that, at each step, is presented with choices, these choices are measured and one is determined to be the best and is selected. We can make whatever choice seems best at the moment and then solve the sub problems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the sub problem.

It iteratively makes one greedy choice after another, reducing each given problem into a smaller one.

In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming. GREEDY ALGORITHM It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution 1. A candidate set, from which a solution is created

2. A selection function, which chooses the best candidate to be added to the solution

3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution

4. An objective function, which assigns a value to a solution, or a partial solution, and

5. A solution function, which will indicate when we have discovered a complete solution Optimal Substructure

A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems. How it works? 1.Determine the optimal substructure of the

problem.

2.Develop a recursive solution.

3.Show that if we make the greedy choice, then

only one sub problem remains.

4.Prove that it is always safe to make the

greedy choice.

5.Develop a recursive algorithm that

implements the greedy strategy.

6.Convert the recursive algorithm to an

iterative algorithm. Dijkstra's Algorithm DIJKSTRA(G, w, s)

1. INITIALIZE-SINGLE-SOURCE(G, s)

2. S = Ø

3. Q =V[G]

4. while Q != ≠ Ø

5. u= EXTRACT-MIN(Q)

6. S= S U {u}

7. for each vertex v (belongs to) Adj[u]

8. RELAX(u, v, w) Kruskal's Algorithm MST-KRUSKAL(G, w)

1.A =Ø

2.for each vertex v(belongs to) G.V

3. MAKE-SET(v)

4. sort the edges of G.E into nondecreasing order by weight w

5.for each edge (u, v) E, taken in nondecreasing order by weight

6. if FIND-SET(u) != ≠ FIND-SET(v)

7. A = A U {(u, v)}

8 . UNION(u, v)

9. return A finally it's look like Prim's Algorithm MST-PRIM(G, w, r)

1 for each u (belongs to) G.V

2. u.key[u] = ∞infinity

3. u.πpi= NIL

4. r.key = 0

5. Q = G.V

6. while Q !=≠ Ø

7. u = EXTRACT-MIN(Q)

8. for each v(belongs to) G.Adj[u]

9. if v (belongs to) Q and w(u, v) < v. key

10. v.πpi = u

11. v.key = w(u, v) Example Application on Huffman code : Both the . mp3 & . jpg formats use Huffman Coding at one stage of the compression. This has been done by Jannatul Ferdous Md.Al-Amin Hossain Khandaker Mohiuddin and the Tech Giant

Full transcriptIt iteratively makes one greedy choice after another, reducing each given problem into a smaller one.

In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming. GREEDY ALGORITHM It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution 1. A candidate set, from which a solution is created

2. A selection function, which chooses the best candidate to be added to the solution

3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution

4. An objective function, which assigns a value to a solution, or a partial solution, and

5. A solution function, which will indicate when we have discovered a complete solution Optimal Substructure

A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems. How it works? 1.Determine the optimal substructure of the

problem.

2.Develop a recursive solution.

3.Show that if we make the greedy choice, then

only one sub problem remains.

4.Prove that it is always safe to make the

greedy choice.

5.Develop a recursive algorithm that

implements the greedy strategy.

6.Convert the recursive algorithm to an

iterative algorithm. Dijkstra's Algorithm DIJKSTRA(G, w, s)

1. INITIALIZE-SINGLE-SOURCE(G, s)

2. S = Ø

3. Q =V[G]

4. while Q != ≠ Ø

5. u= EXTRACT-MIN(Q)

6. S= S U {u}

7. for each vertex v (belongs to) Adj[u]

8. RELAX(u, v, w) Kruskal's Algorithm MST-KRUSKAL(G, w)

1.A =Ø

2.for each vertex v(belongs to) G.V

3. MAKE-SET(v)

4. sort the edges of G.E into nondecreasing order by weight w

5.for each edge (u, v) E, taken in nondecreasing order by weight

6. if FIND-SET(u) != ≠ FIND-SET(v)

7. A = A U {(u, v)}

8 . UNION(u, v)

9. return A finally it's look like Prim's Algorithm MST-PRIM(G, w, r)

1 for each u (belongs to) G.V

2. u.key[u] = ∞infinity

3. u.πpi= NIL

4. r.key = 0

5. Q = G.V

6. while Q !=≠ Ø

7. u = EXTRACT-MIN(Q)

8. for each v(belongs to) G.Adj[u]

9. if v (belongs to) Q and w(u, v) < v. key

10. v.πpi = u

11. v.key = w(u, v) Example Application on Huffman code : Both the . mp3 & . jpg formats use Huffman Coding at one stage of the compression. This has been done by Jannatul Ferdous Md.Al-Amin Hossain Khandaker Mohiuddin and the Tech Giant