Previous Up Next
Dutch / Nederlands

Diary, January 2015

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  31

Friday, January 9, 2015

The Man Who Knew Too Much

I finished reading The Man Who Knew Too Much, an biography of Alan Turing, by David Leavitt. I bought this book some years ago. The prime motivation to read it, is that I had read that the movie The Imitation Game has some historical inaccuracies, and I wanted to know these before I went to see the movie. My first remark is that editors should consult a mathematician with respect to mathematical formuleas as the book contains a number of inaccurately typeset mathematical formuleas. These are some very basic formuleas: like using a double quote for the superscript 11, and using a subscript when a superscript should be used. This biography suffers from the fact that there periods in the life of Turing where there is not much known about him, that are filled with stories about other people, event and such. The book also explains some of Turings papers in great details. But these are almost unavoidable, and thus expected in such a biography. I did have a problem with some of the suggestions that the author made about how Turing could have experienced what happened in his life. I found some of these too suggestive, as if the author wanted to tie together everything in the life of Turing into a single process, as if that is even possible in a normal life of a person.

Saturday, January 17, 2015

Book sale

At bookshop Broekhuis they are having a sale with 50% off for a large collection of books. I also looked at the large collection of second hand books that they acquired. At 17:24:01, I bought the book Logbook 1991-1992 by Harry Mulisch, ISBN:9789023428367, for € 9.45, which contains the diary of Harry Mulisch that he wrote when working on his novel De ontdekking van de hemel (The discovery of Heaven).

Saturday, January 24, 2015


This morning, there fell about 6 cm (2.4 inch) of snow. In the afternoon, the sun started to shine and it the snow started to melt.

Saturday, January 31, 2015

Merging moves in trees

The kind of trees we are dealing with have a single root node and nodes are placed in levels depending on their 'distance' from the root. It could also be said that it is a tree with a parent-child relationship. (A concreet example of this kind of tree is found in a directory structure with folders and files, where both folders and files represent nodes in the tree, the files being leave nodes.) When a single user is making changes to such a tree by each time moving a single node to a new 'parent' where the parent is not one of its own 'descendants', the tree will always remain a tree with nodes placed in levels (possibly different level for some of the nodes each time a node is moved). If a user would be allowed to move two nodes with the above restriction, then it is possible to break the organization of the tree, where it breaks in two part, with one part containing the root node and still being proper and the other part being cyclic, where a chain of nodes are all each owns descendants.

If two users in isolation move nodes around, such that the tree remains well organized, it is not always possible to merge their changes without the tree falling apart in two or more pieces. Of course, there is already a problem when both users move the same node to a different parent. Combining the moves of two users is similar to one user being allowed to make two moves at the same time. The clasical example is tree, using the prefix with children between brackets notation: A(B(C),D(E)), where one user moves D under C, resulting in the tree A(B(C(D(E)))), and the other user moves B under E, resulting in the tree A(D(E(B(C)))). When both moves are combined (merged), this results in a lonely A node and an cycle consisting of B, C, D, and E.

There is no additional complexity in merging the moves of more than two users. In case there is a problem with merging the results of more than two users, there is always a minimal set of users whoes moves cannot be merged. Minimal in the sense that there is no subset of this set which cannot be merged. Because of this one could divide the users of the minimal set in two (non-empty) groups that can be merged. Merging the combined moves of these two groups is similar to the two user problem. It should be noted that it is possible that a large group of user could be combined without problems. Taking the above example, lets assume that there is a third user who moves E to A resulting in the tree A(B(C),D,E). Combining the moves of these tree users results in the tree A(E(B(C(D)))). There are good reasons to require that the moves of a set of users can only merged if any subset (or at least two users) can be merged into a proper tree. One reason being that if this requirement is stated, the moves of the users can be pairwise merged in any order.

The design of a locking mechanism to enforce that moves being made by a group of users can always be merged in any possible order, is far from trivial, especially if it needs to be efficient in time and space. There is a whole range of fine-grained to coarse-grained locking mechanism. One should take into the likelihood of multiple users applying moves to the same part of the tree. It is useless to implement an expensive fine-grained locking mechanism if the likelihood is low.

This months interesting links

Home | December 2014 | February 2015