>The worst sort algorithm in the world!

>In interviewing candidates for programming jobs we have tried to come up with some unusual technical questions. Mostly this is to observe the person’s reaction to such a question and to see how they might try to solve the problem.

My latest favorite question in this vein is this: “What is the worst sort algorithm you can think of?” The more precise problem definition is that the algorithm must be guaranteed to terminate and that the input will be sorted. Typically bad sort is a bubble sort – whose execution complexity is O(N^2) in the worst case.

But can you do better? Or rather, can you do worse?!

Here is an algorithm that in the worse case is O(N!) – where N! stands for N factorial (i.e. N*(N-1)*(N-2)…2*1). It works like this:

  • Take random permutation from the set of permutations of N elements
  • Apply this permutation to the input
  • If not yet sorted, choose another permutation and go back to previous step

Since there are N! permutations of N elements, on average N!/2 permutations will have to be tried. So the execution complexity of this algorithm will be O(N!).

Just to try it out I wrote this sort in Ruby. Here is the code:


require "permutation"

class Array
# return true if array is sorted
def sorted?
return true if self.length <= 1
for i in 0..self.length-2
return false if (self[i] > self[i+1])
end
true
end
end

def worst_sort (a)
perm = Permutation.new(a.length)
while (perm.rank != perm.last)
sa = perm.project(a)
return sa if (sa.sorted?)
perm.succ!
end
end

I tried running this sort on my laptop and for an array of 11 elements it was taking so long that I lost patience and stopped the program.

If you look at the code above the most difficult part is generating permutations on N elements in order. I was lucky to find that the hard work was already done for me in the Ruby “permutations” module. You can find the source for this module here: http://permutation.rubyforge.org.

>Science Fiction – "Blood Music"

>Blood Music (by Greg Bear) tells a story of a brilliant, but quirky, bio-researcher Virgil Ulam. At the begining of the book Virgil is in trouble at work. He had strayed from the worked assigned to him and instead developed intelligent cells. When his boss finds out about his extra-cirricular projects, he orders him to shutdown it down and destroy all bio-matter. Virgil manages to keep a small sample of the super-intelligent cells in a fridge, and when he is fired from his job he injects himself with the organisms – with the plan to extract them when he gets a job at another lab.

Unfortunately, Virgil gets black-listed by his former employer, and is unable to quickly find another job. Meanwhile, his creations multiply inside his body. Initially there seems to be no particular effects of the injection, but after a week or two Virgil notices that his body is “improving”. His health gets much better, he taste changes and he looses weight. His stamina increases greatly – a fact appreciated by his new girlfriend.

But all is not well. Eventually Virgil begins to observe unusal effects within his body – for example a network of white lines just under the skin. Eventually he stops going out all together. In the end of the first part of the book, Virgil seems to go insane – he has “conversations” with the beings livining within his body – and eventually he seems to dissolve into a pile of bio-matter.

This is not where the book ends though. Turns out that the micro-organisms that Virgil created spread to others via exchange of fluids (including sweat).

The second part of the book describes what happens to the world as Virgil’s organism spread across the North American continent. This part of the story is told from several differnt points of view. There were few people in North America that were resitant to the “infection”, a girl in Brooklyn and few hippies in San Francisco.

Another person was a friend of Virgil who gets infected, but manages to get himself to a lab in Germany. There he is placed in isolation chamber. He experiences a slow transformation from a human being into the new kind of organism. Eventually, as he transforms, he is able to communicate with his “invaders”. Although the “invaders” consider him to be the entire “universe” and are suprized to discover at some point that there is an “outside”.

This was an odd book to read. It went from experiences of a single person to a collapse of the world. At first, I didn’t like the world-wide disaster that Virgil caused, but the story was engrossing that I continued reading.

In the end it appears that the age humans has finished and the new intelligent micro-life took over.

>Science Fiction – "Eden"

>”Eden” is one of the earlier books written by S. Lem. It was first published in the 60s. The plot is simple – a spacecraft crashes on the planet Eden, and the crew works on survival and repair, and little exploration. Eden is civilized, but our explorers have hard time figuring out what is going on.

