## CS 5315 Homework #11

**Date Assigned:** Thursday, March 17, 2005
**Due Date:** Tuesday, March 29, 2005

1. Pick a propositional formula and use the general algorithm, to
transform it into DNF and CNF forms.

2. Similarly to what we did in the class, trace how another example of an
NP problem can be reduced to propositional satisfiability. Advise:
pick a problem R(x,y) with x, y of 1 bit length, and with a different
predicate R.