In this problem, you will write a program that implements two algorithms for performing exact inference given a Bayesian network, namely, enumeration and variable elimination. Your program should accept exactly three command-line arguments:

BayesNet

The first argument is a file specifying a Bayesian network (see the section "Specifying a Bayesian Network" below for the file format for a Bayes net). The second argument is either elim or enum, which indicates whether enumeration or variable elimination should be used as the underlying inference mechanism. The third argument is a query. The query should be formu- lated as a probability, such as "P(C|A=f,E=t)". This query would return the two probabilities for C given that A is false, and E is true. Do not include spaces in the query, and you should put the query in quotes. Given these three inputs, one of the things your program should print to stdout the result of the inference. Specifically, the result should be output by printing the conditional probabilities of the query variable given the observed variables, such as:

P(C = f | A = f, E = t) = #

P(C = t | A = f, E = t) = #

for both values of the query variable and the values for the observed variables.

In addition to outputting the result of the inference, your program also needs to output other information it computes during the inference process so that we can track the correctness of your implementation. The sections "Implementing the Variable Enumeration Algorithm" and "Implementing the Variable Elimination Algorithm" provide details on what to print during inference.

To simplify your implementation, your program only needs to handle queries with one query variable. Nevertheless, your program should work even if no observed variables are given. In other words, your program should accept a query containing an unconditional probability of a variable.

Specifying a Bayesian Network

Let us try to understand the file format for a Bayes net via the "alarm" example we saw in class. Recall that in the "alarm" Bayes net, there are five nodes, B, E, A, J, and M, each of which is associated with a conditional probability table. The file for this Bayes net would look like this:

P(B) = .001

P(E) = .002

B E | A

----|-----

t t | .95

t f | .94

f t | .29

f f | .001

A | J

--|-----

t | 0.90

f | 0.05

A | M

--|-----

t | 0.7

f | 0.01

Specifically, each node is sectioned off from the others using double newlines, and there are two types of nodes: nodes without parents and nodes with parents. The nodes without parents are just represented as P(X) = #. The nodes with parents are represented as a table. The first line for the node is a table header which lists the parent nodes separated by spaces, followed by a pipe symbol and finally the name of that node. The next line can be skipped. There are then 2(#parents) lines representing table entries. A table entry is a list of p 't' or 'f' symbols (where p = #parents), separated by spaces, followed by a pipe symbol and finally a decimal number between 0 and 1. The entry can be interpreted as the probability of the node being true given the truth values for its parents. Truth value i corresponds to parent i from the table header.

If you understand BNF notation, below is the specification of a Bayes net in BNF (with extensions):

::= ( )*

::= |

::= "P(" ") = "

::=