This exercise develops a space-efficient variant of the forward-backward algorithm described in Figure 15.4. We wish to compute P(Xklel,t) for lc = 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 be h = (t + 1)/2. Show that P(Xk can be computed for I; = 1, . . . , h given just the initial forward message fpo, the backward message bh+pt, and the evidence el:,;.

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 thie 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 oft, the length of the sequence. How does this change if we divide the input into more than two pieces?

Figure 15.4