S -> Noun VP [0.5] S -> NP Verb [0.5] VP -> Verb Noun [1.0] NP -> Adj Noun [1.0] Adj -> "bronze" [1.0] Noun -> "bronze" [0.1] Noun -> "pots" [0.6] Noun -> "clatter" [0.3] Verb -> "bronze" [0.1] Verb -> "pots" [0.1] Verb -> "clatter" [0.8]
A. Show the two possible parse trees for the sentence "bronze pots clatter" and label each node with its probability. You may write the probability as a product e.g. "0.2*0.3*0.4"; this is not an test on how well you can multiply. Hint: it is more efficient to think about this problem top-down than to try to simulate the CYK parser, which works bottom-up.
B. The CYK parser will add some nodes to the chart that are not in either of the parse trees. Give an example of one such node.
Answer: The two starred nodes below
1. P => (Q <=> R).A. Convert this set to CNF. (You need not show the intermediate steps.)
2. Q <=> ~(R^W)
3. Q => (P^W).
1A. ~P V ~Q V R
1B. ~P V Q V ~R
2A. ~Q V ~R V ~W
2B. Q V R
2C. Q V W
3A P V ~Q
3B ~Q V W
B. Show how the Davis-Putnam assignment finds a satisfying assumption. (Assume that, when a branch point is reached, the algorithm chooses the first atom alphabetically and tries TRUE before FALSE.)
Set S0 as above. Try P=TRUE. Delete clause 3, delete ~P from 1A, 1B. Set S1 1A. ~Q V R 1B. Q V ~R 2A. ~Q V ~R V ~W 2B. Q V R 2C. Q V W 3B ~Q V W Try Q=TRUE. Delete clauses 1B, 2B, 2C, delete ~Q from 1A, 2A, 3B. 1A. R 2A. ~R V ~W 3B W 1A is a singleton clause. Set R=TRUE. Delete 1A, delete ~R from 2A. 2A. ~W 3B. W 2A is a singleton clause. Set W=FALSE. Delete 2A, delete W from 3B. 3B is the null clause. Fail. Return to S1. Try Q=FALSE. Delete 1A, 2A, 3B, delete Q from 1B, 2B, 2C, 1B. ~R 2B. R 2C. W 1B is a singleton clause. Set R=FALSE. Delete 1B, delete R from 2B. 2B is the null clause. Fail Return to S0. Try P=FALSE. Delete 1A, 1B. Delete P from 3A. 2A. ~Q V ~R V ~W 2B. Q V R 2C. Q V W 3A ~Q 3B ~Q V W 3A is a singleton clause. Set Q=FALSE. Delete 2A, 3B, delete Q from 2B, 2C. 2B. R 2C. W 2B and 2C are singleton clauses. Set R=TRUE, W=TRUE. Succeed P=FALSE, Q=FALSE, R=TRUE, W=TRUE.
The INDEPENDENT SET problem is, given a graph G and an integer K, find an independent set in G of size K.
Consider the problem of finding the largest independent set in a graph G. Suppose that you want to use a blind search method (DFS, BFS, or iterative deepening) to solve the problem.
Answer: The problem was inconsistently worded; it first defines the goal as finding an independent set of size K, then redefines it to be the problem of finding the largest independent set. I'll answer the first wording.
State: A list of at most K vertices in alphabetical order such that no two vertices are connected by an edge.
Operator: Given a state S, add some vertex alphabetically later than the vertices in S that is not connected by edges to any of the vertices in S.
Start state: The empty list.
Goal state: A state with K vertices.
Answer: Depth: K. Branching factor: N (at the root). The space is a tree. The goal is at depth K.
Answer: Depth-first search.
Continuing with the INDEPENDENT SET problem from problem 5, Suppose that you now want to solve the problem "Does there exist an independent set of size K?" for some specific K. You want to solve the problem by translating it into satisfiability.
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:
A_in <=> A_1 V A_2 V A_3
D_3 => A_2 V B_2 V C_2
~(C_in ^ G_in).
A_3 V B_3 V C_3 V D_3 V E_3 V F_3 V G_3 V H_3.