Geeky is Awesome

Why multiplying a fraction by 100 gives the percentage of the fraction

2012-02-12T10:21:00.000+01:00

I remember I had this curiosity about why it is that when you multiply a fraction by a number you get that fraction of that number. Why is it that 1/2 × 5 gives half of 5? Why is it that you find the percentage from a fraction by multiplying that fraction by 100? Why is it that multiplication should have this property?

Percentages

As you should know, if for example you have a 10% income tax, that means that out of every 100 units of income you make, 10 units of them are taxes. So a percentage means the number of units you need to take out of every 100 units of a total. This is why it's called "percent", that is, "per hundred", because you are finding the amount of units you need to take our of every hundred units in the total.

However we can also express this statement using fractions instead of percentages. We can just say that 1/10 of your income is taxes. In fact we can convert fractions into percentages by multiplying the fraction by 100, 1/10 × 100 = 10, that is 10%.

The reason why we convert fractions to percentages by multiplying the fraction by 100 is the following:
Given a fraction a/b, when we convert it to a percentage, we are changing the denominator of said fraction to 100, leaving the fraction equal to a/b, and taking the numerator. So a/b becomes p/100 and p is the percentage.

We are finding a number which when divided by 100 gives the original fraction and therefore the amount of units you need to take from every 100 units of a total such that when you divide the amount you took by the total, you get the original fraction.

If you think about it, the fraction a/b means two things:

b is the number of equal sized parts to divide the total and a is the number of such parts to take.
a is the number of units to take out of every b units from the total.

For example, if we want to take 3/4 of 20,

We can either break 20 into 4 equal parts and take 3 of them:
20 = 5 + 5 + 5 + 5 (4 equal parts)
take 3 of the parts and we have
5 + 5 + 5 = 15

Or we can take 3 from every 4 in 20:
20 = 4 + 4 + 4 + 4 + 4
take 3 from every 4 and we have
3 + 3 + 3 + 3 + 3 = 15

In general, if we want to take a/b of T,
T = T/b + T/b + T/b ... (for b times) (b equal parts, that is, T/b × b which is equal to T)
take a of the parts and we have
T/b + T/b ... (for a times) = T/b × a

Or we can take a from every b in T,
T = b + b + b ... (for T/b times) (that is, b × T/b which is equal to T)
take a from every b and we have
a + a + a ... (for T/b times) = a × T/b

So as long as you accept that T/b × a = a × T/b, you must accept that the two statements are equal.

If you add to the mix that T/b × a, a × T/b and T × a/b are all equal to (T × a)/b, then you also know that T/b × a = a × T/b = T × a/b. So both statements are also equal to T × a/b which is what we're trying to prove in the first place.

For example, if you have a total of 50 units and you want to take 1/10 of the total, the number of units you must take from the total, when divided by 50 must result in 1/10. Likewise, if we change the denominator of the fraction to 100, that is, 10/100, then we say that 10% of 50 units is the number of units we must take such that when it is divided by 50 we get 10/100 (which is equal to 1/10).

Percentages are useful because we would be standardizing the denominator of fractions in order to make them easy to compare. If we wanted to compare 2/4 to 4/16 we can change the denominators of both fractions to 100 (50/100 and 25/100 respectively) and then we will only have to compare the numerators in order to know by how much one fraction is bigger than the other.

So what we're doing is finding another fraction which is of the form p/100. However, p/100 must equal a/b in order to remain the same fraction.

So we have the equation a/b = p/100
We want to find p, so p = a/b × 100 (multiplied both sides by 100)

So if we want to express 2/4 as a percentage,
2/4 = p/100
p = 2/4 × 100
p = 50
So 2/4 = 50/100 or 50%.

I think that the percentage sign "%" can be treated as a symbol representing the constant "1/100". Which means that 50% = 50 × 1/100. This makes sense as in order to go from percentage to fraction form you just change the % back to 1/100 and calculate the expression. 50% = 50 × 1/100 = 1/2.

And this is why percentages work this way.

In general

Now we can generalize this to numbers other than 100. If we use "c" instead of "100",
a/b = p/c
p = a/b × c

By changing the denominator to c, the numerator p will be the amount of units you need to take out of every c units of a total, such that when you divide the amount you took by the total, you get a/b. But usually we multiply a number by a fraction just to find that fraction of that number. So more simply, p is the number which when divided by c, gives a/b.

So 1/2 × 5 gives us the number which when divided by 5, gives us 1/2. Hence the answer, 2.5, is half of 5 because when it is divided by 5, the result will be 1/2, or, when 2.5 is multiplied by 2 the result will be 5 (by definition, when you double half of 5 you must get 5 again).

So really all we're doing is simple subject of the formula.

A more complete proof that the square root of 2 is irrational.

2011-11-07T10:03:00.000+01:00

I don't know about you but I never quite liked the usual proof by contradiction that the square root of 2 is irrational. It seems incomplete in some way. I never felt convinced by it. Here's what I feel is the missing piece of the puzzle.

Assume that the square root of 2 is rational. So,
√2 = a/b
=>
2 = (a/b)^2
=>
2 = a^2 / b^2
=>
2 b^2 = a^2

So far so good. The usual proof continues with the following statement:

Since a^2 is equal to a natural number multiplied by 2, a^2 is an even number. But for a^2 to be even, a must be even too (see proof in the appendix at the end). So that means that there is a natural number k where a = 2k.

Since a = 2k and 2 b^2 = a^2,
2 b^2 = a^2
=>
2 b^2 = (2k)^2
=>
2 b^2 = 4 k^2
=>
b^2 = 2 k^2

Just like for a, b must also be an even number.

The proof usually ends right there, claiming that since a and b are both even numbers, then the fraction a/b is not simplified and irreducible, contradicting that a/b exists. But let's see where the proof takes us if we just keep on going.

If both a and b are even, then the fraction a/b can be simplified by dividing both a and b by 2, that is, if a = 2k and b = 2l, then we can say that √2 = k/l. But after doing this we can reapply the same reasoning on k and l and we'll discover that k and l are also both even numbers, and we can do it again and again ad infinitum.

So, which natural numbers can be divided by 2 infinitely? Only 1 number can do that, zero. But replacing zero for both a and b will not make their quotient a real number, or if you want to define 0/0, it will not result in a number whose square equals 2. So there is no fraction a/b which gives √2.

So there you have it, a proof that goes on till the end.

===========================
APPENDIX
Now on to the proof that an even square can only come from an even number squared:

Let a^2 be an even number.

a can either be even or odd, that is there must exist an n where
a = 2n or a = 2n + 1
If a = 2n, a^2 = (2n)^2 = 4 n^2 = 2(2 n^2), which is an even number
If a = 2n + 1, a^2 = (2n + 1)^2 = 4 n^2 + 4n + 1 = 2(2 n^2 + 2n) + 1, which is an odd number

So an even number squared will give an even number and an odd number squares will give an odd number. Hence, a square even number can only come from an even number squared.

Wisdom hierarchy vs Bloom's taxonomy

2011-11-02T14:42:00.001+01:00

