1. Students A, B, C, D and E are enrolled in a variety of different classes: A i

Question

1. Students A, B, C, D and E are enrolled in a variety of different classes:

A is taking English, Math, and Physics.
B is taking History and Geography.
C is taking Government, History, and Math. D is taking English, Physics, and Math.
E is taking Government, Math, and Physics

a) Draw the conflict graph for this scenario.

b) Express the graph as a 2-dimensional array.

c) Create a Final Exam schedule utilizing the minimal number of class periods(minimum number

of maximal independent set groupings) using the Maximal Independent Set algorithm.

Explanation / Answer

int graph[5][6] = { {1,1,1,0,0,0},{0,0,0,1,1,0},{0,1,0,1,0,1},{1,1,1,0,0,0},{0,1,1,0,0,1} }

function ms( G: graph): integer; W” if not connected (G) then begin C := smallest connected component of G; return ms(G - C) + (if /Cl I 2 then 1 else m(C)) end; if ICI I 1 then return ICI; choose A, B vertices of G such that (i) d(A) is minimal and (ii) (A, B) is an edge of G and d(B) is maximal over all neighbours of vertices with degree d(A); if d(A) = 1 then return 1 + ms(G - p(A)); if d(A) = 2 then begin B’ := N(A) - B; {the other neighbour of A } if edge( B, B’) then return 1 + ms(@ - N(A)); return mux(2 + ms(G - F(B) - N(B’)), 1 + mr2(G - #(A), N2(A))) end; if d(A) = 3 then return mux(mr2(G - A, N(A)),1 + WI.S(G - p(A))); if A dominates B then return ms(G --B); return max(ms(G - B), 1 + mr(G - N(B))) end:

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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