Problem 2 15 points Problem Description Alice, a Computer Science student, decides that she wants to get a minor in math. She has already taken many but not all of the required courses as part of her CS degree. Here are the remaining requirements she needs to fulfill: She must take both Analysis (A) and Analysis II (B). She then has three electives of which she must take two; these are: Linear Algebra (C), Number Theory (D) and Modern Algebra (E). Alice must also take the following considerations into account: Alice has three more semesters of study to go. Fortunately, every course is offered every semester, but she can take at most two math courses during any given semester. She must take Analysis (A) before Analysis II (B). She must also take Linear Algebra (C) before Number Theory (D). She can only take Number Theory (D) once she's taken Modern Algebra (E). Analysis (A) and Linear Algebra (C) are always offered at exactly the same time, so she cannot take both in the same semester. CSP Formulation We formulate Alice's scheduling problem as a CSP in which each variable corresponds to a class Alice must take and the values correspond to the numbering of the remaining semesters: 1 for junior Spring, 2 for senior Fall and 3 for senior Spring; and 0 for "does not take this course". Backtracking Search with AC-3 Let's solve this CSP using backtracking search with arc consistency. Namely, we will run the AC-3 algorithm as a preprocessor and after each variable assignment. When there is ambiguity as to which variable to assign next, assign a value to the variable corresponding with the course letter that comes first alphabetically. Furthermore, when the next value to assign to a variable is ambiguous, break ties by assigning the earliest value first (0 before anything else). 1. What are the remaining domains for each variable after applying unary constraints? (5 points) 2. What are the remaining domains after enforcing arc consistency on the results of the unary-constraint application? (5 points) 3. What are the remaining domains after assigning A=1 and re-enforcing arc consistency? (5 points) Problem 2 15 points Problem Description Alice, a Computer Science student, decides that she wants to get a minor in math. She has already taken many but not all of the required courses as part of her CS degree. Here are the remaining requirements she needs to fulfill: She must take both Analysis (A) and Analysis II (B). She then has three electives of which she must take two; these are: Linear Algebra (C), Number Theory (D) and Modern Algebra (E). Alice must also take the following considerations into account: Alice has three more semesters of study to go. Fortunately, every course is offered every semester, but she can take at most two math courses during any given semester. She must take Analysis (A) before Analysis II (B). She must also take Linear Algebra (C) before Number Theory (D). She can only take Number Theory (D) once she's taken Modern Algebra (E). Analysis (A) and Linear Algebra (C) are always offered at exactly the same time, so she cannot take both in the same semester. CSP Formulation We formulate Alice's scheduling problem as a CSP in which each variable corresponds to a class Alice must take and the values correspond to the numbering of the remaining semesters: 1 for junior Spring, 2 for senior Fall and 3 for senior Spring; and 0 for "does not take this course". Backtracking Search with AC-3 Let's solve this CSP using backtracking search with arc consistency. Namely, we will run the AC-3 algorithm as a preprocessor and after each variable assignment. When there is ambiguity as to which variable to assign next, assign a value to the variable corresponding with the course letter that comes first alphabetically. Furthermore, when the next value to assign to a variable is ambiguous, break ties by assigning the earliest value first (0 before anything else). 1. What are the remaining domains for each variable after applying unary constraints? (5 points) 2. What are the remaining domains after enforcing arc consistency on the results of the unary-constraint application? (5 points) 3. What are the remaining domains after assigning A=1 and re-enforcing arc consistency? (5 points)