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.
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.
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 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;
}
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.
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.
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.
Palindrome date
Today is a palindrome date
when written in the (M)M/(D)D/(YYY)Y format: 2/10/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.
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.
At 14:01, I bought the following three books from the 75% off sale at bookshop Broekhuis:
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.
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.
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.
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.
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.
Palindrome date
Today is a palindrome
date for the date format DD-MM-YYYY, because for today
it gives 21-02-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.
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).
- I started studying Gizmo's Freeware: Best Free Rootkit Scanner and Remover
- I downloaded Kaspersky TDSSKiller
- I downloaded Avast Anti-Rootkit
- I downloaded GMER
- I ran GMER. It listed two items in the Rootkit/Malware tab. I have to
admit that I don't understand the two lines. At least it did not mark
any lines red and/or give a warning about a rootkit. The other tabs
contain some interesting tools. This is indeed a tool for the advanced user.
- I ran Kaspersky TDSSKiller. It didn't find anything, which is okay.
- I ran Avast Anti-Rootkit. Performed a QuickScan scan. It reported one
issue in yellow with respect to a service starting with MpKsl. From
the internet I understand this is part of MSE.
- I studied Best Free Intrusion Prevention and Detection Utility for Home Use
(HIPS)
- I studied Best Free Trojan Scanner and Remover
- I downloaded Emsisoft Anti-Malware 6.0
- I downloaded Malwarebytes Anti-Malware 1.60.1.1000
- Check boot device priority. First is 4M-SAMSUNG HD322HJ.
- Removed DVD drive. Now only Fourth IDE Master has disk.
- Attached infected drive. Shows up as Third IDE Master: SAMSUNG HD321KJ.
I cannot select HD322HJ as boot device.
- Swapped cables. Now 3rd is HD322HJ and 4th is HD321KJ.
HD322HJ is boot device. Okay, discovered that I could have
switched it in the BIOS. Booted without network connection.
- Booted 'clean' Windows XP. Immediately MSE pops-up. It detected
"Trojan:DOS/Sinowal.Q" on boot:\Device\Harddisk1\DR1. I did not
clean it.
- I started GMER and let it scan the files on drive F. I get
the message "Windows - Station not ready". Probably MSE is blocking
this.
- Let MSE clean the Trojan. MSE continues scanning.
- Restarted GMER scan.
- I downloaded Microsoft Standalone System Sweeper.
(Has been rebranded to Windows Defender Offline).
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.
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
New bedroom