Homework 1. (Due: Sept 7, 2004) weight 100

1. Given a domain description D that only allows propositions of the form a causes f if p1, ..., pn and observation O about only the initial state: Define when (D, O) entails a query Q.

Hint: You may define initial states corresponding to a given O, and transition function(s) corresponding to a given D, and then use them to define when (D, O) entails a query Q.

Homework 2. (Due Sept 9th, 2004) weight 100

2. Show your attempt at proving R1, R2 and R3.

Homework 3. (Due Sept 16th, 2004) weight 100

3. Prove that 3-SAT is NP-complete.

Homework 4. (Due Sept 28th, 2004) Weight 300

Prove in detail R3 and R5. (The slides give you the sketch. You need to prove that the transformation from 3SAT to the problems R3 and R5 is such that: (i) F is satisfiable iff deciding (D,O), as constructed, is consistent. (ii) F is satisfiable iff there is a plan with respect to D, O, and the goal, as constructed. )

Homework 5. (Due Nov 23rd) weight 200

In the maintainability slides, a direct algorithm using s_i, s_i' etc. is given. In a subsequent slide hints about how to use counters to develop a new direct algorithm is given. (This algorithm is available in the paper on this topic.) Write down this algorithm. Illustrate how the direct algorithm using counters works on the example that I illustrated in the class.

Homework 6. (given Nov 23. was due Nov 30. extended to Dec 2.) (200 pts)

Described in slide 8 of Set 3-1. The reference in the 4th bullet is to slide 2 of that set.

Some solution and additional hints.