Sunday, November 27, 2011

The Khan academy on the foundations of computational complexity

The ones about subtraction said something along the following lines:
"How do you compute 5-3? Here is one way. Say that you have 5 lemons. Here I am drawing 5 lemons. Minus 3 means that you remove 3 lemons. Here I cross them out. How many are left? Let me count: 1,2. There are two lemons left, so 5-3=2." After presenting some other methods based on the number line, he then moves on to the next step: "How do you compute 67 - 34? You could do the same method as before: draw 67 lemons, cross out 34 lemons, and count how many lemons are left. That would work. It would give you the correct answer, but it would take a really long time. So, now I am going to give you a way to do it faster." He then moves on to explaining how to substract the ones digits and the tens digits separately.

The one about multiplications went along the following lines:
"How do you compute 4*3? Here is one way. 3 is 3 cherries. Let me draw 3 cherries on a row. I do this 4 times, so I draw 4 rows that each have 3 cherries. Then I can count: 3+3+3+3 equals 12, so 4*3=12." After presenting equivalent methods, he then moves on: "But what happens if your numbers are really big? For example, if you have 100 lemons, drawing 100 lemons on a row would take a really long time. And if you wanted to compute 100*100 with this method, you'd have to draw 100 rows that each have 100 lemons, and then add them all up: that would take forever. Here, I am going to show you a way to do it fast, even with really big numbers."

One might say: what's the big deal? Of course, when I teach the multiplication algorithm in class, I remark that doing the computation in unary is inefficient, but I always thought: "Why bother mentioning that? Who in their right mind would work in unary?" it hadn't crossed my mind before that there was a natural reason to bring that up, and so my remark goes by unnoticed.

The narrative in those videos is amazing. I am so impressed with this man! He is laying the foundations of asymptotic analysis of algorithms, explained to first graders.