Doors Problem

Problem:
There are N doors in a hallway all closed. There is a robot that iterates through every ith door and it is programmed to invert that door’s state. After i=N the robot stops. For i=1 the robot opens all the doors. For i=2 all even doors get closed. For i=3, door 3 gets closed and door 6 is opened etc. Which doors are left open after the robot is done going through all the doors?

Solution:
I knew that once an ith door was reached whatever state it received became it’s final state. Which means door #1 is always open and doors #2 and #3 are always closed.
It wasn’t immediately obvious to me which doors would remain open, so I wrote a little python program to help me see a pattern.

Output
1.00^2 2.00^2 3.00^2 4.00^2 5.00^2 6.00^2 7.00^2 8.00^2 9.00^2 10.00^2 11.00^212.00^2 13.00^2 14.00^2 15.00^2 16.00^2 17.00^2 18.00^2 19.00^2 20.00^2 21.00^222.00^2 23.00^2 24.00^2 25.00^2 26.00^2 27.00^2 28.00^2 29.00^2 30.00^2 31.00^2

Clearly the pattern is obvious. The mathematical reason why this is so is more interesting than a simple empirical trend. Every integer has an even number factors… except squares.
4:1,2,4
6:1,2,3,6
7:1,7
8:1,2,4,8
9,1,3,9

This is because the singleton factor is it’s own factor pair.

Windows NT Startup Process

I while back I wrote about the fact that I didn’t really know how Windows startup works. As with many things wikipedia clears it all up. It looks like this is what I should have examined in the registry:

Now I know.

Bridge Crossing Puzzle

I was reading Introduction to the Design and Analysis of Algorithms book and found a neat puzzle.

Problem:
There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses either 1 or 2 people must have a flashlight. The flashlight must be walked back and forth, cannot be thrown. Person 1 takes 1 minute to cross. Person 2 takes 2 minutes. Person 3 takes 5 min. Person 4 takes 10 min. A pair must walk together at the slower person’s pace. For example if person 1 walks with person 4 it takes 10 minutes for both of them to cross. If person 4 takes the flashlight back, a total of 20 minutes has elapsed and the mission failed.

Solution:
The most interesting part to me is the concept. You want to minimize the impact of the two slowest walkers, you try to avoid having either of them make more then one trip. You can mitigate the 5 min walker by sending him with the 10 min walker. The second optimization you try to do is decrease the “bringing-the-flashlight-back” time, so the fastest people should bring it back.

———– symbolizes the bridge the bridge
0) ———– 1 min 2 min 5 min 10 min
1) 1 min 2 min ———– 5 min 10 min
Time: 2
2) 2 min ———– 1 min 5 min 10 min
Time: 3
3) 2 min 5 min 10 min ———– 1 min
Time: 13
4) 5 min 10 min ———– 1 min 2 min
Time: 15
5) 5 min 10 min 1 min 2 min ———–
Time: 17

tailor svn to hg

I few weeks ago I discovered tailor. After installing the latest tarball. Following this tutorial I was able to checkout from a svn repository from work into my hg repo. I was not interested in pushing back changes, in my case the project ended, however it should be easy enough to do.

I called my config file: projectname.tailor

At the terminal:

This will create two directories in /home/me/projectname/ hgside and svnside.

XeLaTeX fun

After reading this post I wanted to dabble with TeX again. I haven’t used it since university days so I thought it was time to polish off the rust. I am on a Debian box, so these are the steps I took to get XeLateX to work.

After about 20 minutes I had everything set up and was ready to follow the tutorial.
My sample.tex file looks like this:

Now to make sure everything works…

Success!
Next time I’ll create something a little more substantive.

Things that surprised me

These are concepts from Math,Comp Sci, Physics that have surprised me over the years:

Recursion
My first formal introduction to recursion was through Fibonacci numbers. While the uses of these numbers are quite surprising( i.e. Euclidean algorithm’s running time ). I was never really impressed with them. They seem simple enough. What really floored me about recursion, was the solution of the Tower’s of Hanoi problem and subsequently the 8 Queens problem. On the surface they seemed so difficult to write a good simple solution for but where made almost trivial with recursion. Recursion still amazes me today.

Mathematical Induction

Induction ties into recursion above, but it needs it’s own category in my list. Induction did not even seem fair when I first learned it. It was as if I was cheating. I could prove statements that I knew almost nothing about with minimal effort just by slogging through the algebra steps. At the end I still felt like I haven’t really grasped the problem. A good example at the time was the sum of cubes.

Lambda Calculus
If there is one good way to study recursion it’s lambda calculus. This field has augmented my understanding of every single item bellow and still continues to. From combinators to formal renaming schemes to deriving natural numbers(more on this later).

