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