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.

Advertisements

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.

Eclipse CDT and shared libraries

I had some trouble getting Eclipse CDT (C/C++ Development Toolkit) to work across separate projects. My setup is Eclipse 3.3.1 with CDT 4.0.1 on Windows with the MinGW toolchain. I have two separate projects in Eclipse: One is a shared library and the other is an executable. The executable uses the shared library so naturally it needs to read the header files from the other project in order to sucessfully compile and link. It would also be nice if it was possible to use the Run As Local C/C++ Application feature without the need to copy the shared library file to the directory where the executable file is. I set out on a quest to find the answers.

The first thing you have to do is right-click on the executable project in the Project Explorer, and then go to Properties -> Project References. There you have to select the shared or static library project you want to link to. Then click OK. If you try to build the project it still won’t work because it cannot find the required files.

Let’s open the project properties window again, but this time go to C/C++ General -> Paths and symbols -> References. Make sure that you select the shared/static library under all your configurations. The standard setup contains the Debug and Release configurations which you can switch between with the dropdown list at the top of the window. To make sure that you always link against the Release version of the library when you build the Release version of your executable you can expand the library reference node and select Release instead of the default [Active] selection. The same thing goes for building against the Debug version of the library when you’re building the Debug version of the executable. Click Apply when you’re done.

You might think that everything should be good to go by now, but we have a bit more to do first. In the project properties window go to C/C++ Build -> Settings -> Tool settings -> MinGW C++ Linker -> Libraries. Click the document with the green plus sign (Add button) right next to where it says Libraries (-l). In the input box that appears you should type the name of the library without its file extension. If your library file is “useful.dll” or “useful.so” then you should only type “useful”. Don’t forget that you have to do this for both the Release and Debug configurations if you don’t want any nasty surprises later on. Click OK when you’re done.

At least now it should compile, but you would maybe like to run it from within Eclipse as well? First you have to create a so called run configuration for your executable. Right-click on the executable in the Project Explorer and go to Run As… -> Local C/C++ Application. This will actually launch the program, but it will also automatically create a run configuration for it. The program will terminate without any error messages because it couldn’t find the library file. On the top menu go to Run -> Open Run Dialog…, select the run configuration for your program (if it isn’t already selected, obviously) and go to the Environment tab. Click New…, name the new environment variable “Path” and give it the value “${env_var:Path};${workspace_loc:/useful/Debug}”. Substitute “useful” for the name of your shared library. This will modify the system environment “Path” variable by adding the full path to the library so that the executable will find it.

If you want to use the Release version of the library then just substitute “Debug” from the environment value with “Release”. Unfortunately I haven’t found a way to detect which build configuration is active so you have to manually change this value if you switch between Debug and Release. An alternative is to create a separate run configuration for Debug and Release. This can easily be done by right-clicking on the run configuration and clicking Duplicate.

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

Guns and ammo

In C, you merely shoot yourself in the foot.

In C++, you accidentally create a dozen instances of yourself and shoot them all in the foot. Providing emergency medical care is impossible, because you can’t tell which are bitwise copies and which are just pointing at others and saying, “That’s me, over there.”

Borrowed from: Const Correctness in C++

NOTE: This post has been imported from my old it’s learning ePortfolio 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.

Progress report for week 35

The DECS project was started on 2007-08-27 as a computer engineering project at the University of Stavanger, Norway. The final report must be delivered by 2007-12-14.

During the last week I have registered DECS as a project on Google Code which provides version control by Subversion, a simple wiki, issue tracking and a release management system. I’ve worked on setting up my C/C++ development environment by installing Eclipse with CDT (C/C++ Development Toolkit) plus MinGW and MSYS for the tool chain (compiler, linker, make, gdb, etc.). I’ve made a draft of the system architecture with MS Visio 2007 and a project plan with MS Project 2007. I also made a draft of the report structure as well as rereading Donald Knuth’s Dancing Links paper.

NOTE: This post has been imported from my old it’s learning ePortfolio DECS 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://svn.podzone.org/svnroot/crypto/trunk

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