March 30, 2009

discrete mountains, continuous functions?

One of the first inner geek moments recorded in the wild occurred in Montserrat Spain. If you are ever in the area and have a daytrip to spare, I highly recommend it. Not only is it a monastery in the mountains of features one of the few idols of a black virgin Mary as well as a fairly nice boys choir, they have a fairly fun set of hiking trails. Somewhere in the middle of things, we're probably deep into the part where we lost the trail and are bopping around in some random monk's digs. My mind starts going, and I remember a little trick from YSP back in Chicago.
The day starts with us reaching the base of the mountain at 10am. We hike up and down the mountain. There are switchbacks and sometimes we pick the wrong trail. It makes no difference what path we take, really. We ultimately get just short of the summit and setup camp for the night. We decide that we want to see the sunrise from the peak so we wake up at 6am the next day and hike to the top, where we relax, have breakfast, snap a picture, and make our way back down the mountain.
Rachel overlooking Montserrat

Continuing back down, we take a similar meandering path. Stop to pose for a picture, detour to escape a bear, we might have even left our camera at the top and had to have backtracked to retrieve it. After a grueling day of hiking, we stop at the gift-shop, buy a lousy t-shirt and then ride the tram back down into the city.

The geeky part of this that you can prove that with 100% certainty that there exists at least one time of day for which you were at the exact same altitude on both halves of the trip. More explicitly, there exists a time t in [00:00-23:59] such that f_0(t) = f_1(t) if f_i are functions of your altitude on the respective days of the hike.

Not convinced? Here are a few more clues:
We know that since we started our trip and ended our trip in the same place, so
f_0(00:00) = f_1(23:59)
We also know that we spent the night up in the mountain, so
f_0(23:59) = f_1(00:00)
The kicker is now that both functions f_0 and f_1 are continuous. There was no spot in time that we magically jumped altitudes, it was hectic, scattered even, but continuous nonetheless. Graphing these two functions on top of each other will show you that there is some value of t for which the two functions intersect. Bingo!
For further coolness, you can apply this same argument to the world and weather. One can easily accept that temperature when graphed out is also continuous. This allows me to say:
There exists at least one place (actually an uncountable number of places) for which the temperature at that location and the exact opposite, going through the center of the earth is the same.

but is it an IGM?

i've been talking to people about inner geek moments, and i keep redefining it's definition. not so much in terms of "what is an IGM?" but more like, "this is definitely not an inner geek moment." i guess IGM is in NP. (heh.)

here are some clarifications: is it 'inner geek' moments, or inner 'geek moments'? i posit that everyone has a concept similar to 'inner geek.' but few have inner 'geek moments' and that is exactly what i am trying to catalog.

a few examples to help illustrate my point:
  • having a detailed discussion on continuous functions during dinner does not imply an IGM, this phenomena of geeking out happens often.
  • pondering a seemingly implausible statements using theorems about continuous functions while hiking in the mountains in spain could be seen as an inner geek moment.
(how many times will the words inner, geek, and moment appear in this blog?)

i also want to stress that inner geek moments are not restricted to math and computer science although those subjects tend to dominate mine. giving blood one day led me to this fabled question.

and does it feel weird that in a blog, i'm linking to posts in the future?

March 28, 2009

everyone get in alphabetical order!

we are all familiar with this task; taking an unsorted list and returning a copy sorted by some comparator is something we do in life all the time, as well as one of the most discussed topics in computer science with respect to algorithm cost and complexity. as with many inner geek moments, the question, "is there an optimal solution to this problem?" comes to mind.

when dealt a hand of cards, most people will perform some version of INSERTION SORT. in comparison to other methods of sorting, it's pretty bad (worst case O(n^2) even). luckily a person's actions are weighted very differently from a computers. comparing two (or lots) of elements has almost no cost relative to the amount of time it takes to actually rearrange the cards in their hand. (this is actually one of the reasons that i don't rearrange my cards when playing spades!) this makes insertion sort more along the lines of hO(n) - human O, the rate of growth for a human performing the algorithm.

to further show the difference between O and hO algorithms, see how long it takes you to perform MERGE SORT on a bunch of cards and see how much longer it takes.

another very interesting modification to this scenario is the end of recess in gradeschool. all of the kids get in line, but the teacher tells them to get into alphabetical order. instead of the teacher making comparisons and telling students to move around in line, the sorting happens sort of like this: each student looks at the person in front or behind and they make the decision, "should we switch places." keep doing this until everyone is happy.

as an exercise for my readers (i have readers?!) how much faster is this approach? would you model kids' behaviour differently?

my mission (sorta...)

not much is necessary to have an inner geek moment (IGM)

lots of curiosity, just enough knowledge to be dangerous and sufficient persistence to follow through.

my goal is to embrace (encourage even) these explorations and exercises in an effort to help similarly minded individuals deal with the inevitable question
"hey, "what are you thinking about?"
i actually have a deal w/my wife that compels me to tell her when IGMs occur and explain the topic matter to her.

here we go