[NP Completeness, 50 Points]1 Early spring registration is coming up soon, and wanting to nish all the degree requirements by the end of the Spring, you face the following problem: There are k areas in each of which you still need to take one course. You are lucky and indeed for each of the areas there is a list (set) of courses being oered C1,C2,...,Ck that you have not yet taken. Unfortunately, there are the unavoidable time conicts. Each area has coordinated the schedules so that there are no conicts for courses within each area, but you come up with a list of (class-1,class-2) pairs in dierent areas that are in conict (you cant take both). Now you have to decide if youll be able to nish next semester, that is, you need to decide if there is a way to choose a course from each area so that there are no conicts. Are you doomed ? Is this an NP-Complete problem ? Hint: You can assume, for the purpose of the problem, that you will be passing ECE-1762.