You are in-charge of designing the school curriculum for undergraduate studies and one of your tasks...

Transcribed Image Text:

You are in-charge of designing the school curriculum for undergraduate studies and one of your tasks is to arrange the modules in the different trimesters of undergraduate studies. You are given a list of dependencies between modules. For example, COMP30870 depends on COMP20290, COMP20010, COMP10030, COMP30010 and COMP10070 and therefore, it can only be put in a trimester that is after the trimesters for the dependent modules. [For simplicity, you do not have to worry about the number of modules in each trimester (i.e., your undergraduate students can do an arbitrary number of modules in each trimester).] (a) A dependency cycle between modules is a situation where the module dependencies are cyclic. For example, COMP32145 depends on COMP21345, COMP21345 depends on COMP31200 and COMP31200 depends on COMP32145. Prove that there exists a valid schedule of modules to trimesters if and only if there are no dependency cycles. [10 marks] [Update: There are two parts to this proof: Prove that if there is a cycle, you can't schedule the modules in different trimesters. And prove that if there is no cycle, you can always schedule the modules (the number of trimesters can be arbitrary large). You can use any of the lemmas proven in the lecture as given, by referring to them in these proofs.] (b) Give a (n+ m) algorithm to determine if the modules can be scheduled in at most eight trimesters. Here, n is the number of modules to be scheduled and m is the number of dependencies. Your algorithm should also provide a scheduling of the modules into different trimesters. Argue (no formal proof required) that your scheduling is correct. [15 marks] You are in-charge of designing the school curriculum for undergraduate studies and one of your tasks is to arrange the modules in the different trimesters of undergraduate studies. You are given a list of dependencies between modules. For example, COMP30870 depends on COMP20290, COMP20010, COMP10030, COMP30010 and COMP10070 and therefore, it can only be put in a trimester that is after the trimesters for the dependent modules. [For simplicity, you do not have to worry about the number of modules in each trimester (i.e., your undergraduate students can do an arbitrary number of modules in each trimester).] (a) A dependency cycle between modules is a situation where the module dependencies are cyclic. For example, COMP32145 depends on COMP21345, COMP21345 depends on COMP31200 and COMP31200 depends on COMP32145. Prove that there exists a valid schedule of modules to trimesters if and only if there are no dependency cycles. [10 marks] [Update: There are two parts to this proof: Prove that if there is a cycle, you can't schedule the modules in different trimesters. And prove that if there is no cycle, you can always schedule the modules (the number of trimesters can be arbitrary large). You can use any of the lemmas proven in the lecture as given, by referring to them in these proofs.] (b) Give a (n+ m) algorithm to determine if the modules can be scheduled in at most eight trimesters. Here, n is the number of modules to be scheduled and m is the number of dependencies. Your algorithm should also provide a scheduling of the modules into different trimesters. Argue (no formal proof required) that your scheduling is correct. [15 marks]

Answer rating: 100% (QA)

a Proof To prove that there exists a valid schedule of modules to trimesters if and only if there are no dependency cycles we will split the proof into two parts Part 1 If there is a cycle you cant sc... View the full answer