3. Consider this classic scheduling problem: for a certain lecture room, we are

Question

3. Consider this classic scheduling problem: for a certain lecture room, we are given the start and end tines of a set of classes that could be assigned to the room. We wish to create a schedule that maximizes the number of classes offered in the room, so that none of them overlap in time. (The remaining classes are assigned to other rooms.) Note that there may be more than one optimal schedule! A bold 376 classmate claims to have come up with an algorithm that will always produce an optimal schedule, which works as follows: function Schedule (X): //X= array of classes Y-empty SortByStart (X) // Sort X by start times, ascending order for each C 1n X: if c does not overlap with any class in Y append c to Y returnY Consider the following set of classes for the room: EECS 376 EECS 370 ASTRO 106 1:00P-2:00P EARTH 103 2:15P-4:15P EECS 281 10:30A-12:00P11:30A-1:00P 1:30P-3:00P UC 371 11:00A-5:00P12:00P-1:00P 2:00P-3:15P EECS 482x THTREMUS 285 CRUMHORN 400 HISTORY 220 4:00P-4:30P 5:00P-6:00P (a) What schedule will this algorithm return when given the above list of classes? Is it (b) Provide a set of class times for which the above algorithm returns a suboptimal schedule, (c) Let's modify the above algorithm so that it instead sorts the classes by their finish times optimal? and show an optimal schedule for comparison. (in ascending order). Let Y = [ci, c2, ,ck] denote the final output of the algorithm. and S = [81,82, . . . , sm] denote an arbitrary optimal schedule. Prove by induction that for every i

Explanation / Answer

3.

a)Schedule that we will get for above algorith is, so first sort the data by start time in increasing order

EECS 376 10:30 AM - 12:00 PM
EECS 482x 11:00 AM - 5:00PM
EECS 281 11:30 AM - 1:00 PM
US 371 12:00 PM - 1:00 PM
ASTRO 106 1:00 PM - 2:00 PM
EECS 370 1:30 PM - 3:00 PM
THTREMUS 285 2:00PM - 3:15PM
EARTH 103 2:15PM - 4:15PM
CRUMHORN 400 4:00PM - 4:30PM
HISTORY 220 5:00PM - 6:00PM

Class marked with BOLD is the schedule returned by algorithm mentioned in question.

This is also the optimal schedule as we can observe from below when we sort the classes by ascending order of end time. Schedule part of solution is marked as BOLD.

EECS 376 10:30 AM - 12:00 PM
EECS 281 11:30 AM - 1:00 PM
US 371 12:00 PM - 1:00 PM
ASTRO 106 1:00 PM - 2:00 PM
EECS 370 1:30 PM - 3:00 PM
THTREMUS 285 2:00PM - 3:15PM
EARTH 103 2:15PM - 4:15PM
CRUMHORN 400 4:00PM - 4:30PM
EECS 482x 11:00 AM - 5:00PM
HISTORY 220 5:00PM - 6:00PM

b) Now consider three classes with following time

A 10:00 AM - 5:00 PM

B 11:00AM - 4:00 PM

C 4:00PM - 5:00 PM

So, schedule returned by algorithm mentioned in question is {A} but we can observe that optimal schedule to maximize number of classes is {B,C}

c)

Y = {c1, c2,..........,ck} Output of our algorithm

S = {s1, s2,...........,sm} Optimal schedule

Supporse original problem has only one activity. So, that activity will be selected and and optimal solution has also that activity, so our answer is true for n=1.

Now, lets say finishing time of activity ci is later than si than means that there exits a activity sj where ci==sj and optimal schedule j>i, so there exist a activity j whose finishing time is less than ci but it is not part of solution, but we can add that activity to our solution and sill maintain optimality. So, number is equal to m

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.