Thursday, February 03, 2005

Probability

My favorite mathematical topic and well covered by the Cormen, et. al book. Chapter 5 of the book covers this topic in depth and explains applications to the "The Hiring Problem". The most interesting thing is ofcourse is the uniformly random permutation and the exercises built around it.

Randomize-in-place(A)
n <- length(A)
for i <- 1 to n

do swap (A[i], A[Random(i, n)])

The example above demonstrates a uniformly random permutation. See the book and if you need help with the exercise solutions, we can discuss it.

The Birthday Paradox implies that with atleast 28 people, we can expect to find atleast one matching pair of birthdays. But, what about the pigeon hole principle? The pigeon hole principle states that we require atleast 366 people to definitely find one pair of matching birthdays.
Post a Comment