Greedy Algorithm

A greedy algorithm always makes the choice that looks best at that moment.
Greedy Algorithm works on following property:-
1)Greedy choice property:-It makes locally optimal choice in the hope that this choice to lead to globally optimal solution.
2)Optimal substructure:-Optimal solution contain optimal sub solution. 

Optimal Merge Pattern (Huffman Coding)

    OptimalMergePattern (int A[],int n)
    {
        initialize a priority queue, PQ, to contain n element in A;
        Struct binary tree node*temp;
        for(i=1 ; i<n ; i++)
         {
            temp = (struct*) malloc (size of (binary tree node));
            temp ---> left = Delete_min (PQ);
            temp ---> right = Delete_mn (PQ);
            temp ---> data = (temp ---> left ---> data) + (temp ---> right ---> data);
            insert temp to P;
          }
         return PQ;
      } 

Time complexity : O(n log n)
The number of bits per message = ∑ (frequency of external node 'i')x (Number of bits required for qi)
Weigthed external path length = ∑ qi di (di = distance from root to external nodes 'i')

Fractional Knapsack Problem

   for(i = 1 ; i =< n ; i++)
        a[i] = pi/wi
    Arrange array in ascending order
   Take one ny one object from a and keep in knapsack untill knapsack becomes full.
   Time complexity = O(n log n) + O(n) = O(n log n) 




Job Sequencing  with Deadline

   Sort the given list of n jobs in ascending order of profits.
   Find maximum deadline in the given array of n-deadlines and takes that array of maximum deadlines size.
  For every slot i apply linear search to find a job which repeat this step for every slot.
   Time complexity = O(n²)

Minimum Cost Spanning Trees

    Kruskal's algorithm : O(e log e)
           with heap = O( e log e)
   It starts with edge (min cost edge) and intermediate may results either tree or forest.
   Prim's algorithm : O(n²)
            With heap = O(e log e)
             With fibonacci heap = O(e + log n)
   It starts with vertex (min cost vertex) and intermediate results i "tree".
   Optimal Randomized Algorithm (Minimum weight spanning tree):[O(n + e)]

Single Source Shortest Path (Dijkstra's Algorithm) 

 Time complexity : O((V + E) log V) using binary min heap and using Fibonacci heap: O(E + VlogV)
 Drawback of Dijkstra's Algorithm:It will not give shortest path for some vertices if graph contain negative weight cycle.

Bellmann Ford Algorithm

It finds shortest  path from source to every vertex , it the graph doesn't contain negative weight cycle.
If graph contain negative weight cycle,it don't compute shortest path from source to all other vertices but it will report saying "negative weight cycle exist".
 Time complexity = O (VE)
                                 O(V³) ; for dense graph

                                  O(V²) ; for sparse graph