So lately I've been reading about two subjects that I noticed are very related, the Wisdom hierarchy ( http://www.systems-thinking.org/dikw/dikw.htm) and Bloom's taxonomy (http://www.odu.edu/educ/roverbau/Bloom/blooms_taxonomy.htm). First I need to explain each.

Wisdom hierarchy

This is a hierarchy of how wisdom is obtained and describes the relationship between data, information, knowledge, understanding and finally wisdom.

Data

Data is symbols and signals which can be observed and analysed, but perhaps not be processed and organized.
An example of this is seeing the symbols "3", "×", "4", "=" and "12". Those symbols may not mean anything to you if you don't know arithmetic.

Information

Information is data which is given meaning and use. It answers "what", "where", "who" and "when" questions, that is, simple shallow questions. It is when relationships are formed between the different data and context is given to the data. The data has meaning but perhaps it cannot be used.
So now "3×4=12" has a meaning. It means that if you multiply the numbers 3 and 4, the result is equal to 12. You may know what the symbols mean but you may not be in a form that is useful.

Knowledge

Knowledge is a mass of information which is organized in a way to be useful. It answers "how" questions, that is how can I use the information. The information may be useful but perhaps you don't understand why it is related and how to generate new information from it.
So now we have organized every multiplication of two numbers we learned into a multiplication table. If we want to know what a particular multiplication equals, we know how to do that, we simply look it up our multiplication table. You may know how to multiply numbers together but you may not know why when numbers are multiplied they give a particular number as a result.

Understanding

Understanding is when you understand the knowledge, when you find a pattern to the organization and can use the pattern to generate new information. It answers "why" questions, that is, why is the information organized as it is in the knowledge. The knowledge may be understood but perhaps it cannot be judged and compared with other knowledge.
So now we understand that multiplication is repeated addition. Now we can add to our knowledge new information which is generated from our understanding rather than from the external world (such as having to ask someone). You may understand how to do multiplication but you may not be able to compare different methods to doing multiplication.

Wisdom

Wisdom is when you can pass judgement and make decisions to determine what is the best method to use. The question it could answer is "which" questions, that is, which is best.
We now can decide which method we should use to multiply two numbers, be it by looking up the multiplication table, by repeated addition or by long multiplication.

Bloom's taxonomy

This is a way of categorizing exam questions in a hierarchy such that as you go up the pyramid, the higher the level of thought required to answer the question.

Remembering

Remembering type questions are those that only require the student to remember things, without expecting any understanding.
An example question would be "What does the symbol × represent?".

Understanding

Understanding type questions are those that require the student to know what the things they know actually mean.
An example question would be "Explain what the expression 2×3=6 means in your own words.".

Applying

Applying type questions are those that require the student to be able to use what they know in a situation.
An example question would be "How many apples would you have if you had 2 baskets with 3 apples in each?".

Analyzing

Analyzing type questions are those that require the student to break down a problem into parts and see how they are related to each other.
An example question would be "What is the next number in the sequence 21, 42, 63, __".

Evaluating

Evaluating type questions are those that require the student to justify a decision.
An example question would be "Which multiplication method would you use to multiply 128 by 64 and why?".

Creating

Creating type questions are those that require the student to create something new to the student.
An example question would be "If all you have is the product of the sum and difference of two numbers and one of the numbers, how can you find the other number?".

Together

It is clear that there is a relationship between the two hierarchies. We could say that:
Remembering type questions test the student having memorized data.
Understanding type questions test if the student has derived information from data.
Applying type questions test if the student has developed a useful knowledge from the information and if the knowledge can be readily used.
Analysis type questions test if the student has understood the basis of their knowledge and can derive new information from it.
Evaluating type questions test if the student has obtained any wisdom on the subject and hence can make sound judgement about it.

The last question type, creating, is not covered by the Wisdom hierarchy and perhaps it predicts yet another higher level form of cognition, perhaps called "creativity", which is when you use knowledge, understanding and wisdom together to derive new knowledge, understanding and wisdom, where knowledge provides the raw material to act on, understanding provides the ways to rearrange the knowledge and wisdom guides you into choosing a solution path which is most likely to give good results. Once this is done you will have learned from experience and would have added new knowledge, a deeper understanding of that knowledge together with new ways of using it and you would be able to make better judgement in the future.

A lousy tutorial to C# drag and drop

2011-09-19T01:07:00.002+02:00

Drag and drop is a neat way to allow the user the "transfer" data into a winform control. Here's how to enable drag and drop in a windows form in C#:

1. Create your source and target controls. In this case we're using 2 ListViews where the one on the right (called listView1) is the source of the drag and the one on the left (called listView2) is target of the drop. However note that the source of the drag can even be from the windows explorer by drag dropping a file into the control.

2. Set the AllowDrop property of the control which will receive the drop to true.

3. Set up an event in the control which will be dragged from, that senses that a drag has been initiated, such as the ItemDrag event or the DragLeave event and call the DoDragDrop method. The DoDragDrop method is to be passed the data to be transferred (the object you want the receiving control to get).

4. Set up the DragOver event in the control which will be dropped on, to check if the data being dragged over can be accepted and change the cursor to an invalid cursor picture if not. You can check the type of the data being dragged by using the GetDataPresent method.

5. Set up the DragDrop event in the control which will be dropped on, to actually do something with the data once it has been dropped. This event will only fire if the DragOver event did not set Effect to None.

And there you have it. A lousy tutorial. However, here's something worth mentioning:

If you are transferring an object which could be one of several types and you want to view the object as its base type, then this will not work, as the GetData method will just return null if you pass it a base class for a type. The only was I found to get around this was by created a proxy object which will contain the object of interest casted as its base class, and then what you receive the proxy object in the receiving control you just get the object of interest from it. Like so:

Quicksort partitioning

2011-07-17T16:25:00.001+02:00

During my years in school and at university I was always exposed to only one algorithm of quicksort partitioning. Let's take a look at some ways to partition a list for sorting.

Quicksort

Quicksort itself works by taking a list, picking an element from the list which is referred to as the "pivot" and splitting the list into two sub lists, the first containing all the elements smaller than the pivot and the second containing all the elements greater than the pivot. Once you have these two sub lists you can sort each one independently of the other since elements in one list will not be moved into the other after the sort is complete.

This splitting into two lists is called "partitioning". Partitioning once will not sort the list but it will allow you to either use a different sorting algorithm on each sub list (partition) or to recursively partition the two partitions until you end up with a partition of 1 or 0 elements, which is necessarily sorted.

For example, partitioning the list [7,3,6,4,1,7,3] using 4 as a pivot will give us a first partition of [3,1,3] and a second partition of [7,6,7]. The pivot itself, along with other duplicates of it, may or may not go in one of the partitions, depending on how the partitioning is done. If it does not go into one of the partitions, then the sort will place the pivot between the 2 partitions after they have been sorted.

Partitioning by filtering

The most intuitive way to partition is by creating 2 new lists, going through the unsorted list and copying elements from the unsorted list into one of the 2 lists. This is memory expensive however as you end up needing twice as much space as the unsorted list takes. The following partitioning algorithms are "in-place" and hence do not need any new lists.

Partitioning by moving the pivot

This is the partitioning algorithm I was familiar with at school. It's quite intuitive but slow when compared to the next algorithm. The way this works is by putting the pivot into its sorted place, that is, the place where it will be after the whole list has been sorted. All the elements smaller than the pivot will be on its left and all the elements larger than the pivot will be on its right. Therefore you would have created 2 partitions, the left side of the pivot and the right side.

The algorithm uses a pivot pointer which keeps track of where the pivot is and an index pointer which is used to compare the pivot to other elements. The pivot pointer starts by being at the right end of the list (you can choose a pivot and swap it with the last element if you don't want to stick to the element which happens to be there) and the index pointer starts by being at the left end of the list. The index moves towards the pivot pointer until it encounters an element which is not on the correct side of the pivot, upon which the index and the pivot and swapped and the the index pointer and pivot pointer swap locations. Once the index pointer and pivot pointer meet, the pivot is in its sorted location and the left and right side of the pivot are partitions.

Pseudo code:

function partition(arr, left, right)
  pivotPtr = right
  indexPtr = left
  while pivotPtr != indexPtr
    if indexPtr < pivotPtr //if index pointer is to the left of the pivot
      while arr[indexPtr] <= arr[pivotPtr] and indexPtr < pivotPtr
        indexPtr++ //move index pointer towards the pivot
      if indexPtr < pivotPtr
        swap(arr[indexPtr], arr[pivotPtr])
        swap(indexPtr, pivotPtr)
    else //if index pointer is to the right of the pivot
      while arr[indexPtr] >= arr[pivotPtr] and indexPtr > pivotPtr
        indexPtr-- //move index pointer towards the pivot
      if indexPtr > pivotPtr
        swap(arr[pivotPtr], arr[indexPtr])
        swap(pivotPtr, indexPtr)
  return pivotPtr

Partitioning by dividing

In the previous partitioning algorithm, we had to constantly swap the pivot in order to eventually put it in its place. This is however unnecessary as partitioning does not require the pivot to be in its sorted place, only that we have 2 partitions, even if the pivot itself is in one of the partitions (it doesn't matter in which one as it could be eventually placed in its sorted place in either partition).

This time we will not care where the pivot is, as long as we know its value. We will need 2 pointers, a high and a low pointer, which will be moving towards each other. The low pointer will expect to encounter only elements which are smaller than the pivot and the high point will expect to encounter only elements which are larger than the pivot. When both pointers encounter a wrong element, they swap the elements and continue moving towards each other. When they eventually meet, all the elements to the left of the meeting point will be smaller than or equal to the pivot and all the elements to the right of the meeting point will be greater than or equal to the pivot.
Since both pointers will be moving toward each other before swapping, this algorithm will do less swaps than the previous one and hence will be much faster. In fact a simple experiment will show that it does half the number of swaps.

Pseudo code:

function partition(arr, left, right, pivot)
  lo = left
  hi = right
  while lo < hi
    while arr[lo] <= pivot and lo < hi
      lo++ //move low pointer towards the high pointer
    while arr[hi] >= pivot and hi > lo
      hi-- //move high pointer towards the low pointer
    if lo < hi
      swap(arr[lo], arr[hi])
  /*
    Since the high pointer moves last, the meeting point should be on an element that is greater than the pivot, that is, the meeting point marks the start of the second partition.
    However if the pivot happens to be the maximum element, the meeting point will simply be the last element and hence will not have any significant meaning.
    Therefore we need to make sure that the returned meeting point is where the starting point of the second partition is, including if the second partition is empty.
  */
  if arr[lo] < pivot
    return lo+1
  else
    return lo

Negation Introduction

2011-06-02T10:58:00.000+02:00

When I was in university, one of my favorite units was Mathematics of Discrete Structures lectured by Dr Gordon Pace. In propositional logic, we learned about the negation introduction rule of inference which was this:

P => Q, P => ~Q
---------------
     ~P

and which was used like this:

1.  | P   Assumed
... | ...
10. | Q

11. | P   Assumed
... | ...
20. | ~Q
21. ~P   Negation introduction from lines 1-10 and 11-20

In other words, if P implies that Q is true and also P implies that Q is not true, then P must itself not be true.

I never actually understood the logic behind it however. We were told that this how a proof by contradiction works. An example of a proof by contradiction, in words, is this:

If it were raining, the streets would be wet. But the streets are not wet. Therefore it is not raining.

The fact that if a particular proposition is true, it would lead to another proposition which we know is false, implies that the first proposition must itself be false.

The problem with the rule of inference we used for negation introduction is that the way I interpret it linguistically is not at all how a proof by contradiction is usually told. If we had to turn the rule of inference into words, it would be this:

If P implies that something is both true and false, then P is itself false.

A rule of inference which is closer to a proof by contradiction would be this:

Q, P => ~Q
----------
    ~P

which would be used like this:

...
10. Q
11. | P    Assumed
... | ...
20. | ~Q
21. ~P     Negation introduction from lines 10 and 11-20

This is closer to a proof by contradiction.

If P implies something which is not true, then P itself is not true.

The question is, can we use this new rule of inference instead of the usual one?

When can the usual rule of inference be more powerful than the proposed one? Only when both Q and ~Q can ONLY be derived using P. Hence P must be assumed in both cases which cannot be done with the proposed rule of inference.

But this can easily be solved by using the lemma Q /\ ~Q => X and tautologies. If P can derive both Q and ~Q, then we can also derive Q /\ ~Q from which further derive anything we want, including something false. Worst case, if we don't know what to derive which is false, we can derive the negation of a tautology, such as ~(A => A). A => A is a tautology and we can always just insert it in a proof.

So using this trick, we'd do the following:

1.  | P          Assumed
... | ...
10. | Q
... | ...
20. | ~Q
21. | Q /\ ~Q    Conjunction introduction from lines 10 and 20
22. | ~(A => A)  Q /\ ~Q => X lemma from line 21
23. A => A       A => A lemma
24. ~P           Negation introduction from lines 1-22 and 23

And therefore, where ever we can use the usual rule of inference, we can also use the proposed rule of inference.

QED :)

Artificial Intelligence

2011-04-22T09:47:00.000+02:00

This is an essay I wrote back when I was in university about artificial intelligence. I decided to put it up in my geek blog. Enjoy! By the way, I later learned about the halting problem which makes my last paragraph impossible to be realized if the program is expected to be right every time.

Artificial Intelligence

Intelligence is the ability to do something without previously knowing how and use the new knowledge on other problems, or rather, to learn without being taught. Someone who is stupid and therefore not intelligent is someone who requires instructions in order to do (apparently) everything, much like a computer. So what is artificial intelligence? How can a computer simulate this process?

Well if this is possible then it would imply the end of programming, since essentially there would only be one program which will learn how to do anything the user wants. So basically an intelligent program has 3 phases: You tell it what you want it to do, it figures out how to do it and finally does it. The program can decide that it cannot do what it was told. However the most intelligent program is that which accepts the most specifications. It can also decide that it does not have the necessary resources to do what it was told. Again, the most intelligent program is the one which does the most things with the resources it has.

Learning requires external information. Therefore the program must be allowed to gather information about the problem and perhaps completed research by other sources. This is best accomplished via the Internet, although elicitation with the user is a must. The most intelligent program is that which makes best use of past knowledge and requiring least new knowledge (the ability to reuse knowledge). Of course if the program does not gather new information and relies too much on past knowledge it will end up being “closed minded” and this is not desirable as it will result in a closed region of knowledge with no new ideas.

Just like a computer is built without knowing what it’s going to be used for, so must be an intelligent program. A truly intelligent program would not be made for specific tasks such as recognising images or playing a game. It should be the most reusable application ever programmed. It should not be simply a part of another program, but be the entire program (except perhaps the interface).

So it seems that artificial intelligence means a program which translates specifications to solutions without the programmer knowing the solution. The key point here is that the programmer doesn’t know the solution (OK, no one in the development process knows it). This facilitates programming since the programmer need not know the solution before writing the program but rather leaves it to the program to find the solution. It’s also great when we as humans still have not found a solution (or an efficient one) to a particular problem.

What may the future hold for AI? As already mentioned, one day there will be a published algorithm for true AI which is able to learn how to solve any solvable problem, given a specification which has a high level of expressiveness. The first to benefit would be the humanoid robots which in turn would benefit humans in a variety of ways, which need not be mentioned. However will this mean the end of all human jobs, skilled and unskilled alike? Probably what will happen is that the developed countries will slow down the development of AI in the market in order to preserve jobs. But it might be possible for undeveloped countries to acquire some intelligent robots (through missionaries for example) which will help in some way or another. Perhaps in the developed world some hard to find professions will be filled in by robots, but I doubt they will be popular. However it can be possible that one day no one will work anymore and communism will take over as financial classes will be eradicated. All work will be done by robots and people will live a leisurely life, receiving provisions and resources equally. I doubt this will be allowed.

One application of AI I would pursue would be that of fabricating assignments. It would accept the specs of the assignment in raw format as given to the student, possibly with the addition of some course notes for reference, and the ID number of the student. The routine would understand the spec and using the ID number will generate a unique assignment with compiled code (if any) and documentation and comments. If I were to manage to realise such a routine, I would charge my fellow class mates to write their assignments, except that I wouldn’t do anything except feed the program the spec and ID number. Since every student will receive a unique assignment there will be no fear of plagiarism and detecting that the assignment was generated would be practically impossible unless the lecturers would obtain a copy of the routine and compare the given work with the generated one. Come to think of it, a uniquely generated id number would be better. The reason why AI makes sense to be used is because of the shear difficulty to find an algorithm which solves the problem.

Another application would be the semantic interpretation of a given code. The program would accept a given piece of code (given that it is accepted by the compiler) and produce a description in simple English what happens when it executes, at a given level of abstraction. Of course this can be extended to the interpretation of a given executable file. If this is possible then viruses and all malware would be easily detected with no need for updates. The other way round would also be nice where given a description in simple English, the program generates annotated code, ready to be compiled.

JQuery event / manipulation not working

2011-04-21T12:04:00.000+02:00

This is just a silly mistake I made which I thought I should share with the internetz. When assigning JQuery events to html elements, be sure to do it only after they have been loaded. If you just put them straight into a script file the elements wouldn't have loaded when it executes and hence the event won't work.

Make sure that all html DOM manipulation is done after the html loads by putting the javascript code inside a

$(document).ready(function() {
   event and manipulation stuff here :D
});

Photoshop slices using divs creates gaps

2011-04-21T11:54:00.000+02:00

If you've ever used Photoshop to create websites by drawing them and then slicing out the buttons and if you've ever used divs and css positioning to layout the slicing (done automatically by Photoshop, just follow this) then you probably found out that something like this happens:

This happened to me whilst doing my personal website (www.marctanti.com). The solution was found here. Apparently this happens because when the doctype of the html page is set to strict, images are by default set to display:inline which makes them vertically aligned so that the bottom of the image is in line with where the base line of the text is. In the case of sliced web pages, the slices are placed inside divs so the images are aligned with where the base line of text inside the div would be if there was any. But the divs make room for the "descenders" of text, that is, the extra room needed to display the bottom of the letters 'y' and 'g' for example. Therefore the images will not be aligned with the very bottom of the divs.

So to fix this problem we need to make the images aligned to the very bottom of the containing divs by setting the display css of each slice to block. I gave each slice image a class attribute called slice and then added the following css:

.slice
{
 display:block;
}

That fixed it.

Database Normalization (1-3 NF)

2011-03-30T10:30:00.075+02:00

This is a tutorial for those who are confused about the normal forms due to the extreme confusion you find on the web about the subject. If you want to know what normalization is and why to do it, wikipedia has a great article detailing this information:
http://en.wikipedia.org/wiki/Database_normalization

1NF

1NF is arguably the most ambiguous and confusing normal form on the web. The first normal form is just about making multi-valued fields organized into multiple rows. There are two types of multi-valued fields in unnormalized tables:

This-

Id	Student	Subject 1	Subject 2
1	Harry	Charms	Potions
2	Ron	Charms	Potions

And this-

Id	Student	Subjects
1	Harry	Charms, Potions
2	Ron	Charms, Potions

Or as is shown in most examples, this-

Id	Student	Subject
1	Harry	Charms
		Potions
2	Ron	Charms
		Potions

In both cases we are tying to shove in a list of values, that is a one-to-many or many-to-many relationship with the row, into the row itself. For reasons detailed in the wikipedia article, this should be fixed by creating a separate row for each value and repeating the values in the others fields, like so:

Id	Student	Subject
1	Harry	Charms
1	Harry	Potions
2	Ron	Charms
2	Ron	Potions

The table is now in 1NF were it not for the primary key losing its uniqueness. The id field must be unique in order to identify each distinct student. To solve this we can do one of two things:

Either we create an additional key field for the subjects and make the primary key of the whole table be a composite key of both student and subject ids, thus making the composite key unique-

StudId	Student	SubjId	Subject
1	Harry	1	Charms
1	Harry	2	Potions
2	Ron	1	Charms
2	Ron	2	Potions

Or we could just prepare for the other normal forms and start splitting the tables now as is usually done in examples-

StudId	Student	SubjId
1	Harry	1
1	Harry	2
2	Ron	1
2	Ron	2

SubjId	Subject
1	Charms
2	Potions

Notice that we still need to make the foreign key in the students table part of the primary key in order to preserve uniqueness. If you're wondering why we didn't use a weak entity (bridge table / junction table), that's because it's done in 2NF.

If we had more than one multi-valued field, we'd just create a Cartesian product, like so:

StudId	Student	SubjId	Subject	TeacId	Teacher
1	Harry	1	Charms	1	Filius
1	Harry	2	Potions	2	Slughorn
1	Harry	2	Potions	3	Snape
2	Ron	1	Charms	1	Filius
2	Ron	2	Potions	2	Slughorn
2	Ron	2	Potions	3	Snape

Resulting in 3 tables:

StudId	Student	SubjId	TeacId
1	Harry	1	1
1	Harry	2	2
1	Harry	2	3
2	Ron	1	1
2	Ron	2	2
2	Ron	2	3

SubjId	Subject
1	Charms
2	Potions

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

Complete example:

Id	Student	SubjId	Subject	Room	RoomHall	TeacId	Teacher
1	Harry	1	Charms	101	A	1	Filius
		2	Potions	202	B	2	Slughorn
						3	Snape
2	Ron	1	Charms	101	A	1	Filius
		2	Potions	202	B	2	Slughorn
						3	Snape

Turns into:

StudId	Student	SubjId	Subject	Room	RoomHall	TeacId	Teacher
1	Harry	1	Charms	101	A	1	Filius
1	Harry	2	Potions	202	B	2	Slughorn
1	Harry	2	Potions	202	B	3	Snape
2	Ron	1	Charms	101	A	1	Filius
2	Ron	2	Potions	202	B	2	Slughorn
2	Ron	2	Potions	202	B	3	Snape

Notice that the room is assumed to be dependant on the subject such that each subject is taught in its own room.

We may opt to leave the table as it is as it quite complex to break down into smaller tables without any guidance. However if we are to break the table down, the room information would be included in with the subject table since we said that the room is dependant on it, yielding the following:

StudId	Student	SubjId	TeacId
1	Harry	1	1
1	Harry	2	2
1	Harry	2	3
2	Ron	1	1
2	Ron	2	2
2	Ron	2	3

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

2NF

2NF is only applicable on tables with composite keys. If a table does not have a composite key, then it is already in 2NF. To make a table in 2NF, first you make sure it is in 1NF and then you split it into separate tables depending on which part of the composite key the fields depend on. For example in the students' table above, the student name does not depend on the subject id, it depends only on part of the composite key, that is, the student id. So the student name field should go into a separate table which describes the students (together with the primary key of course).

StudId	SubjId
1	1
1	2
2	1
2	2

StudId	Student
1	Harry
2	Ron

SubjId	Subject
1	Charms
2	Potions

And there is it, the weak entity we are so used to in many to many relationships.

Complete example (following from previous):

StudId	Student	SubjId	TeacId
1	Harry	1	1
1	Harry	2	2
1	Harry	2	3
2	Ron	1	1
2	Ron	2	2
2	Ron	2	3

Turns into:

StudId	SubjId	TeacId
1	1	1
1	2	2
1	2	3
2	1	1
2	2	2
2	2	3

StudId	Student
1	Harry
2	Ron

Hence yielding:

StudId	SubjId	TeacId
1	1	1
1	2	2
1	2	3
2	1	1
2	2	2
2	2	3

StudId	Student
1	Harry
2	Ron

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

Notice that if in 1NF we did not break down the table, we'd result with the same set of tables by now.

3NF

3NF is the normal form we are used to. All we do is check that every field in a 2NF table depends directly on the primary key. If it doesn't or if it depends on a non-primary key field, you place it in its own table. For example if we had the following table:

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

The RoomHall field is directly dependent on the Room field and not on the SubjId primary key field, so the RoomHall field should go into a table on its own together with the Room field. In fact the room where the subject is thought is not a direct property of the subjects entity but is an entity on its own and hence should be separated into a rooms entity and only referenced by a foreign key.

SubjId	Subject	Room
1	Charms	101
2	Potions	202

Room	RoomHall
101	A
202	B

Complete example (following from previous):

SubjId	Subject	Room	RoomHall
1	Charms	101	A
2	Potions	202	B

Turns into:

SubjId	Subject	Room
1	Charms	101
2	Potions	202

Room	RoomHall
101	A
202	B

Hence yielding:

StudId	SubjId	TeacId
1	1	1
1	2	2
1	2	3
2	1	1
2	2	2
2	2	3

StudId	Student
1	Harry
2	Ron

SubjId	Subject	Room
1	Charms	101
2	Potions	202

Room	RoomHall
101	A
202	B

TeacId	Teacher
1	Filius
2	Slughorn
3	Snape

Links

http://portal.dfpug.de/dFPUG/Dokumente/Partner/Hentzenwerke/Visual%20FoxPro%20Certification%20Exam%20Study%20Guide%20Chapter%2002.pdf

Reading Related Tables As Nested Rows

2011-03-14T16:36:00.007+01:00

Problem
A problem I used to face with relational databases is how to handle 1-to-many or many-to-many rows in SQL select statements. Let's say you have 2 tables with a many-to-many relationship between them, such as a Movies table and an Actors table. How do I present a list of movies together with their associated actors?

The naive way to do this is by using nested loops with a query for movies in the top loop and a query for actors in the second loop. In PHP it would look something like...

$moviesResult = mysql_query("SELECT id, title FROM movies"); 
while($moviesRow = mysql_fetch_assoc($result)) 
{ 
    echo("<h1>" . $moviesRow['title'] . "</h1>"); 

    echo("<ul>"); 
    $actorsResult = mysql_query("SELECT actors.name FROM actors INNER JOIN movies_actors ON actors.id = movies_actors.actorid WHERE movies_actors.movieid = " . $moviesRow['id'] . ";"); 
    while($actorsRow = mysql_fetch_assoc($actorsResult)) 
    { 
        echo("<li>" . $actorsRow['name'] . "</li>"); 
    } 
    echo("</ul>"); 
}

This approach however will kill your database. Ideally you should minimize the number of queries sent.

Another approach would be to join the movies table with the actors table and then read it with nested loops.

$result = mysql_query("SELECT movies.id AS id movies.title AS title, actors.name AS actor FROM movies INNER JOIN movies_actors ON movies.id = movies_actors.movie INNER JOIN actors ON actors.id = movies_actors.actor"); 
$row = mysql_fetch_assoc($result); 
while($row) 
{ 
    $currMovieId = $row['id']; 
    echo("<h1>" . $row['title'] . "</h1>"); 
    echo("<ul>"); 
    do 
    { 
        echo("<li>" . $row['name'] . "</li>"); 
    } while ($row = mysql_fetch_assoc($result) && $row['id'] == $currMovieId);
    echo("</ul>"); 
}

This works but as soon as you add another table to the join, determining which rows contain new information can be a nightmare, not to mention all the rows which just contain repeated information due to the cartesian product. For example:

Id	Title	Actor	Genre
1	The Matrix	Keanu Reeves	Action
1	The Matrix	Keanu Reeves	Adventure
1	The Matrix	Keanu Reeves	Sci-Fi
1	The Matrix	Laurence Fishburne	Action
1	The Matrix	Laurence Fishburne	Adventure
1	The Matrix	Laurence Fishburne	Sci-Fi
1	The Matrix	Carrie-Anne Moss	Action
1	The Matrix	Carrie-Anne Moss	Adventure
1	The Matrix	Carrie-Anne Moss	Sci-Fi
2	The Matrix Reloaded	Keanu Reeves	Action
2	The Matrix Reloaded	Keanu Reeves	Adventure
2	The Matrix Reloaded	Keanu Reeves	Sci-Fi
2	The Matrix Reloaded	Laurence Fishburne	Action
2	The Matrix Reloaded	Laurence Fishburne	Adventure
2	The Matrix Reloaded	Laurence Fishburne	Sci-Fi
2	The Matrix Reloaded	Carrie-Anne Moss	Action
2	The Matrix Reloaded	Carrie-Anne Moss	Adventure
2	The Matrix Reloaded	Carrie-Anne Moss	Sci-Fi
3	The Matrix Revolutions	Keanu Reeves	Action
3	The Matrix Revolutions	Keanu Reeves	Adventure
3	The Matrix Revolutions	Keanu Reeves	Sci-Fi
3	The Matrix Revolutions	Laurence Fishburne	Action
3	The Matrix Revolutions	Laurence Fishburne	Adventure
3	The Matrix Revolutions	Laurence Fishburne	Sci-Fi
3	The Matrix Revolutions	Carrie-Anne Moss	Action
3	The Matrix Revolutions	Carrie-Anne Moss	Adventure
3	The Matrix Revolutions	Carrie-Anne Moss	Sci-Fi

Are we supposed to receive all those rows just to display the below?

1	The Matrix	Keanu Reeves, Laurence Fishburne, Carrie-Anne Moss	Action, Adventure, Sci-Fi
2	The Matrix Reloaded	Keanu Reeves, Laurence Fishburne, Carrie-Anne Moss	Action, Adventure, Sci-Fi
3	The Matrix Revolutions	Keanu Reeves, Laurence Fishburne, Carrie-Anne Moss	Action, Adventure, Sci-Fi

Solution
The best solution I found is a hybrid of the above 2 solutions. You make a different query for each table and then read all the rows returned by each query, placing the information in the list it belongs to.

$moviesResult = mysql_query("SELECT id, title FROM movies;"); 
$actorsResult = mysql_query("SELECT movies_actors.movieid AS movieid, actors.name AS name FROM actors INNER JOIN movies_actors ON actors.id = movies_actors.actorid;"); 
$genresResult = mysql_query("SELECT movies_genres.movieid AS movieid, genres.name AS name FROM genres INNER JOIN movies_genres ON genres.id = movies_genres.genreid;"); 

$actorRow = mysql_fetch_assoc($actorsResult); 
$genreRow = mysql_fetch_assoc($genresResult); 
while($movieRow = mysql_fetch_assoc($moviesResult)) 
{ 
    $currMovieId = $movieRow['id']; 
    echo("<h1>" . $movieRow['title'] . "</h1>"); 

    echo("<ul>"); 
    while ($actorRow && $actorRow['movieid'] == $currMovieId) 
    { 
        echo("<li>" . $row['name'] . "</li>"); 
        $actorRow = mysql_fetch_assoc($actorsResult); 
    } 
    echo("</ul>"); 

    echo("<ul>"); 
    while ($genreRow && $genreRow['movieid'] == $currMovieId) 
    { 
        echo("<li>" . $row['name'] . "</li>"); 
        $genreRow = mysql_fetch_assoc($genresResult); 
    } 
    echo("</ul>"); 
}

In this way we only make 3 queries, equal to the number of tables, and we only read as many rows as needed.

SQL Joins Tutorial

2011-03-13T20:01:00.028+01:00

This is a simple tutorial aimed towards those who, like me, completely misunderstood how to, and why to, use joins in SQL. It is not meant to be an advanced reference but a tutorial for beginners who know some SQL but can't understand joins.

Huh?
Let's say that you have a database with tables which are related by foreign keys. For example, a Customers table, a Products table and an Orders table. Each row in the Orders table is linked to a row in the Customers table (the customer who made the order) and to a row in the Products table (the product which was ordered).

Now let's say that you want to query the database to view all the rows in the Orders table but with the customer's name and product's name instead of their primary key. If you learned SQL the same way I did, you'd probably do something like this:

SELECT orders.date, customers.name, products.name
FROM orders, customers, products
WHERE orders.customer = customers.id AND orders.product = products.id;

This is called an implicit join. In fact you are doing an unconditioned join between all 3 tables and then just filtering out the joined rows which are not made of related table rows. What does this mean?

If our 3 tables contain the following data:

Orders:

Id	Date	Customer	Product
1	01/01/01	1	2
2	2/02/02	3	2
3	03/03/03	3	3

Customers:

Id	Name
1	John
2	Michael
3	Terry

Products:

Id	Name
1	Cheese
2	Parrot
3	Spam

Then the query will cause this to happen:

Movies.Date	Customers.Name	Products.Name
01/01/01	John	Cheese
01/01/01	John	Parrot
01/01/01	John	Spam
01/01/01	Michael	Cheese
01/01/01	Michael	Parrot
01/01/01	Michael	Spam
01/01/01	Terry	Cheese
01/01/01	Terry	Parrot
01/01/01	Terry	Spam
02/02/02	John	Cheese
02/02/02	John	Parrot
02/02/02	John	Spam
02/02/02	Michael	Cheese
02/02/02	Michael	Parrot
02/02/02	Michael	Spam
02/02/02	Terry	Cheese
02/02/02	Terry	Parrot
02/02/02	Terry	Spam
03/03/03	John	Cheese
03/03/03	John	Parrot
03/03/03	John	Spam
03/03/03	Michael	Cheese
03/03/03	Michael	Parrot
03/03/03	Michael	Spam
03/03/03	Terry	Cheese
03/03/03	Terry	Parrot
03/03/03	Terry	Spam

And after generating all that it will then select the rows which make sense relation wise, according to the WHERE statement.

Movies.Date	Customers.Name	Products.Name
01/01/01	John	Parrot
02/02/02	Terry	Parrot
03/03/03	Terry	Spam

The big table is called a Cartesian product, which means that all possible combinations of rows between the tables are created, yielding a number of rows equal to the multiplication of the number of rows in each table (3 * 3 * 3 = 27 in this case). As you can tell, this will get really huge really quickly as the table get bigger.

Enter explicit joins.

Joins
In SQL, the FROM statement doesn't mean "a list of tables used in the SELECT statement". In the FROM statement you mention just one table. This table could either be one of the tables you created in the database or a "custom" table, such as one which is a joined version of several tables. The JOIN statement in SQL is not a keyword on par with the FROM statement, as I used to think due to the way it is indented in most tutorials I've seen. It is in fact a binary operator between 2 tables, just like "+" and "=" as binary operators.

The JOIN operator takes 2 tables and returns a new table, which is a joined version of the 2 tables. You can then join another table to that new table and keep on adding more tables to the "composite" table. There are several joins available in standard SQL which will be described later, but if we should use the INNER JOIN type in an example, this is how joins are used in general:

SELECT orders.date, customers.name, products.name
FROM (orders INNER JOIN customers ON orders.customer = customers.id) INNER JOIN products ON orders.product = products.id;

As you can see, the join is used between tables and can even be bracketed in order to state which tables should be joined up first. The ON statement is used to immediately join up the rows which are related, avoiding the cartesian product table in the first place. This will therefore be processed much more efficiently as the third table will only be joined up after the first two tables have been joined correctly, rather than joining everything together without a condition.

In the implicit join example, the tables where joined up with an inner join without the ON condition, hence losing all the advantage of joins. Now that you know how joins work, let's see what are the differences between the 4 join types described in w3schools.com.

Join types
The main difference between the join types is how they handle rows which don't match the ON condition.

INNER JOIN:
Strictly follows the ON condition between tables such that any rows in one table which cannot be matched up with another row in the other table will be left out. This is the kind of join we are used to.

SELECT orders.date, customers.name, products.name
FROM (orders INNER JOIN customers ON orders.customer = customers.id) INNER JOIN products ON orders.product = products.id;

results in

Movies.Date	Customers.Name	Products.Name
01/01/01	John	Parrot
02/02/02	Terry	Parrot
03/03/03	Terry	Spam

As you can see, not all customers or all products where mentioned. Only the ones which were mentioned in the ORDERS table and hence were related in some way were returned.

OUTER JOIN:
This is where things get a bit hairy and hence require that you make an effort to understand. The outer join makes sure that all rows in both tables are returned, even if there is no matching row in the other table. What happens to those tables which have no matching rows? They are joined to NULL values. As long as they are returned, it doesn't matter what they're joined to right?

You can also use LEFT JOIN and RIGHT JOIN to say whether you want to return all the rows of the table on the left of the join operator only or all the rows of the table on the right of the join operator only.

Now in order to use these joins to create a complex joined table, you have to be sure that a join will not return columns with NULL values which will be used in an ON condition of another join.

SELECT orders.date, customers.name
FROM orders RIGHT JOIN customers ON orders.customer = customers.id;

results in

Movies.Date	Customers.Name
01/01/01	John
NULL	Michael
02/02/02	Terry
03/03/03	Terry

SELECT orders.date, products.name
FROM orders RIGHT JOIN products ON orders.product = products.id;

results in

Movies.Date	Customers.Name
NULL	cheese
02/02/02	parrot
01/01/01	parrot
03/03/03	spam

SELECT orders.date, products.name, customers.name
FROM (orders LEFT JOIN customers ON orders.customer = customers.id) RIGHT JOIN products ON orders.product = products.id;

results in

Movies.Date	Customers.Name	Products.Name
NULL	NULL	cheese
02/02/02	terry	parrot
01/01/01	john	parrot
03/03/03	terry	spam

As you can see, depending on how the outer joins are used, we can make a particular table return all its rows, even if it isn't related to any other table.

Final note
I'd like to leave a few notes and links before concluding.

First of all, what I said about the implicit join not being efficient next to an explicit one is not necessarily true since the SQL optimizer may fix it before executing it.

Secondly, if you can avoid using brackets in the the joins it would be better as that will allow the SQL optimizer to make adjustments to the query without it having to make sure to preserve the precedence which you unneccessarily imposed.

In a future post, I will describe a trick which I used to efficiently view multiple one-to-many related tables which I also had trouble with in SQL until recently. But for now I will leave you with these links:

http://www.w3schools.com/sql/sql_join.asp
http://onlamp.com/pub/a/onlamp/2004/09/30/from_clauses.html
http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html

Generic Genetic Algorithms

2011-02-13T21:36:00.001+01:00

I have finally finished my C# generic genetic algorithm library which is based on my university thesis "A Generic Genetic Algorithm using Phenotype Building Functions" (http://www.scribd.com/doc/48697452/A-Generic-Genetic-Algorithm-using-Phenotype-Building-Functions). You can find it at http://code.google.com/p/genericga/. The wiki page explains how to use it.

Cool proofs

2010-07-28T15:45:00.000+02:00

When I was in university, our course had a forum that we maintained ourselves in which we posted anything which would be of help to each other or which we found worth sharing. At the time of writing this, the forum will soon be closed down and all of the information in it will be probably lost. I shall post here my geekiest post ever which was titled "Cool proofs" in which I posted 3 mathematical proofs used in computer science which I literally found cool. ^^

Power set of an infinite set is uncountable
By uncountable we mean that you cannot have a one to one mapping from a countable infinite set, usually the natural numbers to the uncountable one.

For example the set of all integers is countable because there exists a bijective mapping from the natural numbers to the integers, for example:
0 -> 0
1 -> -1
2 -> 1
3 -> -2
4 -> 2
...
That is, even numbers point to positive integers and odd numbers point to negatives. So for every integer there exists a natural number which points to it and every natural number points to an integer. So even though there appears to be more integers than natural numbers, in reality they are equal because they are both countable infinite sets.

Now in order to show that the power set of an infinite set is uncountable we need to show that there exists at least one element of the power set which cannot be pointed by a natural number. Consider this random relation of natural numbers pointing to elements of the power set of all natural numbers:
0 -> {}
1 -> {1}
2 -> {0, 1, 2}
3 -> {1, 3}
4 -> {3, 5}
5 -> {1, 2, 3, 4}
6 -> {100, 1000, 10000}
...
Notice that some natural numbers are pointing to sets which contain themselves and others do not. Lets call the numbers which point to themselves Selfish and the others Non-Selfish. For example 1, 2 and 3 are selfish whilst 0, 4, 5 and 6 are not. Given that the power set of all natural numbers contains every possible subset of natural numbers, it stands to reason that one of the subsets should happen to be the set of all Non-Selfish numbers in our relation. Let's call the natural number which points to the set of all Non-Selfish numbers 'd' and the set of all Non-Selfish numbers S. Since every natural number must either be a Selfish number or a Non-Selfish number, we can safely say that d itself is either a Selfish number or a Non-Selfish number. So what is it?

If d is a Selfish number then it is an element of S. But only Non-Selfish numbers are elements of S.
If d is a Non-Selfish number then it is not an element of S. But S contains all Non-Selfish numbers.
Therefore we have reached a contradiction, because we have found an element which cannot be mapped by a natural number. Therefore it is impossible to make a bijective relation between the natural numbers and the power set of all natural numbers. Therefore the power set of an infinite set is uncountable.

QED

Set of all infinite length binary strings is uncountable
Enumerate the infinite length binary strings in a table in some order. For example:
0011111000110011...
1011100101100100...
1010101010010101...
0000000000000000...
...
Now we can refer to a particular string by referring to its corresponding row number. We can also refer to a particular bit in the string by referring to a particular column number. Let B(r,c) be the bit in column c of the string in row r.

If this set was countable, we can create a bijective mapping from the natural numbers to each and every binary string. But it is impossible to enumerate each and every infinite length binary string because no matter what order we use and no matter how many strings we include, it is always possible to find a string which is not included. Here's how:
Consider the diagonal bits in the table, that is, consider B(i,i) for every natural number i. Construct a string, s, which is made of the diagonal bits, inverted. That is, s[i] = !B(i,i). Now for every string, there is at least one bit which is different from s, because the diagonal includes one bit from every string and s has that bit inverted. Given the previous table, s would be 1101...

So no matter how many strings you enumerate (infinity included) there are always strings which are not included in the enumeration. Or conversely, no matter how you construct a relation of natural numbers pointing to the strings, there are always strings which are left out. Therefore the set of all infinite length binary strings is uncountable.

QED

Notice that for any power set, its elements can be encoded into binary strings, where each bit represents whether a particular element in the original set is in that subset. For example the power set of {1,2} is {{}, {1}, {2}, {1,2}} which can be represented as {00, 10, 01, 11} where the first bit says if 1 is in the set and the second says if 2 is in the set. Therefore if the set of all infinite length binary string was countable, the power set of an infinite set was also countable.

The halting problem
The halting problem proves that it is impossible to construct an algorithm (program which always terminates) which will analyze any program and correctly answer if, given a particular input, will terminate. Here's how.

Assume that such a program exists and can be used by simply calling the function Halt(p,i) which will return whether program p will terminate given input i. What we shall do is construct a program which will use Halt on itself and do the opposite. If this is possible than we have just found a case where Halt will fail, no matter what the implementation.

Construct program D which is defined as:
D(p) = if Halt(p,p) then infinite_loop else terminate
Program D will take a program p, check if it halts when given itself as input and enter into an infinite loop if so or terminate otherwise. If this self input confuses you, think of the input to be a copy of the original program. So if I have written a compression program which takes other files and compresses them, I can copy the program and compress the copy, essentially giving the program itself as input.

The reason we constructed such a funny program is that if we give D itself as input, the following will happen:
D(D) = if Halt(D,D) then infinite_loop else terminate
and as you can see, Halt will essentially check if D(D) will terminate, therefore checking if the whole program will terminate. But what does the program mean? The program will either terminate with itself as input or not, but if it terminates then Halt will return true, causing the program to enter an infinite loop, whilst if it does not terminate then Halt will return false, causing the program to terminate.

So if we now call Halt on this program, by calling Halt(D,D), Halt will not be able to come up with a correct answer because D will check what the output will be and do the opposite. Notice that we will receive an answer, it is the same as that given in the if-condition, but it will obviously be the opposite of what will happen. Remember that Halt will call D(p) and pass D as input (instead of p) and that D as a program and D as an input are two separate 'files' which are copies of each other. Self reference can be detected by for example changing a global variable to know how many times a function has been called but
a) A semantically equivalent function can be rewritten which avoids such tricks, yet results in the same problem.
b) This means that some program-input pairs will not be accepted, which means that you have not constructed the required function. After all, what do you think Halt(D,D) should output?

