Consider the variable elimination algorithm in Sec. $13\mathrm{.}3\mathrm{.}2.$

$($a$)$ Sec. $13\mathrm{.}3\mathrm{.}2$ applies variable elimination to the query

P$($Burglary $|$ JohnCalls $=$ true, MaryCalls $=$ true$).$

Perform the calculations indicated and check that the answer is correct.

$($b$)$ Count the number of arithmetic operations performed, and compare it with the number performed by the enumeration algorithm.

$($c$)$ Suppose a network has the form of a chain: a sequence of Boolean variables X$1,...,$ Xn where

P arents$($Xi$)=\{$Xi$1\}$ fori $=2,...,$ n$.$ What is the complexity of computing P$($X$1|$ Xn $=$ true$)$

using enumeration? Using variable elimination?

$($d$)$ Prove that the complexity of running variable elimination on a polytree network is linear in

the size of the tree for any variable ordering consistent with the network structure.