Exercise 15.3 [islandexercise]
This exercise develops a spaceefficient variant of the forward–backward algorithm described in Figure forwardbackwardalgorithm (page forwardbackwardalgorithm). We wish to compute for . This will be done with a divideandconquer approach.

Suppose, for simplicity, that $t$ is odd, and let the halfway point be $h=(t+1)/2$. Show that can be computed for $k=1,\ldots ,h$ given just the initial forward message , the backward message , and the evidence .

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

Given the results of (a) and (b), a recursive divideandconquer algorithm can be constructed by first running forward along the sequence and then backward 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.

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?