Therefore we have proven that it is always possible to construct a program which will cause Halt to give a wrong output. Similarly, you cannot construct an algorithm which will tell you if a particular action will be carried out in a program given an input because you can construct a program similar to D which will cause it to give the wrong output. Namely D(p) = if ActionPerfomed(p,p) then avoid_action else perform_action.

QED

Typocalypse

2010-07-27T14:55:00.000+02:00

Lately me and my friend Andreas Grech (http://blog.dreasgrech.com/) developed jointly a Microsoft XNA game in just under a sleepless and coffee ridden 24 hours called Typocalypse which is a game where you have to type the words under zombies before they reach you.

My involvement in the game was in using my previous two blog posts, the biasing function for gradually increasing the difficulty of the game by gradually biasing the randomly chosen words to prefer longer words as the score increases and the trie for determining which zombies have a word which has a prefix that matches the currently typed text. I was also responsible for handling keyboard events, displaying the words under the zombies and sound effects which I created orally.

To give credit where credit is due, the background music was taken from the Amiga game The Great Giana Sisters, the pictures including the background image where found from google images and we couldn't be bothered with looking for them again and the library which enabled capturing of keyboard input was taken from here which was developed by George Mamaladze.

The game is open source and you can download and use the source code if you wish, but keep in mind that this was developed in under 24 sleepless hours so at some point coding started getting messy.

Link to the game is http://code.google.com/p/typocalypse/downloads/list.

Enjoy :)

