Please give explanation followed by answer of each question, clearly clarifying what the answer is. Thank you.

Suppose you are a lecturer, trying to organise a class consisting of outside speakers and student projects, for a course lasting for n weeks. The plan is that for the first m weeks, the outside speakers will give lectures. Then for the next nm weeks, students work on projects depending on the speakers' lectures. The outside speakers have time constraints. That is, in week 1 , only some speakers are available, and so on. The projects also depend on the lectures. That is, for each project, there is a set of relevant speakers so that the students need to have seen a lecture by at least one of the speakers in this set, in order to be able to complete the project. The question is: can you design a schedule of the speakers, so that their availability, and the students projects' dependences, are both satisfied? Note that in each week only one speaker can be invited. Let's see an example. Suppose n=5 and b=2 and there are 4 speakers U={A,B,C,D}. The availability of speakers can be encoded by the following sets: L1={A,B,C} and L2={A,D}. The project dependences are encoded by the following sets: P1={B,C},P2={A,B,D}, and P3={C,D}. Then we can arrange the speakers as B for the first week, and D for the second week to satisfy all the constraints. 1. Give a formal set-theoretic formulation of the problem (7.5 pts). 2. Show that this problem is in NP (7.5 pts). 3. Prove that this problem is NP-hard ( 5pts). Suppose you are a lecturer, trying to organise a class consisting of outside speakers and student projects, for a course lasting for n weeks. The plan is that for the first m weeks, the outside speakers will give lectures. Then for the next nm weeks, students work on projects depending on the speakers' lectures. The outside speakers have time constraints. That is, in week 1 , only some speakers are available, and so on. The projects also depend on the lectures. That is, for each project, there is a set of relevant speakers so that the students need to have seen a lecture by at least one of the speakers in this set, in order to be able to complete the project. The question is: can you design a schedule of the speakers, so that their availability, and the students projects' dependences, are both satisfied? Note that in each week only one speaker can be invited. Let's see an example. Suppose n=5 and b=2 and there are 4 speakers U={A,B,C,D}. The availability of speakers can be encoded by the following sets: L1={A,B,C} and L2={A,D}. The project dependences are encoded by the following sets: P1={B,C},P2={A,B,D}, and P3={C,D}. Then we can arrange the speakers as B for the first week, and D for the second week to satisfy all the constraints. 1. Give a formal set-theoretic formulation of the problem (7.5 pts). 2. Show that this problem is in NP (7.5 pts). 3. Prove that this problem is NP-hard ( 5pts)