For me the strength of the book lies in its descriptions of the alien planet, its plants, animals and the local intelligent beings. The crew calls them “doublers” – as they appear to be a combination of two different bodies.

The first order of business after the crash is for the crew to find some drinkable water, as the ship’s supply is mostly radioactive, and all purifiers are not yet working. This leads to initial explorations of the planet. They find some weird plants that can hide under the surface when disturbed, they discover breathing plants – they name these “lung trees”.

On one of the first trips they stumble upon a “factory” – a large structure that seems to be making something, but they are unable to divine the it’s purpose. The Engineer follows through the process, but the production process just seems to loop on itself – producing objects that are at the end thrown in the input hopper.

One odd thing about the book is that the characters do not have names, but are referred to by their function. We have the Captain, the Doctor, the Engineer, the Physicist, the Cybernetist (to manage the robots), and the Chemist. We only learn the real name of the Engineer – Henry.

As the story progresses the crew makes a contact with the “doublers”, but not particularly successful. As they accumulate observations they are unable to make any sense of what is going on. This, I believe, is the main point of the story – we as humans would have a very difficult time trying to explain a completely alien culture. We naturally tend to apply human patterns, and on an alien planet they do not make any sense.

Lem explores this idea in several of his other books: “The Invincible”, “Solaris” and much later in “Fiasco”. Of these, “The Invincible” is my favorite.

The beings on Eden appear to fence in and attack the crashed ship, but in the end our crew is able to leave Eden. Just before the departure, they do establish contact with a doubler, who appears to be a scientist, but the communication between them is imprefect and they get only an inkling of what has happened on Eden.

I liked this book, because it explores the idea of communication between us and aliens without the benefit of a universal translator.

>Do you remember your first program?

>The other day we were sitting at lunch reminiscing about how we got started in programming. Every person present had a different story. Here is the story of my first program.

It was the mid-seventies, also known as the Jurasic era of computing, and I was in college taking a physics class. I needed science courses for my future B.S. (Bachelors of Science) degree, so I took physics because I wanted to avoid chemistry. In the physics class we did occsional labs and our professor wanted us to write a computer program to process lab results.

Just to set the stage for the computing technology at the time remember there were no PCs. I had just gotten my first calculator, wich cost $40, not a small sum in the 70s. The calculator had a red LED display and only provided four operations: +, -, * and /. No square root. In fact I learned to use Newton’s method to extract square roots by hand. Mind you, my physics professor could do computations and estimates in his head faster than I could type them on my calculator.

In any case after one of the labs, he wrote some gibbrish on the board (starting with “//JOB “) and told us to get some punch cards, and go to the computing center and write and run a program. The program in question was to read seven numbers from its input and print the average. The programming language we were to use was called FORTRAN.

Step one was to buy blank punch cards at the college book store. They were sold in batches of 100. The I had to find the compuer center with the keypunch machines. A kepunch machine was a desk size thing with a typewriter keyboard and an elaborate mechanism for feeding in blank cards. Each letter you typed was encoded in a column of what seem like random holes in the card. If your particular machine had decent printing ribbon in place the character was also shown on the top. The funny thing was that it was hard to see what it was you were typing, so it was easy to make a mistake. Of course, you couldn’t fix the card – can’t fill in the holes – so a card was wasted and you had to start over.

Once you keypunched you program and the magical control cards that went in front of it, you brought your deck to the RJE – Remote Job Entry – station and handed your card deck though a window to a student employed at the computer center to be read in. He or she would do it immediately and hand you your deck back. The computer would attempt to run job later. The output, a folded print out, would be put on some shelves when it eventually came out.

Nobody told me that if you make a mistake in the control cards (JCL JOB card for you old timers) no output will be generated. So after having my deck read in I hanged out around the computer center wating for results. When nothig came out after what seemed like a reasonable time, I asked for help from one of the local “hackers”. He quickly identified my JCL error and told me how to fix it.

This eventually worked and I got my first program to run and print out a weird looking answer (things like: 000102E02 or some such).

So, what was your first program?