Previous Up Next
Dutch / Nederlands

Dairy, February 2012



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


Thursday, February 2, 2012

Sorting with partial relation

In the afternoon, I improved a sorting algorithm written by a colleague for sorting an array with a partial relation, which might be non-transitive. The traditional definition of partial order (see Wikipedia) includes the transitivity requirement. The algorithm here works on a smaller-than relation (which is also not reflexive) and sorts an array of unique values such that afterwards there are no two elements placed in the wrong order with respect to the smaller-than relation. The non-transitive partial relation is comparable to acyclic directed graphs with labels. The number of such relations on n elements is given by the integer sequence A003024: "Number of acyclic digraphs (or DAGs) with n labeled nodes." I think that the algorithm is also stable, meaning that it doesn't unnecessary changes the position of elements. The following C++ fragment gives the algorithm, where "a" represents the array to be sorted and "n" the number of elements. The function "before" returns true when the first argument should appear before the second and the function "swap" swaps the contents of the two arguments.

for (int c = 1; c < n; c++)
    for (int i = 0; i < c; i++)
        if (before(a[c], a[i]))
        {
            for(; i < c; c--)
                swap(a[c-1], a[c]);
            break;
        }

I haven't tested the above implementation yet. The central idea of the algorithm is that all elements from 0 to (but not including) c are correctly sorted. I am not sure whether this is the optimal algorithm.


Friday, February 3, 2012

Little snow

This morning around 11:20, it started to snow, but only very light. It continued for some hours, and also in the evening there was some more, but the total was just a few milimeter of snow. In the rest of the country there was a lot snow leading to second worse evening traffic jam (and fourth worse overall) on record and problems with the trains.

Improved sorting algorithm

I found, what I think is, an improvement on the algorithm that I talked about yesterday. The idea is that once you have concluded that the element at c needs to placed before the element at i, you move it to the front and compare it with every element that you encounter. If there is an element that needs to be placed before it, you keep it in front and also move it with you. The elements b to e are the elements that are moved to the front. With every step moving it to the front, you try to move the next element before it through the group, while comparing it. If it moves through, it is okay, otherwise it is made part of the group that of elements that moves to the front.

for (int c = 1; c < n; c++)
  for (int i = 0; i < c; i++)
    if (before(a[c], a[i]))
    {
      int e = c+1;
      for (int b = c; i < b; b--)
      {
        int j;
        for (j = b; j < e; j++)
          if (before(a[j-1], a[j]))
            break;
          else
            swap(a[j-1], a[j]);
        if (j == e)
          e--;
      }
      break;
    }

However, this algorithm is not stable. I think that the next algorithm is:

for (int c = 1; c < n; c++)
  for (int i = 0; i < c; i++)
    if (before(a[c], a[i]))
    {
      int e = c+1;
      for (int b = c; i < b; b--)
      {
        bool pass = true;
        for (int j = b; j < e; j++)
          if (before(a[b-1], a[j]))
          {
            pass = false;
            break;
          }
        if (pass)
        {
          for (int j = b; j < e; j++)
            swap(a[j-1], a[j]);
          e--;
        }
      }
      break;
    }


Saturdag February 4, 2012

Winter sale

Today, I discovered that bookshop Broekhuis were having a winter sale. From the fact that there was a discount of 75%, I think that today will be the last day of the sale. I looked around, and for a while had the book "Het origineel van Laura" (The original of Laura) in my hand, but in the end, at 12:51:56, I only bought the book "Twente: tekeningen in zwart" with pen drawings by Jacq de Groot (ISBN:9789070162191), which I found outside on their permanent display of books on sale, for € 5.


Tuesday, February 7, 2012

Stability of sorting

Yesterday evening and today, I did some extensive testing on the sorting algorithm presented before. And the algorithm passed all the test that I implemented (C++ sources). The algorithm is indeed stable, but only for those elements that have no relation with each other, and some other special cases. This can be seen from the fact if one has the sequence "A B C" where the only requirement is that C should be before A. In that case there are three possible to 'sort' the sequence, namely: "C A B", "C B A", and "B C A". In only two cases B is placed either before C or after A. And there is also no objective criteria to select one of the sequences as the 'best' sort.


Wednesday, February 8, 2012

The Original of Laura

At 11:34, I bought the book Het Origineel van Laura (Dutch translation of The Original of Laura) by Vladimir Nabokov (ISBN:9789023441502) from bookshop Broekhuis) from their 75% off sale for € 7.48. It is not the copy that I had in my hand last Saturday because I remember that it had a torn in the dust jacket.


Friday, February 10, 2012

Palindrome date

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


Saturday, February 11, 2012

Water

I finished reading the book "Water | Wasser | Eau" by Joachim Fischer, ISBN:9783833150241. I started reading this book on Sunday, January 29, after I bought it the day before from bookshop De Slegte. The book is about buildings that use water as an architecture element, either by being close to water or using water inside/around the building. I enjoyed reading all the descriptions and study the pictures.

New bedroom

Over the Christmas holiday, Annabel and I swapped bedrooms. We are both happy with our new bedrooms. I have put five bookcases in the room and filled them with my books and belongings. I have put the bed somewhat in the middle of the room. There is a desk before the window and two smaller cupboards near the window. I took three pictures: one looking into the room from the window, one with the view from my bed, and one showing the bed and the bookcases near it. Behind my bed is the first Dutch book poster of the literary novel "Oeroeg" by Hella Haasse.

