phimuemue

April 21, 2011

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 »

comments closed

February 25, 2011

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 »

comments closed

February 15, 2011

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 »

comments closed

February 1, 2011

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 »

comments closed

January 28, 2011

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 »

comments closed

January 26, 2011

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 »

comments closed

January 25, 2011

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.

comments closed

January 24, 2011

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.

Read the rest of this entry »

comments closed

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.

Read the rest of this entry »

comments closed

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?