C# Trie

2010-07-21T01:54:00.001+02:00

In a recent project I have ventured into, I had to develop a set of classes in C# for a simple trie which are now released as open source (http://code.google.com/p/typocalypse/source/browse/#hg/Trie). This blog post shall describe how it works and how to use it.

Introduction to tries
Simple tries are a data structure for mapping strings to values such that it enables you to efficiently retrieve all the values whose key strings have a particular prefix. This works by storing all the strings in a tree where each node is a prefix to a number of strings and each edge is a character to append to the prefix in the parent node. The root node is the empty string which is a prefix to all strings.

As you traverse a path from the root downwards, you follow the edges which lead to prefixes of the string you are trying to match. Eventually if such a string exists, a node will be pointing to the value mapped by the string. By traversing the descendants of a particular node, you can retrieve all the stored strings which have that prefix in common and their corresponding value.

Here's a diagram example from wikipedia:
http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg

Implemented trie
The implemented trie supports adding, removing and character-by-character prefix searching of string-value pairs.

The way it works is by keeping a reference in each node to a value object such that if the reference is null then the node does not point to a value object and hence the prefix is not a complete string. The type of the values is generic, any referencable type is allowed. Each node points to its children via a Dictionary object which maps characters to nodes, thereby allowing a fast search by following the characters.

