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

# 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.