Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Greedy Algorithm

No description
by

mohammad alamin

on 25 February 2013

Comments (0)

Please log in to add your comment.

Report abuse

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 transcript