Video 3-6: Exhaustive Tabulation Teaser

0:05 The technique we're looking at is um is a general option to somehow slightly speed up things. Um to to one to a certain extent uh you can ask yourself how much can you further speed up the computation of edit distance. We've seen with this assumption that you're only interested in the small values you can you can do something. Um if you're interested in the general problem any kind of strings and you want the precise answer how much can you uh improve upon this textbook undergrad algorithm that we've looked at the dynamic programming one. uh we'll see one one dimension to improve the space usage specifically but keep the running time unchanged next time. Uh another option is to somehow play other tricks and try to speed up the general algorithm while not trying to avoid essentially filling the entire table. And what this what this exhaustive talulation method is uh can in essence be explained with a slightly different problem.

1:17 Uh suppose we multiply boolean matrices. Now this is simultaneously a good and a bad example. It's a bad example because I'm well aware that there's more efficient matrix multiplication algorithms specifically, but let's ignore that. Um, so all of these fancy divide and conquer v varants and and uh the tweaks and twists on those that try to get this exponent down. Um, if I start with an N byN matrix A and I'm interested in their product. The basic method would need cubic time because it has to compute all these uh little products. um every entry in the result is a dotproduct of a a row and a column and in a stupid way the best we can do is spend linear time for each entry. Now again uh ignore the divide and conquer meth methods to speed this up um which are essentially playing with that we're doing multiplications in a specific uh structure on numbers where I also have a subtraction.

2:53 This is uh this is only possible because the numbers I can compute with. um you can modify the problem to not be standard multiplication but some some other um combination of of the entries and then we don't know anything better substantially better than this n cubed but this is really I'm I don't want to get into this really what I what I want to show you is something entirely different and so please just forget about what you learned that you can do this better what can we do without any special knowledge about uh the multiplication but about the fact that it's boolean matrices that the entries are really small and boolean is just the extreme case of that. What you can do is uh split the matrices into small submatrices and I'm going to assign these a size. So this is a t by t submatrix and we'll pick t later.

4:02 uh it's supposed to be square. So that means also this um product matrix consists of these little squares be more smart and just copy it.

4:23 And now uh by virtue of how matrix multiplication works, if I'm if I'm computing this submatrix of the result, I'm essentially uh computing products of submatrices of the input and adding them up. Okay, element wise addition.

5:01 What does that help? Well, because these are boolean matrices, I can make T small enough so that there's not too many different little matrices. There's only 2 to the t * t 2 to the t ^ 2 different little matrices just because they're all zero ones that's the only option. Okay. So if I take two of these and take their product there's also going to be just uh that squared many options for the output. So if I pick my T small enough, and I need a really tiny T, fair enough. But if I pick my T small enough, I can premputee not just all combinations of submatrices from A and B, but all thinkable products of tiny submatrices. And again, this looks bad, but if T is small enough, that's actually negligible. And then every operation here, every product is in constant time on a word ram because I can use uh the indirect address to jump into the lookup table by just taking the entries here and treating them as a number.

6:18 Okay. I'll try to uh make this a bit more clear next time again. But the benefit is instead of having an operation that that used to be t cubed operations for doing these little products, we replace that by a constant operation. And so uh by choosing the right t we can get the overall um the overall cost down divided by some power of logarithm login. Um there's a power there that I forget. And that same trick we're going to try to apply to edit distance.