Week 5 Discussion Forum

Greedy Algorithms

Greedy Algorithms

by Jannatul Anjum Shafa 192-15-2787 -
Number of replies: 0

 Greedy algorithm works if a problem exhibits the following two properties:

  1. Greedy Choice Property: A globally optimal solution can be reached at by creating a locally optimal solution. In other words, an optimal solution can be obtained by creating "greedy" choices.
  2. Optimal substructure: Optimal solutions contain optimal sub-solutions. In other words, answers to sub-problems of an optimal solution are optimal.

Example:

  1. Machine scheduling
  2. Fractional Knapsack Problem
  3. Minimum Spanning Tree
  4. Huffman Code
  5. Job Sequencing
  6. Activity Selection Problem

71 words