How much time will the algorithm take to terminate

Assignment Help Data Structure & Algorithms

Reference no: EM131661951

Assignment

This question considers representing satisfiability (SAT) problems as CSPs.

a. Draw the constraint graph corresponding to the SAT problem

(¬X1 ∨ X2) ∧ (¬X2 ∨ X3) ∧ ... ∧ (¬Xn-1 ∨ Xn)

for the particular case n = 5.

b. How many solutions are there for this general SAT problem as a function of n?

c. Suppose we apply BACKTRACKING-SEARCH (page 215) to find all solutions to a SAT CSP of the type given in (a). (To find all solutions to a CSP, we simply modify the basic algorithm so it continues searching after each solution is found.) Assume that variables are ordered X1,...,Xn and false is ordered before true. How much time will the algorithm take to terminate? (Write an O(·) expression as a function of n.)

d. We know that SAT problems in Horn form can be solved in linear time by forward chaining (unit propagation). We also know that every tree-structured binary CSP with discrete, finite domains can be solved in time linear in the number of variables.

Reference no: EM131661951

Questions Cloud

Resource on the web for programming in python : Research is key when becoming an effective programmer. Locate a useful resource on the web for programming in Python

Operate without roaming profiles : Could a medical facility such as Bayside Memorial Hospital operate without roaming profiles, and if how would it impact user accessibility?

Compare commands in both the windows and linux cli : Compare commands in both the Windows and Linux CLI. How can you get help in Linux?

Mac os x and linux os : Discuss similarities and the differences you've discovered between Mac OS X and Linux OS.

How much time will the algorithm take to terminate : How many solutions are there for this general SAT problem as a function of n? How much time will the algorithm take to terminate?

What factors would affect the internal validity of study : How will you select your sample to make sure that your study has external validity. What factors would affect the internal validity of your study

Python program for problem : PYTHON PROGRAM: Write the Python program for this problem using the Python IDLE editor.

What role a corporation audited financial statements play : What role does a corporation's audited financial statements play in determining its taxable income

Transition to adulthood-emerging adults : Read and summarize a scholarly journal article (published since 2008) with a focus on transition to adulthood.

User Account

All Pages