The following is a description of each class:

TrieNode
This is a non-public class which represents the nodes of the trie, that is, the prefixes. However in this implementation, the prefix itself is not stored, only the last character of the prefix called the Key is stored in order to know which character was followed to access this node. It also stores the value (generic type), a pointer to the parent node and a dictionary which maps characters to children nodes. If this node terminates a string then it's value field points to an object, otherwise it is null.

PrefixMatcher
This is a non-public class which is dedicated to allow the user to search the trie for a particular string or strings with a particular prefix. It was designed for enabling the user to search for the values of said strings on a character by character basis rather than providing the whole string immediately so that it can be used to search for user input as the user types in the query. This requires the maintenance of a state so that it is known which prefix has been entered thus far as well as which node that prefix is found in so as to enable an efficient search. For this reason the search feature was kept in a class of its own. Each time the trie is modified with the removal of a string, the current search is cancelled and must be redone from first character so as to avoid the user from searching non-existent strings.

IPrefixMatcher
This is a public interface which abstracts the methods of the PrefixMatcher class so that the user is provided with an abstraction rather than a concrete class in order to search.

Trie
This is the main class which provides the features of the trie data structure. Searching is done through the public property "Matcher" which returns an instance of IPrefixMatcher. When a string is removed, the current search is cleared so as to avoid the user from searching non-existent strings.

