Previous Up Next
Dutch / Nederlands

Diary, March 2013

Sun Mon Tue Wed Thu Fri Sat
                      1   2
  3   4   5   6   7   8   9
 10  11  12  13  14  15  16
 17  18  19  20  21  22  23
 24  25  26  27  28  29  30

Thursday, March 7, 2013

Alphabet Cover

Alphabet Cover is an extension to Exact Cover that given a collection of vectors over an alphabet and a don't-care symbol, the question is to find a subset of these vectors, such that for all columns the strings contain the same symbol from the alphabet or the don't-care symbol, and such that each column contains at least one vector with no don't-care symbol. Every Exact Cover can be transformed into an Alphabet Cover. Given the incidence matrix, assign a unique symbol to each row, and replace all one's by this symbol and all zero's by the don't-care symbol. It is also possible to transform each Alphabet Cover into an Exact cover, but this transformation cannot be described in a single sentence. But from this we can conclude that Alphabet Cover is also NP-complete. The reason why I came up with Alphabet Cover, is because I think it allows for a more 'space' efficient implementation of a class of Exact Cover problems, which possibly have stronger reduction mechanisms. I am in particular thinking about Exact Covers generated from nonograms.

Sunday, March 10, 2013

Some snow

Around eleven in the morning, there was almost 2 cm of snow on the table in the back garden, but on the pavement there was none at all. There were periods of snowing during the day.

Palindrome date

Today is a palindrome date when written in the (M)M/(D)D/(YYY)Y format: 3/10/2013.

Monday, March 11, 2013

Thin layer of snow

In the morning, there was a thin layer of snow, only partial covering the pavement. It was still snowing and continued for some time. In the evening it started to snow again, resulting in a thin layer of snow covering the pavement.

Data & Reality

This morning, I finished reading Data & Reality by William Kent, which I started reading on February 5. I bought the book because a colleague wrote a positive review about it. It is an interesting book, but I did not find it thought provoking, which might be due to the fact that I already thought over many of the issues mentioned in the book. It did strengthen my ideas about "knowledge enginering" and that problems with information systems often are caused by a too simple model of reality or a mismatch between concepts between users. It seems that many information systems have problems with dealing with cooperation.

Saturday, March 16, 2013

Marek van de Jagt

At 11:24, I bought the book Ik ging van hand tot hand: Verzameld werk van Marek van der Jagt by Arnon Grunberg ISBN:9789044511659, which contains everything he wrote under the heteronym Marek van der Jagt. I bought it for € 7.50 from the bookshop of De Bijenkorf.

Sunday, March 17, 2013


This afternoon, I installed a webserver on FJF, a Samsung NC10 notebook. I downloaded Apache 2.2 and installed it. In the httpd.conf I changed the document root directory. I made some changes in the configuration of the router attached to the optical fiber connection. I assigned a fixed IP address to the MAC address of the wireless network adapter of the notebook and in the NAT configuration, I rerouted WAN port 80 to port 80 of the fixed IP address. Then, last but least, I had to relax the Windows firewall settings with respect to http and https. I had to modify the chkhtml.c program in order to fill the root directory with a copy this website.

Tuesday, March 19, 2013

The Gum Thief

At 13:57:39, I bought the book De Kauwgomdief (The Gum Thief) by Douglas Coupland, ISBN:9789041410214, which includes De Handschoenvijver (Glove Pond) by Roger Thorpe, for € 6.95 from the bookshop of De Bijenkorf. The original price was € 22.95.

Looking into space

Today, I received the Vrij Nederland magazine issue of September 20, 1986, which opens with the article Een blik in de ruimte (Looking into space) by William Rothuizen about the light art work in the ceiling of The Amsterdam Music Theatre by Peter Struycken and some of his other commisioned art works and installations.

Thursday, March 21, 2013

Spring snow

Today, is the first day of the spring. Sometimes the sun was shining, sometimes there was a snow shower, and sometimes, as can be seen in this picture, they happened at the same time. Never I saw some snow stay on the ground. Yesterday afternoon there was also a lot of snow, which did not stay, but when I arrived home, I found some of it on the grass in our garden, which is in the shade.

Deventer murder trial

Today, Gert-Jan Knoops, lawyer and criminal law expert, has made a request to the Dutch High Court to reopen the Deventer murder trial based on five new facts that where not known at the moment of the trial. These are (paraphrased):

Friday, March 22, 2013

Concurrency control

When multiple individuals are making changes to a model (which can be a text document, a database or anything in between) some method for concurency control is required. In an ideal world concurrency control should be orthogonal to the structure of a model, meaning, that one does not need to 'organize' the model to allow a certain form of concurrency control. (And in an ideal world, physical storage should also be orthogonal to both concurrency control and the structure of the model.) Rights management is closely tied with concurrency control, because concurrency control deals with how changes are made to the model and rights management deals with who are allowed to change which part of the model. Likewise, change management (workflow) is also tied in with concurrency control as well as with rights management.

I think there are basically three forms of concurrency control:

