Greedy Algorithms

Jesus A. Gonzalez

July 17, 2019

Greedy Algorithms

Introduction

Elements of a Greedy Algorithm

Greedy Choice Property

Proving that a Greedy Algorithm is Optimal

Optimal Substructure

The Fractional Knapsack Problem

The Fractional Knapsack Problem

The Fractional Knapsack Problem

The Fractional Knapsack Problem

The Fractional Knapsack Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Activity Selection Scheduling Problem

Elements of the Greedy Strategy

Elements of the Greedy Strategy

Greedy-choice Property

Greedy-choice Property

Greedy-choice Property

Huffman Codes

Huffman Codes

Huffman Codes