Greedy Algorithms

Question 1

What are Greedy Algorithms?

Answer 1

Picking the nest thing to do that looks like the best option in that moment

Question 2

What is Interval Scheduling?

Answer 2

GOAL: find maximum subset of mutually compatible jobs.

Compatible: jobs that don’t overlap

Question 3

What is Interval Partitioning?

Answer 3

Consider Lecture j that starts at s_j and fnishes at f_j.

GOAL : find the least number of classrooms to schedule all lectures so that no two occur at the same time in the same room.

Question 4

What is minimizing lateness?

Question 5

What is Optimal Offline Caching?

Question 6

What is Coin Changing?

Question 7

What is meant by ‘Selecting Breakpoints’?

Question 8

What are the methods of proving that the greedy strategy is the optimal strategy?

Question 9

What is the Greedy Template for Interval Scheduling?

Answer 9

• Earliest Start Time : choosing earliest start time (s_j)
• Earliest Finish Time : choosing earliest finish time (f_j)
• Shortest Duration: Choosing lowest (f_j - s_j)
• Fewest Conflicts: for each job j counter conflicts and order in ascending conflicts

Question 10

Out of each greedy options for interval scheduling which are optimal and which are not?

Answer 10

• Earliest start time: NOT OPTIMAL
• Earliest finish time: OPTIMAL
• Shortest Duration: NOT OPTIMAL
• Fewest Conflicts: NOT OPTIMAL

Question 11

What is the Counterexample for the earliest start time for interval scheduling?

Answer 11

consider selecting job with early start time but extremely long duration, taking up entire time

Question 12

Counter example for using shortest duration greedy template for interval scheduling?

Answer 12

consider job with short duration that is incompatible with 2 longer duration jobs which are compatible with each other

Question 13

Counterexample for using fewest conflicts greedy template for interval scheduling?

Answer 13

consider a job with few conflicts that is incompatible with a jobs with more conflicts however those 2 jobs are compatible with each other and the original job is compatible with neither.

Question 14

What is the proof that the earliest-finish-first greedy strategy is optimal for interval scheduling?

Answer 14

• Assume for contradiction that the greedy algorithm is not optimal
• Assume that the greedy algorithm is a set of defined intervals i_… and the optimal solution is a set of defined intervals/jobs b_..
• Say that they are the same up to some maximum value r.
• Now consider the next job to be selected by either algorithms and use the exchange arguement