Week 5 Discussion Forum

Greedy Algorithm Introduction

Greedy Algorithm Introduction

by Md. Sabbir Hossain 192-15-2809 -
Number of replies: 0

A 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 subsolutions. In other words, answers to subproblems 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

72 words