### Height of an AVL-tree

I came across the following question lately: Show that the height of an AVL-tree is $O(\log n)$.
Read the rest of this entry »

### Expected waiting time

When I’m waiting for the bus, it may happen, that I decide to go home by foot, since it might be faster than waiting for the bus. I told my grandmother that I go home from time to time by foot and she asked me how long this would take. So I told her, normally it takes an hour or so, but sometimes someone who knows me comes by and picks me up.

So I wanted to know the following: When going home, I assume constant speed. Going the whole way takes $L$ hours ($L\in \mathbb{R}$ obviously). There are several cars on the road occurring poisson-distributed with parameter $\lambda'$. Each of these cars has a driver that knows and picks me up with probability $p$.

What’s the expected time to go?
Read the rest of this entry »

### A winamp plugin: Making of

This post shows the basics of writing a very simple plugin for my favourite music player.

There is no special knowledge necessary. A bit of C++, basic experience in Visual Studio, the Winamp SDK some time and patience and a bit of common sense are enough (in my opinion).
Read the rest of this entry »

### Eulerian numbers

Yesterday I came across the following question: How many permutations of $n$ (different) numbers are there, that contain exactly $m$ runs?

A “run” is an ascendins subsequence of the permutation. For example, the following permutation has three runs (seperated by a bar): $3\ 6 \ | \ 2\ | \ 1\ 4\ 5$.
Read the rest of this entry »

### How to algorithmically simulate probabilistic distributions using other distributions

In this article, we explore (in short) how we can generate random numbers of any distribution if we have a corrupt toin coss generator (i.e. a random toin that produces 1 with (unknown) probability $p\in(0;1)$ and 0 with (unknown) probability $q=1-p$).
Read the rest of this entry »

### Geometric distribution “extended”

Everyone knows the geometric distribution, which is used to model “waiting for the first success”. Here, we consider another experiment: We have a Bernoulli random variable with success probability $p$ and $q=1-p$ and we count the number of Bernoulli trials until we have $n$ successive successes (note that $n=1$ is the special case that corresponds to the usual geometric distribution). More precisely, we are interested in the expected number of trials until $n$ successive successes.
Read the rest of this entry »

### Differential equation intermezzo!

Hi all,

I’ve encountered (and solved) the following differential equation:

$\frac{d}{dt}x(t)=-\frac{x(t)}{t}+sin(t)$,

which can be easily transformed into:

$x'(t) \cdot t - t\cdot \sin(t)=-x(t)$

Integrating both sides yields:

$\int_0^t x'(u)\cdot u \ du - \int_0^t t \sin(u) \ du = \int_0^t -x(u)\ du$

We can transform the above to:

$\int_0^t x'(u)\cdot u \ du + \int_0^t x(u)\ du = \int_0^t t \sin(u) \ du$

The left side of the above can be evaluated to $[x(u)\cdot u]_0^t$ (via partial integration) and the right side evaluates to $\sin(t) - t\cdot\cos(t)$ (also via partial integration). Thus, we obtain, that

$x(t)\cdot t=\sin(t) - t\cdot\cos(t)$, from which we conclude that $x(t)=\frac{\sin(t) - t\cdot\cos(t)}{t}$. That’s it.

### Merge shuffle

Following this question on stackoverflow, I came up with the following “merge shuffle” algorithm to permute a linked list. Originally, I had doubts that the results would be distributed uniform, but I discovered that the algorithm gives good results. So I decided to check whether the distribution is indeed uniform.

### Fibonacci numbers “the other way”

Every programmer comes to the point where he or she must/should/wants to implement a programm for calculating fibonacci numbers. But I think my way is quite a new one.

### An Amazon interview question (not completely solved)

Taken from this site:

Given red balls and blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is maximized, assuming that the user randomly chooses a container and then randomly picks a ball from that?