CS272:  Prob. Models for AI Fall 2018

Problem  Set 4

Due Sunday February 4, 2018 at 11:55pm

Problem 1. [3 pts] Exercise 9.3 from the book.

Problem 2. [8 pts]

Using the factor code you wrote for the third problem set, write code to perform variable elimination as in algorithm 9.1

Use this algorithm along to calculate the marginals over variable J and over the pair I-J, in the Bayesian network given below. This network is the same as the running ple in the book, except that I (intelligence) has been replaced with T (test-taking ability) and I is now a parent of T, and H (happiness) has been removed.

image.png

image.png


Your algorithm should have running time O˜(nc) where nis the number of eliminated factors and cis the number of elements in the largest factor produced. Note that the key operation is step 1 of Sum-Product-Eliminate-Var. Doing it in O(n) time is not hard. Doing it in O(lg n) requires an index of some form. You may submit an algorithm that takes O˜(n2c), but you will receive a maximum of 6 points.

Your code must be written in C++ and must implement the varelim method of the bn class given by bn.h and bn.cpp (supplied on iLearn with this project). The file vetest.cpp tests your code’s ability to find the marginal over J and the marginal over I & J in the network above.

Your project should run with the supplied factor.h and factor.cpp, which are solutions to the previous programming project. There is no need to change bn.h, so you should not submit a new version. Please do NOT submit any additional files.

To make grading easier, each question is its own “project” on gradescope. Submit your answers to problem 1 for project 4.1 and your code for problem 2 for project 4.2. For problem 4.2, submit onlybn.cpp.