Examples
Here is an example of how to use the implemented trie:


            //Create trie
            Trie < string > trie = new Trie < string > ();

            //Add some key-value pairs to the trie
            trie.Put("James", "112");
            trie.Put("Jake", "222");
            trie.Put("Fred", "326");

            //Search the trie
            trie.Matcher.NextMatch('J'); //Prefix thus far: "J"
            trie.Matcher.GetPrefixMatches(); //[112, 222]
            trie.Matcher.IsExactMatch(); //false
            trie.Matcher.NextMatch('a');
            trie.Matcher.NextMatch('m'); //Prefix thus far: "Jam"
            trie.Matcher.GetPrefixMatches(); //[112]
            trie.Matcher.NextMatch('e');
            trie.Matcher.NextMatch('s'); //Prefix thus far: "James"
            trie.Matcher.IsExactMatch(); //true
            trie.Matcher.GetExactMatch(); //[112]

            //Remove a string-value pair
            trie.Remove("James");

Link to classes
http://code.google.com/p/typocalypse/source/browse/#hg/Trie

Biasing uniform random fraction generators towards larger or smaller fractions

2010-07-07T12:27:00.000+02:00

The need for a function which allows you to bias a uniform probability distribution random number generator towards fractions closer to 0.0 or 1.0, and to control the degree of the bias, has been felt a few times whilst I was programming. C# only has uniform random number generators and in a recent project I had, I had to devise a function to enable me to bias the random numbers generated. In this post I shall describe this function.

