Consider the task of creating a timetable for final exams (assuming offline exams) for this semester. Assuming a uniform practice of 2-hours for the end-sem exams (Grad Algo exams are always scheduled outside of this process!) the only slots for any day are: 9-11, 11-1, 1-3, 3-5. Academic office has a list of all students, all courses that they are registered for (assume that all courses have end-sems), and the list of their instructors. Of course, two exams cannot happen in the same slot even if a single student has to take both exams (or the instructor is common). DoAA has further instructed the acad office to ensure that no student writes more than two exams on the same day (assume that every student is registered for at most 5 courses).

Suppose, the acad office approached you for a solution; in particular, they want to know the number of days needed to hold all exams. Since you recently learned the theory of NP-completeness reductions, you thought to undertake the task of proving this task as extremely challenging.

Towards this goal, consider the below problem:
Given a list of c courses A={A1 ... Ac} (each Ai is a course), the list of students in each course S={S1 ... Sc} (each Si is a set of at most n students), the instructor for each course J={J1 ... Jc} (each Ji is an instructor), the task is to determine the minimum number of days needed to schedule all exams meeting the above conditions.

(a [2 points]) Design a decision problem that is equivalent to solving the above optimization problem and state it precisely (name it EXAM) . Briefly explain the equivalence in 5-6 sentences (avoid pseudocode).

(b [2 points]) Show that EXAM is in NP.

(c [7 points]) Show that EXAM is NP-hard. Include a clear statement of the other problem used for reduction. Refer to JE-12.14 for some tips.

Note that (b) and (c) show that EXAM is NP-complete, and this along with the connection to the original problem as outlined in (a) shows that the general computational problem faced by the acad office is unlikely to have a polynomial-time solution.

(d 4 points]) Suppose that exams has to be scheduled only for senior PhD students and the Director wanted to know if all of their exams can be conducted in exactly two slots (9-11 and 3-5) on a single day. Design a polynomial-time algorithm for by reducing this problem (call the problem PHDEXAM) to a graph problem and applying a standard graph algorithm. Include all steps and justification but keep the description short [avoid pseudocode]. The inputs to PHDEXAM are A and S as describe above (instructors need not be present in their exams).