Introduction

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.

Questions

2SAT

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

• Given a graph G=(V,E), S ⊆ V is an independent set if no pair of vertices in S is joined by an edge of G (i.e. no pair is in E). You assignment is to write a backtracking algorithm for the following

• INPUT graph G=(V,E), integer k

• OUTPUT If G has an independent set of size at least k then YES else NO.

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.