Question $7(20)$

Consider the discussion of the complexity of the DPLL algorithm given in $3\mathrm{.}6\mathrm{.}4.$

$1.$ Check the time complexity analysis by showing how the DPLL algorithm will deal with a set

of clauses involving $3$ propositional symbols, as specified for the worst case. Execute the DPLL

algorithm. Count and state the number of clauses, the number of choice points and the number

of inspections to verify the given formulas.

$2.$ Devise a way to mark the clauses and literals in a set of clauses to allow the DPLL algorithm

to attain a space complexity of O$($n$).$

$3.$ Count the number of inspections involved in a single branch, that the non$-$deterministic analysis

would require as described in the final section of the $3\mathrm{.}6\mathrm{.}4.$