Sunday, January 28, 2007

Beautiful mountains

This is from a few weeks ago while x-country skiing. It snowed the entire day and made it a fun adventure!

Pictures from cross country or snow shoeing

These are some pictures from my few cross country or snow shoeing trips this winter.

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.

Monday, January 15, 2007

Climbing Walls

The big chase scene in 007 is based on an actual discipline called Parkour. It makes skateboarding look like a sissy sport.

Read more
More videos