I will hand out the answers and discuss them on Tuesday, Oct. 17.

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.

- A
*state*is a triple < L1,U1,V1 > where L1 is a list; U1 and V1 are sets; and L1, U1, and V1 are a partition of L (that is, each element of L is in exactly one of L1, U1, and V1. - The operations on < L1,U1,V1 > are defined as follows: Delete the head of L1 and either add it to U1 or add it to V1, as long the sum of the elements in the new set is no more than M/2.
- The start state is < L, {}, {} >
- A goal state is one in which L1 is the empty list.

A. Show the portion of the state space generated in a depth-first search for the problem L=[1, 2, 3, 4]. Note that M=10. (Note: To save writing, just label each state with the values of U1 and V1; you can omit L1.)

B. Suppose that the list L has size 50. What is the branching factor? What is the maximum depth of the tree? Give an upper bound on the maximum size of the tree.

(P <=> Q) => R.

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.

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:

- V is in Z if and only if V is the Ith vertex in Z for some value of I.
- 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.)
- If U and V are connected in G then U and V are not both in Z.
- Some vertex is the Kth vertex in Z.

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

B. No city is part of any sea.

C. A region is landlocked if and only if it does not border any sea.

D. There exists a country that contains every city that borders Paris.

E. There is at least one landlocked country in Europe.

F. Portugal does not border any landlocked countries.