Differences

This shows you the differences between two versions of the page.

--- sav08:homework04 [2008/03/12 18:55]
vkuncak
+++ sav08:homework04 [2008/03/13 11:47] (current)
vkuncak
@@ Line 1: / Line 1: @@
-====== Homework 04 -DRAFT ======
+====== Homework 04 - due 19 March 2008 at 11:00 ======
 ===== Problem 1 =====
@@ Line 7: / Line 7: @@
 ===== Problem 2 =====
-Build a DPLL SAT solver that accepts input in the CNF version of the [[DIMACS format]].  (The input file is a formula in conjunctive normal form, where each clause is given on a separate line as a list of indices denoting propositional variables, a negative index indicates a negated propositional variable.)
+Implement the basic [[DPLL Algorithm for SAT]].  Your program should accepts input in the CNF version of the [[DIMACS format]].  (This input file is a formula in conjunctive normal form, where each clause is given on a separate line as a list of indices denoting propositional variables, a negative index indicates a negated propositional variable.)
-If a given formula is satisfiable, the SAT solver should produce an assignment to all variables such that the formula evaluates to //true// under this assignment.
+If a given formula is satisfiable, your SAT solver should produce an assignment to all variables such that the formula evaluates to //true// under this assignment.
+If a given formula is unsatisfiable, for now the SAT solver can simply say "false".
+The expected level of sophistication is the simple DPLL solver with unit propagation described in [[DPLL Algorithm for SAT]], it is not required that you implement advanced techniques or very efficient data structures.
+You will extend your solver in [[homework05]].
-If a given formula is unsatisfiable, the SAT solver can simply say "false".
-The expected level of sophistication is a DPLL solver with unit propagation, additional techniques will be part of the next homework.