Computer Science 242

Homework B

Suggested review problems - not collected.
  • AIMA Chapter 6
    • Ex 6.6, 6.8, 6.13, 6.15
    • Find a tree decomposition of this graph:


      What is the lowest treewidth you can obtain?

    • Find a tree decomposition of this graph:


      What is the lowest treewidth you can obtain?

  • AIMA Chapter 7
    • Ex 7.4, 7.6, 7.7, 7.9, 7.18
    • Convert the following sentences of propositional logic to conjunctive normal form (CNF). Your answer should be a set of clauses of the form [X, Y ], [Z, ¬X, Y ], . . ..
      • P ⇒ Q.
      • (¬P ∧ Q) ∨ R
      • W ⇒ (P ∧ Q)
      • (P ∨ Q) ⇒ (R ⇒ (S ∧ V ))
  • AIMA Chapter 8
    • Ex 8.2, 8.4, 8.12, 8.24
  • AIMA Chapter 9
    • Ex 9.3, 9.4, 9.25, 9.26
    • Convert the following sentences to first-order conjunctive normal form (CNF).
      • ∀x ∃y Boy(x) ∧ Girl(y) ⇒ Likes(x,y)
      • ∃y ∀x Boy(x) ∧ Girl(y) ⇒ Likes(x,y)
      • ∃x ∀y ¬ P(x,y)
      • ∃x ¬ ∀y P(x,y)
      • ¬ ∃x ∀y P(x,y)
      • ∀x ∃y ¬ P(x,y)
      • ∀x ¬ ∃y P(x,y)
      • ¬ ∀x ∃y P(x,y)