Wednesday, January 24, 2007

Stop, and think of a better way

People usually underestimate the applications of learning mathematics or computer science in real life. Most math/science people understand the importance of framing a problem. Every problem can be solved in many different ways. Some ways of thinking about a problem make it much easier. Computer Scientists in particular understand that brute force approaches are bad. If something repeatedly fails, we try to re-frame the problem to get unstuck. Let me give a few examples to show what I mean by framing.

Example 1
Let's look at sorting. Most people know how to sort cards they receive when playing cards. Most people use "insertion sort": starting with nothing, they pick (or insert) one card at a time in its right place. It works well when you have 10 cards to sort. But it really doesn't work when you have a hundred or so. One of the things that we learn a lot in CS is how to quantitatively evaluate and compare different ways of solving a problem. In insertion sort, at each step, one has to compare the new card with all the cards currently being held. For example, the last card is compared with every single card that was previously picked. The math is a little tedious (or obvious depending on your background), but given n cards you end up with n x n or n^2 comparisons. So sorting 100 cards this way requires 10,000 comparisons. And sorting 1,000 cards takes 1,000,000 comparisons. Wow, that grows quickly.

Now, most people don't actually compare the card with all the cards they are holding. At each step, they quickly find the spot for the new card by guessing where it should be and adjusting a little. We all do this when we look up something in Yellow Pages or a dictionary. If we're looking for an attorney in the Yellow Pages, we open up the front. And we quickly adjust our guess by guessing again. A more general version of this is called binary search where you cut the problem in half in every step. Binary search is must faster than linear scan. Again, the math is hard or obvious depending on your background, but binary search takes about log(n). So looking through 1000 sorted things for an item only requires only 10 comparisons (because you reduce the problem to 500 items, and then 250, then 125, 63, 32, 16, 8, 4, 2, and finally 1 -- that's 10 steps), as compared to 1000 for a linear scan. Extending the insertion idea above to use binary search instead of linear scan reduces the complexity from n x n to n log (n). For 1,000 cards, we go down from 1,000,000 to 10,000 comparisons. So these are two different and correct ways of doing the same thing. But one is a lot faster. What's needed is having a way to quickly compare different ways of solving the problem.

Example 2
Here is another problem that shows framing. I like this puzzle. Imagine two trains, 100 miles apart, moving towards each other on the same train track. One is traveling 10mph and the other is going at 15mph. Eventually, the trains will crash. There is a super bee traveling at 20mph going back and forth between the trains trying to get the attention of the train drivers. Let's ignore the time it takes for the bee to turn and speed up again. How many miles does the bee travel in its futile attempt to save the trains? A bad way to frame this problem is start adding up all the distances the bee travels. It's hard to count because the trains are moving and the distance the bee travels keeping getting smaller. I'll let you try to do this on your own time. An easy way to frame the problem is to compute how long it takes the trains to crash: 100/(15+10) = 4 hours. Since we know the bee is moving at 20mph, it's easy to figure out that the bee will need to travel 80 miles in 4 hours.

Example 3
Here is my favorite example. Let's say you're on a boat in a river. You are traveling 20mph up stream. The river itself is moving 5mph. Let's say your hat falls in the river at noon and you only realize that this happened at 12:15. How far is your hat and how long will it take you to go back and fetch it? Your hat is now further up stream than where you dropped it since it's been moving at 5mph. [Stop reading here if you want to solve this.] Again, there is a hard way and an easy way. The hard way is pretty tedious since the river is moving. Knock yourself out if you want to do the arithmetic. The easy way is to change your point of reference. Does it really matter that the river is moving in respect to the trees and the land? The only things that matter here is that the boat is moving 20mph away from the hat for 15 minutes. So the answer is obvious. The speed of the river does not matter at all. Thank you Einstein for relativity.

Now, here is a version of the same problem that's easier for people to understand. Let's say you drop your hat on an escalator while you're walking up the escalator. Assume you drop your hat, climb 5 steps, and realize you need to go back to get your hat. It's easy to see that the hat is only 5 steps below. For some reason, we can abstract away the relative moving of the escalator. It doesn't matter how fast the escalator is going or that it's even moving at all. This is easier for people to understand than the previous problem.

Ok, enough examples! Now get to the point

These examples show a few things. First, it's important to frame the problem correctly, to ask the right question, to look at the minimum amount of facts needed to solve a problem. Second, it's important to be able to quickly compare different ways of solving a problem with each other. It's good to experiment and see what works. If you ever have to make 100 peanut butter sandwiches, it's good to take some time and think of a good way. It can save you a lot of time.

Most importantly, I don't understand how people can repeatedly try a brute force approach at solving a problem. When one is stuck or when things are not working as smoothly as expected, it's important to stop and think about a different way instead of trying the old way. Often, trying random new things is better than persistence and banging your head on the wall. In fact, there is a whole field of Randomized Algorithms based on this idea.

I think in the past couple of decades, businesses understood the importance of these things and that's why we started seeing people with PhDs in science and math in board rooms and on trading floors. Maybe in the next few decades, we'll see a similar trend and emphasis in more social disciplines that so far have focused on the soft skills.


Anonymous Anonymous said...

Randomized algorithms is not quite about trying random new ideas, but rather making an algorithm less deterministic, with the goal for it to work well most of the time. Hmm, I think that's what it was. Anyway, randomized algorithms are cool.

12:24 AM  
Anonymous Anonymous said...

Some editing of example 3, about the lost hat on the river and escalator, would make things clearer. Traveling 20mph up stream in a river flowing at 5mph would usually imply the boat is moving at 25mph relative to the water. However, later it says the boat is moving away from the hat at 20mph, implying the speed of the boat is only 20mph. The speed of the water does matter if part of the problem is to convert from one reference frame to another. Isn’t the point of the example to show how converting to the reference frame of the river makes the solution simpler?

11:59 AM  
Anonymous Anonymous said...



6:22 AM  
Anonymous Anonymous said...

warhammer gold warhammer money warhammer accounts tibia money tibia gold tibia item runescape accounts buy runescape accounts runescape money runescape gold runescape gp runescape power leveling runescape powerleveling cheap rs2 powerleveling runescape equipment buy rs equipment runescape runes cheap rs2 runes runescape logs cheap rs2 logs runescape items buy runescape items runescape quest point rs2 quest point cheap runescape questpoint runescape gold runescape items runescape power leveling runescape money runescape gold buy runescape gold buy runescape money runescape items runescape accounts runescape gp runescape accounts runescape money runescape power leveling runescape powerleveling tibia gold dofus kamas buy dofus kamas wow power leveling wow powerleveling runescape questpoint rs2 questpoint Warcraft PowerLeveling Warcraft Power Leveling World of Warcraft PowerLeveling World of Warcraft Power Leveling Hellgate money Hellgate gold buy runescape logs buy rs2 items cheap runescape items Hellgate London gold Guild Wars Gold buy Guild Wars Gold runescape items rs2 accounts cheap rs2 equipments lotro gold buy lotro gold buy runescape money buy runescape gold buy runescape runes lotro gold buy lotro gold runescape money runescape gold cheap rs2 powerleveling eve isk eve online isk buy runescape power leveling rs2 power leveling tibia gold tibia item runescape accounts Fiesta Silver Fiesta Gold Scions of Fate Gold Hellgate Palladium Hellgate London Palladium SOF Gold Age Of Conan Gold AOC Gold ArchLord gold tibia money tibia gold runescape accounts runescape gold cheap rs2 powerleveling buy ArchLord gold DDO Plat Dungeons and Dragons Online Plat

6:55 PM  

Post a Comment

<< Home