General Algorithm Library (GAL)

I have published code for some general algorithms implemented in Java. Most of this work was done as part of the Algorithm and Complexity Theory (MID170) course at the University of Stavanger. The general algorithms umbrella covers most algorithms, but with a slight emphasis on flexibility and performance.

The first revision contains:

  • Dijkstra’s shortest path algorithm
  • Kruskal’s MST algorithm (incomplete)
  • Stable in-place quicksort
  • Union find for locating the k-th smallest key (not complete at all)
  • Sequence union for merging two sorted sequences into a set

You can grab a copy of the first release at the end of this post or you may fetch the smoking fresh, bleeding edge, bug ridden, latest revision directly from the Subversion (SVN) repository by the magic of the command line client:

svn checkout svn:// trunk

If you prefer a GUI client I recommend TortoiseSVN (Windows), RapidSVN (Windows, Linux, Mac) and Subversive (Eclipse plugin). You may also browse the latest and greatest code from the online FishEye repository viewer which provides a more developer oriented overview.

I welcome improvements that makes the algorithms more efficient or generally easier to use as long as the changes are relatively comprehensible. Hopefully more comprehensible than it currently is.

NOTE: This post has been imported from my old it’s learning ePortfolio project blog.


RSA and public-key cryptography

Here you can download the report (Norwegian) and the implementation (C# source code) of the RSA encryption algorithm Jens Otto Hatlevold and I did. It was done in 2006 for a project in the computer security course at the University of Stavanger. You can view the source code repository online with FishEye.

For the latest source code revision, point your SVN client to the following URL: svn://

NOTE: This post has been imported from my old it’s learning ePortfolio project blog.

Tetris and dominoes

Have you ever experienced deja vu? I just discovered that it’s most likely not deja vu, but rather a sort of precognition. Still, it’s a pretty strange sensation, and when they call it precognition you fell all Minority Report like. Let’s just be happy they don’t put us in a pool of water and hook us up to some supercomputer.

Twice I’ve got this sudden urge to know everything about tiling problems. The first time I didn’t know the proper terminology so I never really got started. I was driven by this puzzle game, IQ-Block, and somehow I just had to know how many solutions it had and if there was some established theory on the subject. On my second attempt I inevitably stumbled upon Colin Ramsay’s paper: The IQ-Block: an interesting polyomino puzzle. From there on I devoured about 20 more papers on polyominoes and related topics before my brain was forced to do a context switch1 (why on earth do we have to sleep all the time?), and I forgot all about it.

Actually, I believe it was my conscience that somehow convinced me that polyominoes weren’t “decent” enough. While I was sleeping my sneaking backstabbing conscience was crawling around my brain, replacing all references to polyominoes with pointers to exams and other school related material. At that time my next exam was more than five days away so I had plenty of time to practice anyway. No reason to get all medieval on my brain cells like that.

A polyomino is basically a collection of one (monomino) or more squares connected to form a geometric figure. Just like dominoes consist of two squares and blocks in Tetris (created by Alexey Pajitnov and named after tetraminoes and tennis) have four squares. A polyomino is naturally a figure with several interconnected squares and tiling (sometimes called tessellation in mathematics) is basically the act of combining several polyomiones with each other. When those polyominoes are of different shapes and sizes things become very interesting, both from the view of mathematicians and computer scientists.

One common tiling problem is to combine a given set of different polyominoes into a rectangle, or possibly even a square (or any other geometric shape for that matter) of a certain size. You know the total area of the square because you know the total number of squares each polyomino has, but you still have to put them together in the right way.

There is also a similar problem where you have to find the least amount of copies of a given polyomino that is required to tile a rectangle covering the least amount of space. This number is usually referred to as the polyomino’s (rectangular) order. Each polyomino might also have different properties that can be exploited in order to find solutions more efficiently. Then you have the problem of enumerating all the different of polyominoes of a given size, which is not trivial when you get to a certain size. Many of these problems are yet to be solved and this is what makes it interesting.

About one week ago I was checking out my wish list on Amazon and saw Polyominoes: Puzzles, Patterns, Problems and Packings by Solomon W. Golomb. Golomb is known as the inventor of polyominoes and so this book is the definitive guide. Needless to say, I simply had to buy it.

A few days later my lecturer in discrete mathematics mentioned that Douglas Rogers (a mathematician within the field of combinatorics) would be coming over (Norwegian page) for a talk and the topic would be Catalan numbers and tiling. Of all the possible places and things in the world, he was coming here and he was going to talk about tiling. It was like all the pieces in my own little puzzle were falling into place. The sequence of events that was unfolding was like a sign from a higher power. A power of a sufficiently large integer to say the least.

Douglas Rogers visited the Institute of Mathematics and Science here at the University of Stavanger (UiS) today (2007-01-23). I was the only student attending so I guess that leaves more knowledge for me and more problems I can solve without interference. Less people, more for me. That’s my basic trail of thought. More people dropping out of school, more work for me, and so on.

Rogers gave a talk about the sequence of Catalan numbers and how they relate to jigsaws, computer science and models for biological growth. He talked about different approaches to enumerate all n-ominoes for a given integer n and binary coding of polyominoes and rooted tree structures. At the end we finished up with a Douglas Adams joke involving the Catalan number 42 for which a certain type of problem was still unresolved.

Douglas Rogers referred to the following sources for further reading:

To summarize it basically went something like this: Deja vu, tiling, Coling Ramsay, IQ-Block, Solomon W. Golomb, polyominoes, Douglas Rogers, Douglas Adams, 42.

Now, where did I leave my copy of The Hitchhiker’s Guide to the Galaxy…

Notes on the bottom of my foot

1 Both No Silver Bullet (see section on time-sharing) by Frederick P. Brooks and Human Task Switches Considered Harmful by Joel Spolsky support the claim that context/task switching affects certain creative processes negatively.

NOTE: This post has been imported from my old it’s learning ePortfolio blog.