Sample Mid-Term Exam

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

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.

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.

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.

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.

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.

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
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.