(80 pts.) Constraint Solving Suppose you are given a list of m constraints over integer variables vi, ..., Vn, with each constraint being either an equality (e.g. vi = vj) or a disequality (e.g. Vi #v;). Some sets of constraints are consistent, or satisfiable, in that it is possible to make them simultaneously true: for example the constraints v1 = v2 and v2 # vz can be satisfied by assigning vi = v2 = 0 and v3 = 2. Other sets of constraints are inconsistent (or unsatisfiable), being impossible to make simultaneously true: for example vi = v2, v2 = v3, and vi + v3. (a) (30 pts.) Describe an efficient algorithm to determine if a set of constraints in the form described above is satisfiable. Your algorithm should take less than (nm) time. (b) (10 pts.) What is the worst-case asymptotic runtime of your algorithm, in terms of n and m? (c) (40 pts.) Prove your algorithm correct, i.e., prove that it returns true if and only if the given constraints are satisfiable. (Note: This is a type of Constraint Satisfaction Problem (CSP), a class of problems with a huge variety of practical applications, e.g. in scheduling, software verification, cryptanalysis, circuit design, etc. The question of whether there is an efficient algorithm for another type of CSP, the Boolean Satisfiability Problem (SAT), is at the heart of the famous unsolved P vs. NP problem in complexity theory. We'll touch briefly on this problem at the end of the course if we have time, and you can learn all about it in CSE 103.) (80 pts.) Constraint Solving Suppose you are given a list of m constraints over integer variables vi, ..., Vn, with each constraint being either an equality (e.g. vi = vj) or a disequality (e.g. Vi #v;). Some sets of constraints are consistent, or satisfiable, in that it is possible to make them simultaneously true: for example the constraints v1 = v2 and v2 # vz can be satisfied by assigning vi = v2 = 0 and v3 = 2. Other sets of constraints are inconsistent (or unsatisfiable), being impossible to make simultaneously true: for example vi = v2, v2 = v3, and vi + v3. (a) (30 pts.) Describe an efficient algorithm to determine if a set of constraints in the form described above is satisfiable. Your algorithm should take less than (nm) time. (b) (10 pts.) What is the worst-case asymptotic runtime of your algorithm, in terms of n and m? (c) (40 pts.) Prove your algorithm correct, i.e., prove that it returns true if and only if the given constraints are satisfiable. (Note: This is a type of Constraint Satisfaction Problem (CSP), a class of problems with a huge variety of practical applications, e.g. in scheduling, software verification, cryptanalysis, circuit design, etc. The question of whether there is an efficient algorithm for another type of CSP, the Boolean Satisfiability Problem (SAT), is at the heart of the famous unsolved P vs. NP problem in complexity theory. We'll touch briefly on this problem at the end of the course if we have time, and you can learn all about it in CSE 103.)