Algorithms und Data Structures
Summer Term 2022
Fabian Kuhn

 

Daphne

The programming exercises have to be programmed in Python and submitted via Daphne. Your Python scripts should include unit tests. These tests as well as a style check will be executed automatically by the build-server Jenkins after you committed the file to the SVN server.

Subversion (SVN)

After your registration to this course, a SVN repository will be created for you, having an URL of the following form:

https://daphne.informatik.uni-freiburg.de/ss2022/AlgoDatCond/svn/your-rz-account-name/

Additionally, there is a public repository (named public) where we provide files that you need for your solutions:

https://daphne.informatik.uni-freiburg.de/ss2022/AlgoDatCond/svn/public/

For these repositories you should make a "checkout" to get a local copy on your pc. Through the command "update" you synchronize your local public folder with the current version on the repository. Through the command "commit" you upload your local files to your repository on the server. A more detailed overview can be found here. There are different subversion clients you can use. For Windows Tortoise-SVN is recommended.

Python

To write your programs in Python, you need a Python interpreter (we use Python 3). Additionally, you should install the style checker flake8. The style checker checks if your program is written according to the convention PEP-8. This is mandatory for a sucessful submission of your programing exercises.

You should use the program make to execute the Python interpreter, the style checker and the unit test. To use the make program, you must copy the file Makefile (from the Coding Standards or the public repository) into your local folder exercise-xy. The Makefile from the public repository is designed for using doctest for unit tests, the one from the coding standards uses the library unittest. Both procedures are feasible.
For the style check, you should execute make checkstyle. Unit tests using doctest are written directly as a comment at the beginning of each Python function. For unit tests using the library unittest you must write a file ending with Test.py (make looks out for such files for the tests). In the examples of the coding standards you can see how these unit tests should look like. The command make test executes the unit tests. Style check and unit tests can also be executed together with the commands make or make all. Python will automatically create additional files which should be deleted before you add your files to the SVN repository. This can be done with the command make clean.

Jenkins

To be checked automatically by Jenkins, your files must be stored in a subfolder exercise-xy of your personal SVN repository, where xy is the number of the respective exercise sheet (one-digit numbers with a leading zero, i.e., 01, 02,...). After uploading this folder (including Makefile) to the SVN server, Jenkins executes a style check und the unit tests.

Jenkins gives a feedback for the tests on the Daphne website. If all tests have been successful, you will see a green checkmark. A red cross indicates an error. Clicking on it opens the Build-Logs from which you may deduce the error.

Gnuplot

For some practical tasks, you should evaluate the runtimes of your implementations by creating and submitting plots. We do not make any specifications about the software that you should use for this, but since we use gnuplot in the lecture and for our solutions in the exercise, we provide a small instruction manual (at the request of students, supplementary to our verbal explanations) in which the most important steps are explained again in writing.

The software Gnuplot and some information about installation for various operating systems can be found hier. In many operating systems, Gnuplot can be installed with a single shell command (if you use OSX / Linux and the package manager homebrew, for example, brew install gnuplot is sufficient).

First you have to generate the relevant data that you can plot. In the lecture we have our Python programs make a corresponding output that corresponds to a cloud of 2D points of the form X Y. The coordinates X Y are separated by a white space, with a line break between two pairs. X usually represents the input size and Y the runtime. For details on the output in the Python code, please see the Python source codes that we provide with the first exercise sheet and the demonstrations in the first lecture.

The output of the Python program can then be redirected to a text file as follows: python3 file.py > plot.txt. The corresponding plot.txt output can now be directly converted into a graphic in gnuplot. To do this, start gnuplot in your respective command line and type the command plot 'plot.txt'. That’s it. Gnuplot will generate a corresponding point cloud with automatically adjusted axis scaling.

You may want to display multiple plots in one graph due to improved comparability. If you already have the corresponding files plot1.txt and plot2.txt available, simply use plot 'plot1.txt', 'plot2.txt'. You can also give these plots a title by plot 'plot1.txt' title 'plot 1', 'plot2.txt' title 'plot 2'. If the key hides the graphic, you can move it, e.g. to the left with set key left. Furthermore, it could sometimes improve the overview if you choose a logarithmic y-axis. You can do this simply by typing set logscale y. You can (and should) label the x and y axes using set xlabel 'input size' or set ylabel 'elapsed time in ms'.

Gnuplot is of course much more powerful than what we can explain here. You can get a much deeper description of the possibilities of Gnuplot (among others) here.