Problem
We would like a function which skews the number line between 0.0 and 1.0 such that the range of numbers closer to 0.0 are denser than those closer to 1.0 or vice versa.

Consider the following statistics gathered from the Python function random.random(), where we shall count the number of random numbers generated that are greater than 0.5 and those that are less out of 10000:

Seed	random()<0.5	random()>=0.5
0	4980	5020
1	5023	4977
2	5038	4962

The frequencies are very close to each other. This is because random.random() uses a uniform probability distribution, meaning that each number between 0.0 and 1.0 has an equal chance of being generated. But what if we wanted to bias the frequencies so that more numbers are less than 0.5?

An application for this could be to randomly select an element from an array which is sorted on priority such that you want to randomly select the first element more often than the last. To do this you bias the random number generator towards smaller indices.

Solution
We need a function which takes the set of inputs from 0.0 to 1.0 and returns numbers in the same range, however skewing the mapping such that a larger part of the number range gets mapped to a smaller part of the output range.

In the graph below, y = x, the mapping is unbiased, no part of the output range has been squashed.

However if we were to bend the line so that it still goes through (0,0) and (1,1) but is curved then we could skew the mapping as demonstrated below:

The graph on the left skews the output such that there is a bias for smaller numbers; all inputs which are less than 0.6 will be mapped to be closer to 0.0 whilst the rest of the inputs will be mapped to be closer to 1.0. On the other hand, the graph on the right skews the output such that there is a bias for larger numbers; only inputs smaller than 0.4 will be mapped to be closer to 0.0 whilst the rest of the inputs will be mapped to be closer to 1.0. Also, in the graph on the left, the smaller the number the greater the chance of it being returned whilst in the graph on the right, the larger the number the greater the chance of it being returned.