Lisp
I have learned as much about Computer Science from this language as I did with everything else I’ve encountered in this field combined: Functional Programming, OO, macros, closures, higher order functions, bottom-up programming, parsers, syntax. Each of these areas has either been completely revolutionized in my head or planted there, where before was nothing.

Dedekind Cuts
I have never imagined that it’s possible to derive Real and Complex numbers out of Integers. What an amazing feat (see: Foundation of Analysis by Landau).

Derivatives and Integrals
These two things are reason I decided to also get a Math degree. I really wanted to understand why and how these work.
I remember what I thought when I saw derivatives in high school like it was yesterday. “So I take a function f(x) change an argument I am passing to it to x+h where h is so small that I can never write down a number y greater than zero that is smaller than h. Subtract f(x) and then divide this sum by another effectively zero “number” and I get rate of change with respect to x. Great!” Once that became clear, I ran into another issue.

The situation got worse with Leibniz notation. I could do things like “cancel out” infinitesimals (dx/dt)*(dt/dy)=dx/dy but I could not do this with derivatives with a higher order than 1. Makes perfect sense!

For integrals it was worse. “I take f(x) multiply it by something that makes no sense by itself and add up all the columns in the interval and BAM!… I got the function I was looking for. Great!”

Taylor’s Theorem
I was delighted when I found this was possible. I always wanted to prove it. When I finally got to in Real Analysis and was able to prove it, it was one of the most satisfying experiences of my college career.

Fourier Series/Transform
This started in my Differential Equations course and made worse by my Signals and Systems EE class. In DEq I was told about Laplace transforms. In EE I was told about FTs. I had no idea how these could possibly work. Fourier series was also quite disturbing. If I add a bunch of infinitely smooth functions I can get non-smooth ones. This was a pretty big deal. These transforms are still on my list to prove.

Lagrangian and Hamiltonian Formulation of Newtonian Mechanics

I am still working on these concepts. I was never satisfied by their explanations in class. You’ll have to watch the Sussman lecture to understand why.

Noether’s theorem
Out of all the physics discovered this in my mind is the most amazing theorem. Even in simplified form I am in awe.

Of course the list has more entries but these are my top 10.

aria2 download tool

I ran into an interesting downloading application, Aria2. I was reminded of a GetRight utility I ran into years ago. The thing I really liked about GetRight at the time was the ability to download linux ISOs from multiple mirrors and merge the results into one coherent file. It really sped up downloading new Slackware releases :-) This to me is the most compelling feature of Aria2 and it works thus:

The main page has plenty of examples with many different transfer protocols. Too bad the parallel download features seem to have disappeared with the invention of bit torrent.

Countable Rational Numbers

In my Real Analysis class in college I remember seeing the proof that rational numbers are countable via a diagonalisation argument. Proving something is true and implementing a counting algorithm that will assign any given Rational a unique positive integer are two very different things.

This link is class room explanation behind all the math without dumbing anything down. Here’s the original amazing paper by virtue of simplicity and elegance. The only things needed to understand it is the most rudimentary understanding of binary trees and Euclid’s gcd algorithm.

I wrote up some scheme code to print out the “parents” of the node, which allows one to assign a unique positive integer to every/any Rational.

Sussman Thought Process

I found a great lecture by Gerald Sussman about thought processes and computers. I stumbled upon it when reading about the Feynman algorithm of solving problems.
The Feynman Algorithm:

1. Write down the problem.
2. Think real hard.
3. Write down the solution.

His talk about Structure and Interpretation of Classical Mechanics reminds me of a quote by Knuth: “Science is what we understand well enough to explain to a computer. Art is everything else we do.”

World Magnetic Model

In about a dozen or so math courses I remember having to prove (always by induction) that the sum of N numbers (1+2+3+…+N) is equal to n(n+1)/2 and always thinking, this is pointless. I stand corrected.

At work I was tasked to calculate magnetic declination using java instead of the C implementation NOAA used. The program is pretty much a function: MagDec:(double,double,double)->double (elevation,latitude,longitude)->magnetic_dec. A key component used to calculate the declination is a file with spherical harmonics gathered by satellites. It looks something like this:

My goal was to create S = G(m,n) – G_dot(m,n) and C = H(m,n) – H_dot(m,n) for each value of m and n.
Since Java IO isn’t the most convenient thing in the world, instead of sscanf() I was forced to use java.util.Scanner, which IMO is not nearly as convenient for this type of data organization.
I realized that if I have a flat list it looks something like this:

Written in a different way:
G(1) G(2) G(3) … G(12)
2 3 4 … 13

which means there are 13(13+1)/2 – 1 coefficients for G. If I am presented with a single column of numbers like Col B. and I want to pick G(2,1) all I need to do is is realize that there are 3(3+1)/2 coefficients up to G(2,2) which means G(2,1) is 3(3+1)/2-1. Of course it would’ve been a lot easier if I could do the straightforward thing easily like: