UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 9


This assignment is due on Tuesday April 10 (the last day of classes), at 5PM, in the assignment boxes. It is based on Chapter 9 of DPV.

A solution is available.



Write an O(m+n) time algorithm that, given a set of m 2SAT clauses with n variables x[j] , an index j ∈ {1 … n}, and value v ∈ { 0, 1 }, returns the set of "reduced" clauses after setting x[j] = v, (set variable j to value v) i.e. remove satisfied clauses and false literals. Analyze your algorithm.

Subset Sum

At the beginning of lecture notes 05.1, there is a backtracking algorithm for subset sum. Rewrite this into the "test + expand" model given previously for SAT and N-Queens.

Independent Set

In particular:

  1. Define a subroutine expand that splits a problem into smaller subproblems. Analyze this subroutine.
  2. Define a subroutine test that returns SUCCESS, FAIL, or UNKNOWN according to the rules of Section 9.1 in DPV. Analyze this subroutine.
  3. Prove the resulting backtracking algorithm is correct.