Archives

Learned the hard way: Type safety is not everything  May 2, 2015
You may have heard that in Haskell "once it compiles, it works". While this seems to apply in Haskell more than in other languages, a compiling program is not guaranteed to be bugfree, even if you might think so. In this post, I shortly want to showcase an example I experienced and what I hopefully learned from it.

An adventure in Haskell: A simple lambda interpreter  August 2, 2014
I was never an expert of lambdacalculus, but I always wanted to learn (at least the basics of) it. So, I decided to write a very simplistic interpreter for the untyped lambda calculus.

Five ways to solve one of my favourite mathematical problems  May 10, 2014
During my studies, we had to take the lecture "Discrete Probability Theory" which quickly became one of my favourite ones. The day before the exam, I found the following riddle in the internet (see here):
n persons, all of different heights are standing in a queue facing the window of ticket distributor in a cinema hall. What is the expected number of persons visible to the person at the ticket window if each permutation of n persons is equally likely?
Over time, I found some solutions to this problem, and I'd like to present them to you.

A simple lambda interpreter  April 2, 2014
I was never an expert of lambdacalculus, but I always wanted to learn (at least the basics of) it. So, I decided to write a very simplistic interpreter for the untyped lambda calculus.

Expected number of runs in a random permutation  March 28, 2014
My last post was about the expected number of cycles in a random permutation. Today, we'll compute the expected number of runs in a random permutation.

Expected number of cycles in a random permutation  March 20, 2014
Once again a random experiment and an associated random variable: We generate a random permutation and are interested in the expected number of cycles.

Bird tree  March 16, 2014
I came across a very nice method of enumerating the positive rational numbers based on a particular tree. This post explains how this tree is constructed and shows that actually all positive rational numbers are contained in this tree.

A (pure) C extension  March 12, 2014
Over three years ago, I came across a little problem and was able to write a header file for C++ that allowed the programmer two write things like the following:
10 times { do_something_here(); }
This did exactly what you would expect from what it read. Additionally, the implementation had support for an implicitly generated counting variable denoted by a single underscore. The only drawback: It was only for C++.
Now, over three years later, I can claim that I have found a way to implement (at least to some extent) the original thing in pure C.

Finding all paths  October 23, 2013
Consider the following problem: You are given a twodimensional array of integers and you are allowed to place a chess king on one of the arrays. The king can move in any of the eight directions at a time and you want to know how many (simple) paths this king can go that satisfy that the corresponding numbers are strictly increasing and that end in an even number.
As an example, consider the following array:
0 1 2 3
In this array, we have the paths
[0], [0 1 2], [0 2], [1 2], [2]
(strictly increasing and ending in an even number). 
A hiring problem  September 28, 2013
Imagine the following scenario: You want to hire a new employee, and of course you want to take the best candidate. Therefore, you conduct a series of interviews with the candidates one after another. We now impose the following restriction: You have to tell the candidate whether he or she is good enough or not (i.e. if you want to hire him or her) directly after the interview. That is, once you told a candidate you hire her or him, the interview process is over and you do not interview any more candidates. And once you told a candidate you won't hire her or him, this candidate is away and can not be hired anymore. We now consider a strategy to solve this problem: We hire a candidate if he or she is better than the expected value of the best of all following candidates. If there are no more candidates, we have to hire the last candidate.

Vim LatexSuite missing features  October 10, 2011
Since Emacs needs quite an amount of time to start, I decided to give vim a try and am quite happy with it. However, I missed a feature that I appreciated since I came to know it in AucTeX: Showing and browsing the table of contents. So, I implemented a basic table of contents myself.

An interesting bijection  September 11, 2011
I came across the following identity recently: \(\sum_{i=0}^n \binom{n}{i}^2 = \binom{2n}{n}\). This can be proved in various ways. Here, I will describe a "combinatorial proof".

'Addendum: Encoding tuples with numbers'  September 4, 2011
I described how to encode tuples of natural numbers into natural numbers. Now, I wrote (hacked) a small piece in Haskell to try it in practice.
 'Intermezzo: A brainf***interpreter'  August 4, 2011
 A nice property of primes  July 31, 2011
 A very nice proof of existence  July 15, 2011
 A little thougt about how to encode tuples of natural numbers with prime numbers  July 12, 2011
 Messing with skolemization  July 4, 2011
 A quick and dirty unification algorithm  June 30, 2011
 A seemingly simple problem proven hard  April 21, 2011
 Height of an AVLtree  April 21, 2011
 Expected waiting time  February 25, 2011
 'A winamp plugin: Making of'  February 15, 2011
 Eulerian numbers  February 1, 2011
 How to algorithmically simulate probabilistic distributions using other distributions  January 28, 2011
 Geometric distribution "extended"  January 26, 2011
 Differential equation intermezzo!  January 25, 2011
 Merge shuffle  January 24, 2011
 Fibonacci numbers "the other way"  January 24, 2011
 An Amazon interview question (not completely solved)  January 24, 2011
 A little... extension for C++  January 24, 2011
 Emacs regular expressions...  January 17, 2011
 Moved to WordPress  January 17, 2011