Progress report for week 36

In order to expand my limited knowledge of C/C++ I’ve started to read and use the following books as reference material:

  • “Thinking in C++, Volume 1, 2nd Edition” by Bruce Eckel (free version)
  • “Effective C++, 3rd Edition” by Scott Meyers
  • “Sams’ Teach Yourself C in 21 Days, 4th Edition” by Peter Aitken and Bradley L. Jones

I’ve also read an article or two in the book “Game Programming Gems” (edited by Mark DeLoura) while looking for a good way to store and manipulate the boolean matrices for the DLX algorithm. I’m leaning towards using Andrew Kirmse’s code from the “Simple, Fast Bit Arrays” article which has a license on the following form: “As long as you keep the copyright notice you can do whatever you want with it”. Not sure how that will interact with the GPL license I’m using, but I’ll figure out something.

I’ve checked out Donald Knuth’s own DLX program: dance.w. He uses a system called CWEB (hence the .w) to write his programs so I had to download, compile and run that in order to convert dance.w into dance.c. Then I could finally compile it. With my limited C knowledge I only understood bits and pieces, but I’ll keep trying as I┬álearn more. I could argue that I don’t understand everything because he uses a handful of GOTO statements, but that’s not where I get stuck. Still, I don’t┬áthink Dijkstra would have approved of those GOTOs. Knuth has also written a more general version of the DLX program named gdance.w, but I’ll visit that after I’ve intellectually conquered dance.w.

My own implementation of the DLX algorithm in C++ is also complete. I’ve spent more than a few hours trying to befriend C++ and I think I’m finally getting the hang of it. I’ve implemented the algorithm as a shared library (.dll in Windows .so in Linux) by following the pseudo code from Knuth’s paper. My code uses the same variable names and it follows the same structure as in the paper. The storage, manipulation and transformation algorithms which takes the input boolean matrix and turns it into a collection of objects is still under development. This means that I’ve not actually tested the DLX implementation, but seeing how similar it’s to the pseudo code there is a fair chance that it might actually work.

I’ve also reread the paper “PRP – Parallel Recursive Procedures” by Arne Maus and Torfinn Aas in order to get some more ideas on how to parallelize the DLX algorithm. As I was implementing the DLX algorithm I wrote a bit about the implementation and some other challenges which are yet to come. Currently the progress on the project is as scheduled by the project plan.

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

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://svn.podzone.org/svnroot/algorithms/trunk 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.