Q1) Determine whether each of the following problems belong to the class NP or not. If the problem does not belong to the class NP, explain why not; if it does, discuss how the problem satisfies all of the characteristics that define the class NP. (a) Given is a set of jobs. Each job has a specific processing time, a release time, and a deadline. Jobs must be assigned to a machine that will execute it. A job can be executed only after its release time. Once the execution starts, the job will take a time equal to its processing time to complete. Is there a schedule that assigns all given jobs to one machine so that all jobs are completed before their deadlines? (b) A room described by a simple polygon 1 is given. A set of obstacles is given in the interior of the room. Each obstacle is described by a convex polygon. Two points a and b on the boundary of the polygon are also given. Find the shortest path between a and b that lies in the interior of the room and that does not cross the interior of any obstacle. (c) Given an array A of n integers, and a value v, is there an entry in the array A that equals v ? (d) Two graphs G1=(V1,E1) and G2=(V2,E2) are isomorphic if there exists a bijective function f:V1V2 so that (u,v) is an edge in graph G1 if and only if (f(u),f(v)) is an edge in graph G2. Given two graphs, are they isomorphic