Actually the third form is a whole range of forms of concurrency control depending of the types of inconsistencies you allow. It should also be noted that there is also a range of pessimistic concurrency control implementations depending the kind of locking mechanism that is used. An important issue is lock granularity and locking types. Actually, if you think about it, it all starts with a set of rules that define what are non-conflicting changes. For example, (you could have the rule that) inserting two elements into a set is defined as non-conflicting. A locking mechanism should prevent the creation of set of changes that violate these rules, but could possibly be more restrictive.

With optimistic concurrency control there is another important division which is asymmetric versus symmetric concurrency control. With asymmetric concurrency control there is a central model (such as in Subversion) and with symmetric concurrency control there is no concept of a central model (such as in Git).

Optimistic concurrency control does not use a locking mechanism, but instead tries to combine set of changes. When two sets of changes are without conflicts with respect to rules, they can be combined (merged) without problems. In case there are conflicts, one could either decide to resolve these conflict or to allow inconsistencies to be introduced. Resolving conflicts can be done in several different ways. One could simply split a set of changes in those that are without conflict and those that are in conflict, and discard the later. One could also apply changes to the set of changes as to resolve conflicts. (In Subversion this is done by allowing the user to manually edit conflicts.)

It should be noted that there is slight difference between resolving conflict based on the change history (the changes In the order which they were made by the user) and based on the resulting set of changes, because it is possible that the change history there are operations that cancel each other. For example if user created an object and later remove it again, it is possible that the change history contains a conflict (because the parent to which the object was created has been removed) while the change set (which does not contain anything about the object that was created and later removed) has no conflict at all.

Saturday, March 23, 2013

Dialect atlas

At 14:42, I bought the book Dialectatlas van het Nederlands (Dialect atlas of Dutch) edited by Nicoline van der Sijs, ISBN:9789035133785, from bookshop Broekhuis for the reduced price of € 15.00, where the original price was € 49.95. I also got the book De verrekijker (The binocular) by Kees van Kooten, ISBN:9789059651913 for free.

Sunday, March 24, 2013

Computer Science in Vietnam

Yesterday, I came across the blog CS in VN by Niel Fraser about Computer Science being taught in schools in Vietnam. It contains a story of students in the highest grade in highschool having to solve a problem related to diagonal mazes within 45 minutes using Pascal. Most of them finish the assignment in time and only few needed another five minutes to finish it. I decided to give it a try myself. I needed 45 minutes to write a program in C++. Pascal is a little more verbose than C++. I needed just a few minutes to come up with a good algorithm, needed about 20 minutes to implement it, and about 15 minutes to debug it. I left some debugging statements in the source code.

The assignment was to calculate the number of enclosed areas in a given diagonal maze, and give the area of the largest area. I continued working on the program to investigate the distribution of the size of the areas found. I experimented on a maze of 1000 by 1000 cells, and presumed that it was repeated in both directions. I collected the counts for a large number of random generated diagonal mazes. So far, I did not derive any conclusions from this.

Wednesday, March 27, 2013

Amsterdam and Beijing

At 13:55, I bought the following two books from bookshop De Slegte;

Sunday, March 31, 2013

A white Easter

In the past three days it has been snowing often. Friday, when I left around 9 o'clock, there was almost 2 cm of snow on the table in our back garden, but it did not stay everywhere on the ground. Yesterday, there was a short period in the morning, that the snow stayed for a while, but still not everywhere. Whenever the snow stayed for some time, it also melted away soon. So, I think we cannot qualify this as a white Easter. It has been quite cold for this time of year. Still every night the temperature drops below zero degree Celsius. It has been the coldest March since 1987.

Left/right maze

In the past week, I have been working on a program for counting the number of path with a certain length in diagonal mazes, starting from the program the I wrote for the Vietnamese highschool assignment. The program works on random generated 1000 by 1000 square, and assume that it is wrapped around in both directions. Then it counts the length of all paths. Where every you start, you will always return at the starting position (when wrapping around the edges), but in some cases you will arrive there with an off-set of multiplies of 1000. In a sense you can consider these as infinite paths. When repeating this for a large number of times, the number of such paths is around seven percent. The question I have been trying to answer is what percentage consist of infinite paths if you are on an infinite maze.

I also got the idea to look at the kind of maze you get when either on a square you turn right or left, no matter from which direction you are coming. My first thought was that it would be quite similar. Below the rounded path are shown for a random generated diagonal maze, with the edges such that no path crosses an edge.

This text is displayed if your browser does not support HTML5 Canvas.

Below, I did this for a left/right turn maze. On every side of a square there is an 'entry' and 'exit' point. A square representing a right turn has four arcs connecting the 'entry' point (on the right) to the 'exit' point of the edge on the right. A sqaure representing a left turn has four crossing edges, where the 'entry' point is connected with the 'exit' point of the edge on the left. This results in two crossing mazes, which are coloured with red and blue. These look very similar with the one above, and it turns out that the statistics with respect to the length of the paths is very similar to the diagonal mazes.

This text is displayed if your browser does not support HTML5 Canvas.

Home | February 2013 | April 2013