Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
For the Algolab, we use
This page is here to help you to get these technical details out of the way as quickly and painlessly as possible.
The computer rooms CAB H56/H57 and HG E26.1 are equipped with the necessary software and are reserved for Algolab during the problem-of-the-week timeslot on Monday.
We recommend that you use the Fedora operating system on these machines. On those C++, BGL and CGAL should run fine and with recent versions.
The RedHat system on the machines in CAB also works, but the default boost packages are outdated. The recent ones (which are necessary for the MinCostMaxFlow implementations in BGL), are available but need to be activated. To activate them, execute this command in your terminal: scl enable rh-mongodb32 bash
Just download the most recent g++, boost and cgal packages from your favorite package manager. On Ubuntu for instance, just run
sudo apt-get install build-essential libboost-all-dev libcgal-dev cmake cmake-data
First install Xcode which includes a recent version of the LLVM C++ compiler. To install Boost and CGAL, we recommend homebrew which offers packages for both of them. To compile and link with the BGL, you need to provide the header path,
e.g. g++ yourcode.cpp -I /usr/local/opt/boost/include/ -o yourprogram
or you can just use the regular cgal_create_cmake script.
Getting everything to run with cygwin can be a pain. We recommend that you use our VirtualBox image, see below.
You can download a VirtualBox image with the libraries preinstalled here!
This tutorial is based on the virtual machine for the IFMP 2015 course by Christian Zingg.The goal of this virtual machine is to provide you with a hassle-free way to get started with the BGL and CGAL libraries for the Algorithms Lab.
We use Ubuntu as the operating system. A program called VirtualBox allows you to use it within your existing operating system. This guide is mostly for users of Windows and OS X. If you are using Linux, it's probably easier to just install the necessary packages for Algolab directly on your machine. But if you don't want to fill your machine with CGAL and Boost packages that you only need for the course, then this virtual machine (VM) might also be useful for you.
Important warning: Updating Ubuntu within the VM might lead to instabilities with VirtualBox. We recommend to just use the VM as it is.
Importing the Virtual Machine into VirtualBox
If you get an error when importing the appliance which says that the "compressed image is corrupted", then something probably failed when downloading the file algolab64.ova. In that case it should help if you just download algolab64.ova again. If that does not help, try another browser or do it while connected at ETH.
Where can I submit?
You can either use the 'submit'-links for each task on the moodle, or you can click on the name of any problem on the overview page of the judge.
I can not access the documentation on the judge?
The documentation on the judge is only available from within the ETH network. If you see "Error 403 - You don't have permission to access /doc/ on this server.", please use ETH VPN.
Run errors only on the judge
If you access your vector outside of its bounds, i.e. at V[V.size()], then many different things can happen. On your local machine, e.g. if it is running macOS, it might seem to run fine, your program reads a zero value and continues. On the judge however, your program most likely crashes and gets the verdict "RUN ERROR". Luckily, there is an easy way to locally check whether you run out of the bounds of any STL container: Just compile with the g++ flag -D_GLIBCXX_DEBUG. If you are using clang++ (default on macOS), then use -D_LIBCPP_DEBUG=0 instead.
Getting all of Boost to install and compile
If you are having trouble to get all the boost components installed on your system, there is an easy way out: The boost graph library (BGL) is header-only, so no installation is required. Just download the most recent version from the official website and link to it when compiling
g++ yourcode.cpp -I /path/to/your/boost/include/ -o yourprogram
Prim's Minimum Spanning Tree is buggy
If you are noticing buggy behavior of Prim's minimum spanning tree algorithm, then you should use a newer version of BGL. The version 1.54 was buggy.
Minimum Cost Maximum Flow algorithms are missing
If you are missing the cycle_canceling or the successive_shortest_path_nonnegative_weights algorithm, then your boost version is outdated. You need at least version 1.55.
No support for bundled properties
Bundled Properties could be nice to cleanup the template code in our graph definitions. Unfortunately, there is no obvious way on how to make them work with the flow algorithms that we need for the course, so we currently recommend that you do not use them.
C++11 features and cmake
The cgal_create_cmake script that we recommend you to use for the CGAL problems does not compile with the C++11 flag, unless you are using a very recent CGAL version. This might cause weird compiler errors when your code uses C++11 features like auto or range-based for loops. This is how you can enable C++11 support in that case:
- run cgal_create_cmake_script
- manually add a line with set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") at the end of the file CMakeLists.txt
- then run cmake . and make as before
Can I bring my own keyboard?
No.
What material is available during the exam?
Everything on the documentation page of the AlgoLab judge (lecture slides, code templates, library manuals) is available during the exam. The moodle and your past submissions are NOT available. If you would like to propose some helpful scripts to all the students to be added here, please post it in the Moodle forum.