1. The following question will ask you about the below test scheduling constraint satisfaction graph, where each node represents a course. Each course is associated with an initial domain of possible test days (most courses could be on Monday, Tuesday, or Wednesday; a few are already restricted to just a single day). An edge between two nodes means that those two classes must have test on different days.

After enforcing arc consistency on this problem, what are the resulting domains for the variables C, D, and E? [25 points]

2. A car company manufactures trucks and SUVs. A Truck needs 15 hours to be made and can be sold for a profit of $4000. A SUV takes 20 hours to be completed and sells for a profit of $5000. There is a client who wants at least 25 cars and at least 5 of each type ready in 48 hours. The manufacturer is interested in the best combination of trucks and SUVs to make so that it has the most possible profit from the client.

Formulating this linear programming problem and define the cost function and the constraints associated with it. [25 points]

3. As shown in the following map, Australia has seven political divisions including New South Wales (NSW), Queensland (Q), Northern Territory (NT), Western Australia (WA), South Australia (SA), Victoria (V), and Tasmania (T).

You want to color each region of Australia on the map using red, blue, or green. You need to do it in such a way that no neighboring territory has the same color.

Consider this as a CSP and answer the following questions.

3-1. Define this CSP in terms of its variables, their domain, and possible constraints. You also need to draw the constraint graph associated with this CSP. [20 points]

3-2. How many solutions are there for this map-coloring problem? Briefly justify your answer. [10 points]

4. Explain why it is a good heuristic to choose the variable that is most constrained but the value that is least constraining in a CSP search. [20 points]