Project III in developing distributed services

This report contains a C# web service implementation of assignment 2 from the previous project (source code). The assignment has one console applications which acts as a test client, the class library from the previous project and a web service implementation which uses the class library.

Here is the assignment description from project II: “Assignment 2: Programming some algorithms like bubble sort, linear search and binary search. The console application, which does some sorting and searching on some arrays of integers, is non-interactive.”

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

Enumeration of prime numbers 0.2

I’ve updated the Prime Time command line program to version 0.2. Changes includes a huge memory optimization and some minor performance optimizations. The computation time is reduced by about 12% so the test from the previous post (finding all primes up to the number 10 000 000) now takes only 4.602 seconds on average, compared to 5.211 seconds in version 0.1.

I also did a test on how long it took to find all primes up to 4 294 967 295 (the maximum value an unsigned 32-bit integer can hold) which took 5 hours, 17 minutes, 16 seconds and 70 milliseconds. The end result was a list of 203 280 221 primes. I ran the test without printing each individual prime to prevent disk IO operations from slowing down the process. Afterwards I ran the program with the – -print-primes option to write all the primes to a file. I ended up with a 2.2 GB large file and, when compressed with 7-Zip‘s most aggressive settings, it was reduced to about 200 MB. I choose the maximum unsigned 32-bit value because I knew that would go relatively fast on my 32-bit processor, but if you’re feeling adventurous you can crank it up to the maximum value of an unsigned 64-bit integer, which is the limit for the program. Just don’t complain to me when it never finishes. Both the binaries and source code is available for download.

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

Enumeration of prime numbers 0.1

The Prime Time command line program allows you to enumerate all the prime numbers up to a specified number and it also lets you know how long it takes. The binaries has been compiled for x86 as well as an x64 specific version. In addition to the binaries you can also download the source code which is licensed under the GPL version 2.0. The program is written in C# and so it requires that one of those .NET framework things are installed. I have no clue as to which version of .NET you need. All I know is that I wrote this in Visual Studio 2005.

If you are interested in benchmarks and performance metrics you might want to know that my Dell XPS M170 laptop (Intel Pentium M 2.13 GHz, 2 GB DDR2 PC4200) takes an average of 5.211 seconds to find all the prime numbers up to 10 million (not the 10 million first prime numbers, but all the prime numbers up to the number 10 000 000). I used the command line:

primetime --max-prime 10000000 --runs 10

It uses a very simple algorithm to enumerate all the primes. What it does is to divide each odd number, starting from 3, on every prime below it (well, actually every prime up to the square root of the number being tested). If all of the divisions has a non-zero remainder, then the number is added to the list of primes and the next odd number is tested.

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

Project II in developing distributed services

This project contains the solution to three C# programming assignments (source code). Each assignment has one or more console applications and associated class libraries which contains the actual business logic.

• Assignment 1: Modeling and programming the basic behaviour of a bottle. Filling, emptying and pouring the contents of one bottle into another. The console application is non-interactive.
• Assignment 2: Programming some algorithms like bubble sort, linear search and binary search. The console application, which does some sorting and searching on some arrays of integers, is non-interactive.
• Assignment 3: Program a poker and a dice game. Both of the console applications are interactive. In the dice game you bet a certain amount of money and if none of the four dices rolls a 1 you win. The poker game draws a hand of five cards, classifies it by how good it is and allows you to swap cards so that you can improve your hand.

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

Progress report for week 39

Good news, bad news. The bad news is that my laptop still hasn’t been fixed and I’ve had some trouble accessing the BOINC homepage lately, so I haven’t got a chance to download and test it for myself. I keep getting “connection timed out” when I’ve tried accessing it from school and at home.

The good news is that I’ve received two much needed reference books:

• “The C Programming Language, Second Edition” by Kernighan and Ritchie
• “The C++ Programming Language, Special Edition” by Stroustrup

I admit that I liked Kernighan and Richie’s book best because it’s about 700 pages shorter than the one by Stroustrup and it’s more to the point. I’m thinking about reading the C book from beginning to end because I like K&R’s writing style. Even though C++ is a more comprehensive language than C, a significant portion of the content in the C++ book feels superficial. It’s a good reference book, but not one that I would read from beginning to end. In that respect I prefer Bruce Eckel’s two “Thinking in C++” books.

I finally wrote the missing code for initializing the “boolean matrix circular quad-linked list” (BMCQL) data structure used by the DLX algorithm. That means that the libdlx library is more or less functional. However, not everything went according to plan. I spent about 6 hours to debug some silly mistakes I did in a couple of getters and setters. I was almost certain that I was doing something wrong with some of the pointers, but strangely enough they appeared to work without a hitch. On the bright side at least I gained a much better understanding of how pointers work.

A program using libdlx to solve exact cover problems has also been written. I’ve simply called it “dance”. It has been used to verify that the DLX algorithm has been implemented correctly. I’ve only tried it on a couple of small matrices I have written by hand, but I’ll soon test it on some n-queens problems as well.

By successfully implementing the DLX algorithm the first milestone of the project has been achieved. The completion of the second milestone will be announced as soon as I’ve been able to verify the correctness of the implementation by running it through some of the n-queens problems.

I’ve added some pseudo code to the report about the BMCQL data structure initialization and written more about the implementation. The dance program and the DLX library version 0.1 has been released on Google Code. The binaries are only available for Windows, but it shouldn’t be too much of a problem to compile it in Linux. A basic makefile will be added shortly.

Update: As you might notice I also figured out how to reorder the posts into reverse chronological order. Unfortunately I’ve been unable to find my way back to where this functionality is hiding so this post is stuck in the wrong position (at the bottom).

Update: After some research I found the ordering functionality. On the Portfolio page where you have a list of the portfolio elements you have to change the category. Use the drop down list on the right side and change it to “No category” (or whatever category you’re trying to sort) instead of “All” in order to access the ordering mechanism. Makes perfect sense, right?

Update: The BOINC homepage appears to be back online.

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

Progress report for week 37

In week 37 I’ve been working on the report and I’ve written about the architecture design and about exact cover problems and a bit about how the Dancing Links algorithm works. I’ve been looking into some of the other Dancing Links implementations which are released as open source and tried to see how they solved the problems. Most of the implementations were made for one specific purpose (solve sudoku, n-queens and polyomino problems). This is different from my implementation which will be a generic solver, but with direct support for some of the specific problems.

The file format which the problem matrices will be stored in has been sketched out, but I need to investigate what features the Grid middleware has for dealing with file transfer and reading. My main canditate is BOINC, but I’ll be checking out other possible options soon.

I’ve been a bit busy with another report so I’ve not been able to fully implement one of the problem transform like I had planned. Other than that everything is going according to the plan. I’ll make an extra effort to neutralize the slippage the following weeks.

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

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.