Write a C++ (or Python or Java) program for performing variable elimination. The program should take as input two files: (a) a Markov network in UAI format and (b) Evidence (namely an assignment of values to some subset of variables) in UAI format and output the partition function given evidence. Your program should eliminate the variables along the min-degree order (ties broken randomly).

Recall that the variable elimination algorithm has three steps:

1. Instantiate Evidence (Reduce the CPTs or factors).

2. Order the variables. (You are using the min-degree order for the purpose of this assignment)

3. Eliminate variables one by one along the order. Recall that to eliminate a variable X, we compute a product of all functions that mention X. Let us call the new function f. Then, we sum-out the variable from f to yield a new function f 0 . Then we replace all functions that mention X with f 0 .

Thus, following the divide and conquer approach to programming, you can first develop the following helper functions and then put them together into a variable elimination algorithm. (Note that either you can use the following approach or develop your own. The following might be easier).

1. Function Read: Create a class called GraphicalModel and create a object of this class from the given UAI file

2. Function Order: Compute a min-degree ordering over the non-evidence variables (note that you only have to eliminate only the non-evidence variables if you instantiate the evidence properly). 1

3. Function Instantiate: Take a factor and evidence as input and instantiate evidence in the factor.

4. Function Product: Take two factors 1 and 2 as input and output 3 = 1 2. 5. Function Sum-out: Take a factor and a set of variables Y as input and output 1 = P y .