This exercise develops a space-efficient variant of the forward'backward algorithm described in Figure. We wish to compute P (X k?e l; t) for k = 1... t. This will be done with a divide-and-conquer approach.

a. Suppose, for simplicity, that t is odd, and let the halfway point he h = (t + 1)/2. Show that P (X k?e l; t) can be computed for k = 1. . , h given just the initial forward message f1:0, the backward message bh+1: t, and the evidence e1:h.

b. Show a similar result for the second half of the sequence.

c. Given the results of (a) and (b), a recursive divide-and-conquer algorithm can be constructed by first running forward along the sequence and then backwards from the end, storing just the required messages at the middle and the ends. Then the algorithm is called on each half. Write out the algorithm in detail.

d. Compute the time and space complexity of the algorithm as a function of t, the length of the sequence. How does this change if we divide the input into more than two pieces?

funetion FORWARD-BACKWARD(ev. prior) returns a vector of probability distributions inputs: ev, a vector of evidence values for steps 1,..., t prior, the prior distribution on the initial state, P(Xo) local variables: fv, a vector of forward messages for steps 0,...,t b, a representation of the backward message, initially all Is sv, a vector of smoothed estimates for steps 1,...,t fv[0) - prior for i= 1 to t do fvli)- FORWARD(fv[i 1], ev[i]) for i = t downto I do sv[i]- NORMALIZE(fvi] x b) b- BACKWARD(b, evli) return sv