What is the Method of Four Russians in Dynamic Programming?

[evinda]

Hello! (Wave)I am reading about the Method of Four Russians from here.

We divide the dynamic programming table $D$ into $t$-blocks such that the last row of a $t$ − block is shared with the first row of the $t$ − block below it (if any), and the last column of a $t$ − block is shared with the first column of the $t$ − block to its right (if any).

Instead of filling all the cells of the matrix $D$, we just fill the cells that are on the boundary of each $t$-block, so just these that are on the last column and last row of each $t$-block.

We fill firstly the first row and column of the matrix $D$ and then we fill the last row and column of each $t$-block.

We fill these cells with the offset vectors, or not?

These offset vectors consists of the values of the function $\delta$, i.e., the costs of insertion, deletion, match und mismatch, right?

How exactly do we get the optimal alignment-score?

Why can we just fill the cells that are on the boundary of each $t$-block and get in that way the optimal alignment?

 

[Future Bruno]

The Method of Four Russians is an algorithm for solving the dynamic programming problem of computing an optimal alignment between two strings. The idea behind the algorithm is to divide the dynamic programming table into t-blocks, so that only the cells on the boundary of each t-block need to be computed. This reduces the time complexity of the algorithm from O(n^2) to O(nt). The offset vectors used by the algorithm are the costs of insertion, deletion, match and mismatch, which can be precomputed and stored in a lookup table. By computing the score of each cell on the boundary of the t-block and combining it with the offset vectors, the algorithm is able to calculate the optimal alignment-score between the two strings.