## Introduction

Boolean formula (e.g. x ∧ y ∨ z) are used throughout computer science (programming languages, AI, etc.). Sometimes, we want to know if something is possible. In this case, we might want to know whether a boolean formula is satisfiable, i.e., is there a setting of the variables in a way that makes the entire formula true. Sometimes, we want to know how many ways something can be done. This corresponds to counting the number of satisfying assignments to a boolean formula. For this assignment, you will be counting the number of ways that a given boolean formula can be evaluate to true.

For the purposes of this assignment, boolean formula will be described recursively as follows.

A boolean formula might be just a single variable, e.g., ABC. Here, a variable is given a sequence of characters. The first character must be either a lowercase or uppercase letter (a-z or A-Z), with all subsequent characters being letters or numbers. So, for example x1 would be considered a variable name, whereas x.1 would not be a valid variable.

If A1 and A2 are boolean formula, then (A1 + A2) is a boolean formula (+ == AND), (A1|A2) is a boolean formula (| == OR), and A1 is a boolean formula (- == NOT).

Hence, for example, (x + (y | -z)) is a valid boolean formula. This formula is true exactly 3 times.

So, for this assignment, you will read in a boolean formula and you will compute the number of satisfying assignments to the boolean formula.

## Part 1 Sequential Algorithm

For the first part, you will create a class SeqCounting with at least one public member function int SatisfyingAssignments(string formula); that takes a boolean formula as input (in string form) and returns the number of satisfying assignments. Your code will do this by trying every possible setting of the variables.

## Part 2 Parallel Algorithm VI

For the second part, you will create a class ParCounting with at least one public member function

1 | int SatisfyingAssignments(string formula); |

that takes a boolean formula as input (in string form) and returns the number of satisfying assignments. Your code will do this by trying every possible setting of the variables. However, your code will run in parallel using the OpenMP constructs given in class. However,this code should NOT use the reduction construct.

Your code should be at least 75% efficent when using 4 cores.

## Part 3 Parallel Algorithm VII

For the second part, you will create a class Par2Counting with at least one public member function

1 | int SatisfyingAssignments(string formula); |

that takes a boolean formula as input (in string form) and returns the number of satisfying assignments. Your code will do this by trying every possible setting of the variables. However, your code will run in parallel using the OpenMP constructs given in class. In particular, your code should use the reduction construct discussed in Lecture #5. Your code should be at least 75% efficent when using 4 cores.

## Submission

Each of the classes described above should be implemented in a single separate C++ file. The instructor will provide an appropriate test harness. DO NOT modify the class names or prototypes. Make sure that your code is adequately documented.