1. Consider a set S of n classes, where each class i has a start time...

  

Transcribed Image Text:

1. Consider a set S of n classes, where each class i has a start time s; and a finish time f. We want to broadcast an announcement that will be heard by all classes; if the announcement is broadcast at time t, then all classes i such that s; ≤ t ≤ f; will hear the announcement. We are willing to broadcast the announcement multiple times, so we can hit all classes, but we want to minimize the number of broadcasts. (a) Consider a greedy approach that repeatedly picks the midpoint of the shortest remaining class, and then removes all classes that are hit by that broadcast time. Give and demonstrate a counterexample to show that this approach does not always find the minimum number of broadcast times. (b) Design and write a greedy algorithm that, given the start times s; and finish times fi for each class, will find a minimum size set of times when the announcements can be broadcast in order to hit all classes. (c) Prove that your algorithm from (b) is correct. 1. Consider a set S of n classes, where each class i has a start time s; and a finish time f. We want to broadcast an announcement that will be heard by all classes; if the announcement is broadcast at time t, then all classes i such that s; ≤ t ≤ f; will hear the announcement. We are willing to broadcast the announcement multiple times, so we can hit all classes, but we want to minimize the number of broadcasts. (a) Consider a greedy approach that repeatedly picks the midpoint of the shortest remaining class, and then removes all classes that are hit by that broadcast time. Give and demonstrate a counterexample to show that this approach does not always find the minimum number of broadcast times. (b) Design and write a greedy algorithm that, given the start times s; and finish times fi for each class, will find a minimum size set of times when the announcements can be broadcast in order to hit all classes. (c) Prove that your algorithm from (b) is correct.

Answer rating: 100% (QA)

a Counterexample to the greedy approach Consider the following class schedule Class 110001100 Class ... View the full answer