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
• Tasks
– Processing requirements, release times,
deadlines
• 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
• Tasks
– Processing requirements, release times,
deadlines
• 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
• Tasks
– Processing requirements, release times,
deadlines
• 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
Schedule earliest available task
Schedule shortest available task
Schedule task with fewest conflicts
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!