Courses

# Notes - Greedy Algorithm Notes | EduRev

## : Notes - Greedy Algorithm Notes | EduRev

``` Page 1

CSE 421
Algorithms
Richard Anderson
Lecture 7
Greedy Algorithms
Page 2

CSE 421
Algorithms
Richard Anderson
Lecture 7
Greedy Algorithms
Greedy Algorithms
• Solve problems with the simplest possible
algorithm
• The hard part: showing that something
simple actually works
• Pseudo-definition
– An algorithm is Greedy if it builds its solution
by adding elements one at a time using a
simple rule
Page 3

CSE 421
Algorithms
Richard Anderson
Lecture 7
Greedy Algorithms
Greedy Algorithms
• Solve problems with the simplest possible
algorithm
• The hard part: showing that something
simple actually works
• Pseudo-definition
– An algorithm is Greedy if it builds its solution
by adding elements one at a time using a
simple rule
Scheduling Theory
– Processing requirements, release times,
• Processors
• Precedence constraints
• Objective function
– Jobs scheduled, lateness, total execution time
Page 4

CSE 421
Algorithms
Richard Anderson
Lecture 7
Greedy Algorithms
Greedy Algorithms
• Solve problems with the simplest possible
algorithm
• The hard part: showing that something
simple actually works
• Pseudo-definition
– An algorithm is Greedy if it builds its solution
by adding elements one at a time using a
simple rule
Scheduling Theory
– Processing requirements, release times,
• Processors
• Precedence constraints
• Objective function
– Jobs scheduled, lateness, total execution time
• Tasks occur at fixed time
• Single processor
• Maximize number of tasks completed
• Tasks {1, 2, . . . N}
• Start and finish times, s(i), f(i) Interval Scheduling
Page 5

CSE 421
Algorithms
Richard Anderson
Lecture 7
Greedy Algorithms
Greedy Algorithms
• Solve problems with the simplest possible
algorithm
• The hard part: showing that something
simple actually works
• Pseudo-definition
– An algorithm is Greedy if it builds its solution
by adding elements one at a time using a
simple rule
Scheduling Theory
– Processing requirements, release times,
• Processors
• Precedence constraints
• Objective function
– Jobs scheduled, lateness, total execution time
• Tasks occur at fixed time
• Single processor
• Maximize number of tasks completed
• Tasks {1, 2, . . . N}
• Start and finish times, s(i), f(i) Interval Scheduling Simple heuristics