How does the number of leafs on a tree grow with the height of the tree?

As a was lying on my back in the University park to day, resting a bit between reading papers (more on that later), I looked up at a pine tree and asked myself a very computer sciencey question. How does the number of needles L on the tree grow, as the tree grows taller? If the height of the tree is h, what is the size of L?


I initially thought that surely this must be exponential, after all just think of a binary tree: The number of leaf nodes in a balanced binary tree of height h is 2^h. So maybe:

L \approx 2^h

Read more

Back on my regimen

Sometimes my head hurts from all the papers I have to read. All the lines of software I have to code. All the pages of high quality scientific output I have to write. All the people I have to impress.

At those times I’m a little whiner, a weak quiter, feel so sorry for myself, and blame it all on something stupid like: I must know what going on on Facebook, or in my GMail inbox. I think I need a cup of coffee, a walk, to go to the rest room, to air out, to take of my shirt, put my feet up, not enough blood in the head, or whatever. Whatever keeps me from working.

At those times I’ll watch this video, just once, take a few deep breaths, exhale slowly, and then get to m*therf*cking work on that m*therf*cking Ph.D.

Simulating the Golden Balls game show

In this eposide of Golden Balls, an inspired event takes place:

I retold the event at DIKU APL lunch (nice to have a job where game theory is a valid conversation topic), and we had a conversation about it. At first I thought this was prisoners dilemma, but it was quickly revealed that it is a different game. What is cool about it is, that Nick basically forces Abraham to pick split. I don’t think the same approach would work again though. The person in Abrahams position might be tempted to try a counter-steal. The person in Nicks position might be tempted to actually steal the money, which would be a dirty thing to do, but not completely unlikely.

Read more

Creating visually random images

How complicated does a mathematical function, pseudorandom(x), have to be to create something that seems random, and how do you check whether it seems random? Looking at a long list of numbers is not a good way, because our ability to look at long lists of numbers is very limited. Our ability to look at images is much better.

So, to inspect whether a list of numbers is seemingly random, a fun way is to create an image using the numbers for each pixel, and simply look at it.

Given a number x in the series {0, 1, 2, …, huge n}, let’s create an image that plots a random function that’s implemented using the sin() function and a 3rd degree polynomial function:

color_range = 2**8
a = -3.0
b = -5.0
c = 13.0
def pseudo_randombit(x):
	color255 = math.sin(a*x**3 + b*x**2 + c*x) % color_range
	# make black/white
	bit = color255 / 127
	return bit

Read more

Never forget your password again, version 1

The recommended practice is to have different passwords on different websites. But how do you remember all those passwords without storing them somewhere? The tricks is, you don’t. You remember a single strong password, and use a mechanism to generate other passwords from that.

This is not for securing government secrets, but should work for your twitter account.

Create a single very strong password

There are many ways to do this:

Read more

Low tech male/female voice detection system

I was drinking a bootle of water, while listening to a group of people having a debate. As the water level sunk, I noticed something. In the beginning the bottle would resonate/vibrate when the people with higher pitch voices talked. When the bottle was nearly empty, it would resonate/vibrate (and more so) when people with bassier voices talked.

Using bottles of water (with different waterlevels) and a vibration sensor on each, one could make a low tech thing that detects whether a male or female is speaking in the room. Why not use a microphone and a spectrum analyzer? Well, because you are McGyver and you’re caught in some prison, and mission dictates that you find out when the guy with the really bassy voice enters the room. You know, ad hoc spy stuff.

Here is a figure that illustrates the “Low Tech Male/Female Voice Detection System”:

Saving output from ‘text to speech’ to a file on Mac OS X

In terminal you can write something like:

say 'hello world'

Which will make your computer talk. To save the audio output to a file, use the -o option. A full example is:

say -o hello.aiff -v 'Alex' 'Hello, my name is Alex'
open hello.aiff

This will say ‘Hello, my name is Alex’, in the voice of ‘Alex’ (other voice-options are ‘Bruce’, ‘Fred, ‘Kathy’, ‘Vicki’ and ‘Victoria’), and save the output to ‘hello.aiff’.

It seems there is no option for setting the speed (can be set in System preferences -> speech). See man say for all options. Interesting options include sending the output over the network.

Finding a route from one wikipedia page to another

Here’s a game I like to play. Select two wikipedia pages at random, and find a route from one to the other. I stated a theorem once that:

you can get from any page on wikipedia to the page on pollination in 7 steps or less. (it was actually another page, but let’s say it was pollination)

I devised a method for doing this using Google search. Let’s call the random page s, and the page you want to reach t, e.g. pollination. A given page on wikipedia has a set of incoming links (other pages linked to the page), and a set of outgoing links (other pages linked to by the page). Let’s call these two sets in[p] and out[p]. These two sets contain direct decendants and ancestors of p respectively.

Read more