This page is about the bachelor course "Communicating Mathematics". Here you'll find a short course description and information on the two topics I did a presentation about during this course.

This course is an obligatory part of the Mathematics bachelor course. It learns the students to effectively communicate mathematical knowledge. This is course is followed with several other students in reasonably small groups (typically around 8 participants).

Under guidance of experienced teachers, all participants must give a presentation about a scientific subject to the other students in his or her group. Each presentation is followed by a discussion about how good (or bad) it went, and how to improve the presentation style. A student will also make notes about this discussion and email them to every member of his or her group; this ensures the lessons learned can be reviewed any time.

Grading will not only depend on the quality of the presentations, but also on how one participates in the discussions and the quality of the notes produced. Also, presence at each presentation is obligatory; under certain circumstances, a fixed maximum number of presentations may be missed though.

My first presentation was about calculating Gamma(1/2). The Gamma function can be viewed as an extension of the faculty function to real and complex numbers, instead of only integers. On a slide I showed the Euler integral version of the Gamma function. In this presentation, I used statistic concepts to calculate Gamma(1/2).

After introducing the integral Gamma function, I moved on to introduce the probability density function (pdf). I remembered the necessary fact that if we integrate a pdf over all real numbers (from negative infinity to positive), the outcome should equal 1. This was also visible on the slide.

Then I introduced the standard distribution's pdf, noting the standard distribution by Z. After seeing this example of a pdf (also on the slide), I moved on to construct a Gamma distribution function. This pdf is equal to the integrand of the integral Gamma function, but normalized so that the integration of the pdf over all real numbers indeed equals 1. Then, substituting x/Beta for the main variable, we obtain the Gamma(Alpha, Beta) distribution, the final equation shown on the slide.

With this Gamma distribution and the standard normal distribution, I calculated Gamma(1/2) as follows. Suppose Y=Z^2. Then, we can make note of two things. Firstly:

P(Y <= y)	=	P(-Sqrt(y) <= Z <= Sqrt(y))
	=	1 - P(Z < -Sqrt(y) - P(Z > Sqrt(y))
	=	1 - P(Z > Sqrt(y) - P(Z > Sqrt(y))
	=	1 - 2 *(1 - P(Z <= Sqrt(y)))
	=	2 * P(Z <= Sqrt(y)) - 1

This shows that the cumulative density function (cdf) of the distribution Y can be expressed in terms of the cdf of Z (which is commonly denoted Phi).

The second interesting thing to note is something we see when we derive the pdf of Y. The cdf is defined explicitly as the integral from minus infinity to x over the pdf. Following the main theorem of calculus, this means that the pdf is equal to the derivative of the cdf. From the above, we know that the cdf of Y, which we will now note by F(x), equals 2*Phi(Sqrt(x)) - 1. In deriving this to x we get the pdf of Y, which we will note by f(x):

f(x) = F'(x) = 1 / Sqrt(x) * Phi'(Sqrt(x)).

Since Phi is the cdf of Z, it's derivative equals its pdf which is given on the slide. Explicitly, it boils down to:

f(x) = 1 / Sqrt(2*Pi) * x^(-1/2) * Exp(-x/2)

Notice the similarity to the Gamma(Alpha, Beta) distribution? Let us try to express f(x) as a Gamma(Alpha, Beta) distribution. We see Exp(-x/2) as the last factor at f(x), so Beta should equal 2. We also see the factor x^(-1/2), so Alpha should equal 1/2. Thus Beta^Alpha will equal Sqrt(2).

Lets us now try to solve Gamma(1/2,2) = f:

1 / (Gamma(1/2) * Sqrt(2*x)) * Exp(-x/2) = 1 / Sqrt(2*Pi*x) * Exp(-x/2)

Noting that on both sides, the factor in front of the exponential are normalization factors, it is obvious that both factors should equal each other. And so, the following equation must hold:

1 / Gamma(1/2) = 1 / Sqrt(Pi)

And thus, Gamma(1/2) is equal to Sqrt(Pi), concluding this presentation.

The second talk was about the 8-queens problem. This problem is about placing eight queens on a chessboard so that no queen can hit any other queen. Queens can move horizontally, vertically and in both diagonal directions.

Three basic algorithms for solving this problem will be treated. However, firstly is noted that we need a data structure to represent the queen's positions on the board. Also it is needed an algorithm to determine whether or not a given solution is valid.

The proposed data structure is a simple one; we use an array of integers of size 8 to represent the problem. The array can ofcourse be accessed by a command like a[i]=b. We let i denote the i'th row on the chessboard, and b the column on which the queen on the i'th row is placed.
This data structure immediatly enforces the impossibility of a solution having multiple queens at the same row. By also demanding that the values that b can take are from a set B={1,2,3,4,5,6,7,8}, and each value from B can only be taken once, we also enforce the impossibility of multiple queens at the same column.
So, in effect, this data structure reduces the queens problem into a permutation problem; we must find a permutation of the array [1, 2, 3, 4, 5, 6, 7, 8] so that a given validation function on this array succeeds.

The first solving method discussed as a genetic algorithm. This algorithm simply randomly interchanges elements of the array, until the array validates as a solution. On the first slide the data structure is shown in an example, the validation algorithm is given and the genetic algorithm is shown.

The second solving method is based on the previous method. It is an evolutionairy algorithm which works with a population of queen positions. At each iteration of the algorithm, a new generation of the population is derived from the old population. This happens by genetic transformations of each array, and, in addition, two old arrays may be combined into a new one.
On each of the resulting new arrays, a scoring function is calculated. In this case, we simply use as the score the number of ways any queen can be hit by another queen. Note that the number of new arrays exceeds the number of old arrays. However, as per the basis of evolutionairy algorithms, our maximum population size is constant; only the best scoring arrays are kept, while the worse scoring arrays are simply discarded. This is a form of survival of the fittest, and thus the scoring function from above is also commonly called a fitness function, and the result from that function on a member of the population is called the fitness score.

An example of the fitness function and a simple genetic transmutation are shown on the second slide. An example of the evolutionairy algorithm is shown on the third slide; only three generations are calculated there.
On a side note, it is true that the genetic algorithm should find a solution; but this may take an undefined amount of time. However, the evolutionairy algorithm can find itself in a loop under certain circumstances, and will then never finish. Most of the time, a large enough population space will prevent such a loop.

The last method we discuss is the depth-first search. This is the most common solution method to this problem. This algorithm will simply choose a column position for each queen at each row, successively. If all queens on all rows have a position, the validation function is performed; if it succeeds, we're done. If not, the algorithm traces back to where it lastly made a choice for a column position, and then tries another position, etcetera.
Note that this method is deterministic; it searches the entire search space exhaustively. This means that if the algorithm finishes without finding a solution, it is certain that there isn't any solution.

The above method has many variations, including the most effective one I know of; the traceback algorithm. That method works largely the same as the depth-first search, but the difference is that the when the algorithm chooses a column position for a queen on any row, it only chooses from valid positions. Thus, the validating happens on-the-fly and not when the entire array is known. Note that this algorithm still is deterministic, and faster than the normal depth first algorithm.