Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    Greedy Algorithm: Dynamic Programming Kruskal's Minimum Spanning Trees Dijkstra's

    Uploaded by

    manish_chawla_12
    Greedy algorithms make locally optimal choices at each step to find a global optimum. This document discusses greedy algorithms for finding minimum spanning trees using Kruskal's and Prim's algorithms, single-source shortest paths using Dijkstra's algorithm, and optimal Huffman trees. Huffman encoding is a greedy algorithm that always combines the two smallest numbers to construct the optimal encoding tree. Minimum spanning tree algorithms like Kruskal's work greedily by repeatedly adding the lowest cost edge connecting nodes not yet in the partial spanning tree.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Greedy Algorithm: Dynamic Programming Kruskal's Minimum Spanning Trees Dijkstra's

    Uploaded by

    manish_chawla_12
    18 views6 pages
    Greedy algorithms make locally optimal choices at each step to find a global optimum. This document discusses greedy algorithms for finding minimum spanning trees using Kruskal's and Prim's algorithms, single-source shortest paths using Dijkstra's algorithm, and optimal Huffman trees. Huffman encoding is a greedy algorithm that always combines the two smallest numbers to construct the optimal encoding tree. Minimum spanning tree algorithms like Kruskal's work greedily by repeatedly adding the lowest cost edge connecting nodes not yet in the partial spanning tree.

    Original Description:

    Greedy Algorithm

    Original Title

    Greedy Algorithm

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Greedy algorithms make locally optimal choices at each step to find a global optimum. This document discusses greedy algorithms for finding minimum spanning trees using Kruskal's and Prim's algorithms, single-source shortest paths using Dijkstra's algorithm, and optimal Huffman trees. Huffman encoding is a greedy algorithm that always combines the two smallest numbers to construct the optimal encoding tree. Minimum spanning tree algorithms like Kruskal's work greedily by repeatedly adding the lowest cost edge connecting nodes not yet in the partial spanning tree.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    18 views6 pages

    Greedy Algorithm: Dynamic Programming Kruskal's Minimum Spanning Trees Dijkstra's

    Uploaded by

    manish_chawla_12
    Greedy algorithms make locally optimal choices at each step to find a global optimum. This document discusses greedy algorithms for finding minimum spanning trees using Kruskal's and Prim's algorithms, single-source shortest paths using Dijkstra's algorithm, and optimal Huffman trees. Huffman encoding is a greedy algorithm that always combines the two smallest numbers to construct the optimal encoding tree. Minimum spanning tree algorithms like Kruskal's work greedily by repeatedly adding the lowest cost edge connecting nodes not yet in the partial spanning tree.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 6

    GREEDY ALGORITHM

    A greedy algorithm can be proven to yield the


    global optimum for a given problem class,
    it typically becomes the method of choice
    because it is faster than other optimisation
    methods like dynamic programming.
    Examples of such greedy algorithms are
    Kruskal's algorithm and Prim's algorithm for
    finding minimum spanning trees, Dijkstra's
    algorithm for finding single-source shortest
    paths, and the algorithm for finding optimum
    Huffman trees.

    HUFFMAN ENCODING
    The Huffman encoding algorithm is a
    greedy algorithm
    You always pick the two smallest numbers
    to combine

    The Huffman algorithm finds


    an optimal solution

    MINIMUM SPANNING TREE


    A minimum spanning tree is a least-cost subset of
    the edges of a graph that connects all the nodes
    Start by picking any node and adding it to the tree
    Repeatedly: Pick any least-cost edge from a node in the tree to
    a node not in the tree, and add the edge and new node to the
    tree
    Stop when all nodes have been added to the tree

    You might also like