75% off

At 14:01, I bought the following three books from the 75% off sale at bookshop Broekhuis:


Monday, February 13, 2012

Little snow

This morning, there was a little snow everywhere, which must have fallen during the night. Yesterday, there was still some snow left in the back garden from the little that fell on Friday, ten days ago. This morning, the Royal Netherlands Meteorological Institute issued an exterme weather warning because of black ice in some parts of the country. Around noon all the snow had melted. The cold periode is over by now. This might have been the last snow for this year.

The Dutch Tongue

This evening, I finished reading The Dutch Tongue: how Nancy learns Dutch thanks to Thomas by Ben van der Have (ISBN:9789055946334), which I started reading last Saturday, the day I bought the book. This book is different from other books for learning the Dutch language, and not in the first place because material is presented in the form of a story. This book can be best viewed as a book about linguistics, where Dutch is taken as the main example language. Examples from other languages are also included.


Friday, February 17, 2012

Replacing harddisk

Today, I have come to the conclusion that the harddisk of johan is contaminated with a very dangerous virus, possibly even a rootkit. I have automatic updates of Windows XP switched on and I am running Microsoft Security Essentials. Last week we noted that the computer suddenly restarted by itself. It also started having problems with hanging during the startup of windows, usually shortly after the Windows Logo disappeared and before the blue screen appeared. The mouse cursor would be in the middle of the screen and the system would become unresponsive. Pressing the reset button for a few seconds would switch it off. Most of the times it would start-up normal the second time. I assumed that it was related to some hardware issue and due to old age. I guess, I might have been wrong. I let MSE run an extra virus scan after I read something on the internet that the behaviour might be related to a virus. I also noticed that internet was getting slower lately. I wonder how the virus/trojan got in because I feel that I have been quite carefull with respect to security. I guess, I even have to be more secure. The coming time, I will be busy with installing software, I am afraid, and also thinking about how to avoid this in the future. Luckily, I still have the netbook, which I consider safe.


Saturday, February 18, 2012

Reviving lixia

Today, I spend a lot of time getting our computer lixia to work again by reinstalling Windows XP from the recovery disk. Since Sunday, July 11, 2010, it would get into an endless loop when starting-up. I noticed that the boot partition of the first drive was marked as unknown, and was left with no option than to perform a format. After I got XP installed, I performed all the necessary security updates and installed Windows Security Essentials. I did perform a virus check on my ScanDisk Cruzer® Mirco 16GB USB drive, which did not find anything harmful. Everything seems to work again, except for the sound. I tried to install the 'multimedia' hardware, but it failed. Andy has been using it to surf the internet.


Sunday, February 19, 2012

Wet snow and rainbow

This afternoon, I went walking with Li-Xia. First it started to rain a little, but then (around 15:33) there was some wet snow in the form of very light hail. The sun was shining and I looked for a rainbow. I only saw a very small and faint fragment. Li-Xia did not see it. When we were almost back at the nursing home, it started to rain and while we enter the property we saw a full single rainbow against the grey cloulds, while to our left the sky was largely blue.


Tuesday, February 21, 2011

Palindrome date

Today is a palindrome date for the date format DD-MM-YYYY, because for today it gives 21-02-2012.


Tuesday, February 28, 2012

The Flatiron building

On the wall of our office we have a large poster from IKEA of the Flatiron building made by Angelo Cavalli. It seems that this picture is taken from the Empire State Building. I tried to find this position in Google Earth, which resulted in this KML file.

Fixing johan

I decided to make an attempt to remove the trojan/rootkit from the infected disk from johan that I removed on February 17. I installed Window XP on the replacement disk and also Microsoft Security Essentials (MSE).


Wednesday, February 29, 2012

Fixing johan (part 2)

The GMER scan that I started yesterday on johan continued during the night. When I opened the computer, a blue screen appeared and the PC rebooted before I could read the message. Started MSE scan on drive F. Quickly reported the presence of some dangerous software. After more than 3 hours scanning, MSE reported the following infections: It would not surprise me if it was the PWS:Win32/Sinowal.AJ infection through which Trojan:DOS/Sinowal.Q was installed on the MBR. It is possible that the other exploits (except for the two false positives) where acquired after MSE had been 'disabled' by Sinowal.Q.

My confidence in MSE has not been harmed, but I realize the reality that no virus checker never can give guarantee 100% security and that trojans cannot be avoided if you surf the internet. I am thinking about keeping the disk with the fresh install of Windows XP inside the PC and use it to scan the other disk on regular intervals. Of course, I have to keep it disconnected most of the time, because I expect that some trojans will infect the MBR of all connected hard disks.

Playing Go

This evening, I went to the university to play Go. I was the first to arrive. First Rudi came and a little later Huub. It has been some time ago that I saw them. I was decided that I played against Huub. I played with black and I did not expect much of it. About half way the middle game, Huub felt that I was far ahead, although I had not felt that way. This made me a little optimistic and I made some stupied moves losing a lot of points. But then I made some cut, and because Huub did not immediately see the threat of this cut, he did not make the necessary defense move, and I easily could kill a large group, and he resigned. We replayed some parts of the game and Rudi made some comments about our play, pointing out beter moves.


This months interesting links


Home | January 2012 | March 2012 | Random memories