1 This exercise develops a space-efficient variant of the forwardbackward algorithm described in Figure 4. We wish...

1 This exercise develops a space-efficient variant of the forward–backward algorithm 

Transcribed Image Text:

described in Figure 4. We wish to compute P(X e1t) 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 be h=(t+1)/2. Show that P(Xe1t) 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.