Sample Mid-Term Exam Solutions

Problem 1

The PARTITION problem is defined as follows: The input is a list L of numbers. The output is either (A) a partition of L into two sets U and V such that the sum of the elements is U is equal to the sum of the elements in V (and therefore equal to half the sum of the elements in L); or (B) the statement that no such partition exists.

For example, given the input [1, 4, 6, 14, 17, 20] the output could be {1, 4, 6, 20}, {14, 17}, since both partitions add up to 31. Given the input [3, 4, 6, 14, 17, 20] the output would be "FALSE" since no such partition exists. Consider the following solution to this problem using state space search: Let M = the sum of the elements in L.

Problem 2

Show the result of carrying out alpha-beta pruning on the game tree shown below.

Problem 3

Convert the following sentence to CNF:
(P <=> Q) => R.
Answer: Going through the important intermediate steps.
[(P => Q) ^ (Q => P)] => R
~[(~P V Q) ^ (~Q V P)] V R
[(P ^ ~Q) V (Q ^ ~P)] V R.
Finally, one attains four clauses
1. P V ~P V R
2. P V ~Q V R
3  Q V ~P V R
4. Q V ~Q V R.
But clauses (1) and (4) are tautologies (true for all valuations, since they have a literal and its negation) and therefore can be dropped.

Problem 4

Trace the workings of the Davis-Putnam procedure on the set of clauses.
1. ~P V Q V R
2. P V ~Q
3. P V ~R
4. ~P V ~Q V S
5. ~Q V R V ~S
6. ~R V ~S
7. ~A V P.
8. ~A V R.
Step 1: ~A is a pure literal. Set A=FALSE. Delete 7 and 8.

Set S1:

1. ~P V Q V R
2. P V ~Q
3. P V ~R
4. ~P V ~Q V S
5. ~Q V R V ~S
6. ~R V ~S
Step 2: No singleton clauses, no pure literals. Try P=TRUE. Delete clauses 2 and 3, delete ~P from 1 and 4.

Set S2:

1. Q V R
4. ~Q V S
5. ~Q V R V ~S
6. ~R V ~S
Step 3: No singleton clauses, no pure literals. Try Q=TRUE. Delete clause 1, delete ~Q from 4 and 5.

Set S3:

4. S
5. R V ~S
6. ~R V ~S
Step 4: 4 is a singleton clause. Set S=TRUE. Delete clause 4, delete ~S from 5 and 6.
5. R
6. ~R
Step 5: 5 is a singleton clause. Set R=TRUE. Delete clause 5, delete ~R from clause 6.

Step 6: 6 is now the empty clause. Fail. Go back to step 3, set S2. Try Q=FALSE. Delete clauses 4, 5. Delete Q from 1.

Set S4.

1. R
6. ~R V ~S
Step 7: 1 is a singleton clause set R=TRUE. Delete clause 1. Delete ~R from 6.
6. ~S.
Step 8: 6 is a singleton clause. Set S=FALSE. Delete 6.

There are now no clauses left, so succeed. Return the current valuation: A=FALSE, P=TRUE, Q=FALSE, R=TRUE, S=FALSE.

Problem 5

Let G be an undirected graph. An independent set in G is a set of vertices Z such that no two vertices I,J in Z are connected by an edge. For instance, in the graph shown below, the set { E,F,H } is an independent set because the graph does not contain any of the edges EF, EH, or FH.

The INDEPENDENT SET problem is, given a graph G and an integer K, find an independent set in G of size K.

An instance of the INDEPENDENT SET problem can be translated into propositional satisfiability as follows: For each vertex V and for each integer I=1 .. K, define the atom V_I to be the assertion that V is the Ith vertex, alphabetically, in the set Z. Define the atom V_in to be the assertion that V is in the set Z. One then needs the following four types of constraints:

  1. V is in Z if and only if V is the Ith vertex in Z for some value of I.
  2. For I > 1, if V is the Ith vertex in Z then one of the vertices alphabetically before V is the (I-1)st vertex in Z. (If V is the first vertex alphabetically in G, then this amounts to the statement that V is not the second or third or fourth ... or Kth vertex in Z.)
  3. If U and V are connected in G then U and V are not both in Z.
  4. Some vertex is the Kth vertex in Z.
Give one instance of each of these four types of constraints that would be generated for the above graph with K=3.

Answer:
1. A_in <=> A_1 V A_2 V A_3.
2. C_2 => A_1 V B_1
3. ~(A_in ^ D_in).
4. A_2 V B_2 V C_2 V D_2 V E_2 V F_2 V G_2 V H_2
(There are many possible answers.)

Problem 6

Let D be a domain of geographical regions. Let L be a first-order language over D with the following primitives.
p(X,Y) --- Predicate. X is part of Y.
b(X,Y) --- Predicate. X borders Y.
ci(X) --- Predicate. X is a city.
co(X) --- Predicate. X is a country.
ll(X) --- Predicate. X is landlocked
s(X) --- Predicate. X is a sea.
paris, portugal, europe --- Constants.

Express the following sentences in L:
A. Every city is part of some country
Answer: forall(X) ci(X) => exists(Y) co(Y) ^ p(X,Y).
B. No city is part of any sea.
Answer: ~[exists(X,Y) ci(X) ^ s(Y) ^ p(X,Y).]
C. A region is landlocked if and only if it does not border any sea.
Answer: forall(X) ll(X) <=> ~(exists(Y) s(Y) ^ b(X,Y)).
D. There exists a country that contains every city that borders Paris.
Answer: exists(X) co(X) ^ [forall(Y) ci(Y) ^ b(Y,paris) => p(Y,X)].
E. There is at least one landlocked country in Europe.
Answer: exists(X) co(X) ^ ll(X) ^ p(X,europe).
F. Portugal does not border any landlocked countries.
Answer: ~[exists(X) ll(X) ^ co(X) ^ b(portugal,X)]