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.
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.
Today is a palindrome date
when written in the (M)M/(D)D/(YYY)Y format: 3/10/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.
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.
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.
Webserver
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.
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.
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.
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.
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):
- Using modern techniques, it was revealed that there was far less DNA on
the blouse of Jacqueline Wittenberg than the Netherlands Forensic Institute (NFI) claimed in the their report.
- The report by the NFI contains calculation errors.
- Parts of the blouse that show signs of strangling contain less DNA of
Ernest Louwes than those around it.
- The expert report about the mobile phone reception is based on a
weather report three months later than the date of the murder. At the
suspected time of the murder, the weather conditions where such that
phone of Louwes could have been reached by said cell tower.
- There are not hundreds of cell towers along the route, but only three.
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:
- pessimistic concurrency control (with implied consistency enforcement)
- optimistic concurrency control with consistency enforcement
- optimistic concurrency control without consistency enforcement
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.
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.
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.
Amsterdam and Beijing
At 13:55, I bought the following two books from bookshop De Slegte;
- Scenic points Amsterdam by Eelco van Geene and M. Mooy,
ISBN:9789025748272 for € 4.99.
- Destination Beijing by Philippe De Baeck,
ISBN:9789079761722 for € 5.00.
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.
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.
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.
Home
| February 2013
| April 2013
Thursday, March 21, 2013