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

- Define a subroutine
`expand`

that splits a problem into smaller subproblems. Analyze this subroutine. - Define a subroutine
`test`

that returns`SUCCESS`

,`FAIL`

, or`UNKNOWN`

according to the rules of Section 9.1 in DPV. Analyze this subroutine. - Prove the resulting backtracking algorithm is correct.