We would like to devise a function which will give us this curve, and to some how parameterise the curvature so that the bias can be made stronger or weaker. Such a curve is given by the exponent function
y = x^k           (1)
which, given that k is positive, goes through (0,0) and (1,1) and which different values of k will change the curvature such that when k is between 0.0 and 1.0 the curvature will be going flatter and when k is between 1.0 and infinity the curvature will be going steeper.

In order to control the curvature we shall allow the user to specify a point which the curve is to pass through. To find which value of k will go through the point (x',y'), we make k subject of the formula in (1) after substituting x with x' and y with y' and we get
k = ln y' / ln x'           (2)
and by substituting (2) into (1) we get
y = x^(ln y' / ln x')           (3)
which is useful for describing our curve, provided both y' and x' are between 0 and 1, both not included.

However we would like the way we control the curvature to be more meaningful to the user. So instead we let the user provide just one variable, called the bias, which will be the x value which will be mapped to 0.5, hence all smaller values will be mapped to be less than 0.5 and all greater values will be mapped to be more than 0.5. To do this, we set y' to be 0.5, so that x' will be the bias, that is, the x value which gives 0.5. After modifying equation (3), the new equation is
y = x^(ln 0.5 / ln b)           (4)
where b is the bias.

The following graphs are obtained for different values of b:

Results
The following statistics demonstrate the validity of the function. Again 10000 random numbers are generated using Python's random.random() except that this time we shall pass the random numbers to the devised funtion as x using different values for b and all cases use a seed of 0:

b	bias(random())<0.5	bias(random())>=0.5
0.1	1026	8974
0.5	4980	5020
0.9	9043	957

So using this function we can easily give a bias to random number generators. The only problem with it is that a bias of zero or one will result in a log of zero and division by zero respectively and hence cannot be done.

Summary
To bias a random number generator which gives random fractions so that it is biased towards numbers closer to 1 or 0, use the equation y = x^(ln 0.5 / ln b) where x is the unbiased random number, b is the fraction of numbers to be less than 0.5 and y is the biased random number.