Like this:

In Section 7.4 they talk about using the 4-Russians technique on the longest common subsequence problem.   The short version is that once you subdivide into t by t squares, you need to solve the problem for each vertex on the edges, not just the corners.  But even still you can improve the algorithm from to by taking .   Lest you think that is not much of an improvement, I used Wolfram Alpha to compute these two functions for n=100, and the first is 10,000 and the second is 2171 (approximately).  That is, for n=100 the first algorithm takes nearly 5 times longer than the second one!   And the difference between the two grows as n gets larger (I’ll let you sort that out).

 

In Section 7.5 is some history, which I’ll leave to you to read.

 

 

Advertisement