You may assume you already have a function FordFulkerson( G ) which computes max

Question

You may assume you already have a function FordFulkerson(G) which computes maximum flow on a weighted, directed graph given as an argument. Let n = |C|, m = |D|, and r = |R|.Describe how to find a valid exam schedule as a maximum flow problem. As well as a clearly labelled, visual representation of the flow network (drawn as for some small n,m, r, but clear how that would extend to arbitrary n,m, r), provide pseudo-code which would properly construct the flow network, call FordFulkerson(), and then emit the schedule.

Explanation / Answer

Exams for all courses are held at the end of each term, within a ?xed number of days, and using a ?xed number of rooms (assume each room has capacity to hold any one course). Each day has 3 time slots available for exams (morning, afternoon, evening). The task is then to compute an exam schedule given as input a set of courses C, a set of exam days D, and rooms R, and producing as output a time slot and room for each exam. In all of the below, in expressing pseudo-code you may assume you already have a functionFordFulkerson(G) which computes maximum ?ow on a weighted, directed graph given as an argument.

Let n = |C|, m = |D|, and r = |R|.

1. Describe how to ?nd a valid exam schedule as a maximum ?ow problem. As well as a clearly labelled,

visual representation of the ?ow network (drawn as for some small n, m, r, but clear how that would

extend to arbitrary n, m, r), provide pseudo-code which would properly construct the ?ow network, call

FordFulkerson(), and then emit the schedule.

2. A realistic exam schedule must take into account exam con?icts. If any student is taking course c1 and

course c2, then the exams for c1 and c2 cannot be held at the same time.

Modify your solution to accommodate this constraint, assuming that your input now includes a set of

students S and a mapping from students to course registrations (S ? P(C)). Again, provide a representative ?ow network where it is clear how it extends to arbitrary input, as well as the full pseudo-code

which constructs the appropriate ?ow network, runs it through FordFulkerson(), and emits a valid

schedule.

3. The goal now is to understand the complexity of your solution to question 2.

(a) How many edges are in the network you constructed in question 2? Give a precise number (and 10

justi?cation), based on n, m, r, and any other parametrization(s) of the S ? P(C) function you

feel is necessary.

(b) What are upper and lower asymptotic bounds on the time complexity of your code, excluding the 5

actual maximum ?ow calculation? Give a clear and convincing derivation.

4. Ideally, the exam schedule should also be as short as possible. Use pseudo-code to describe an algorithm 10

that would ?nd the minimum m given all of the above constraints. Suppose you also want it to be O(nk)

for some constant k. Does this limit the other parameters

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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