AG Algorithmen und Komplexität

Sommersemester 2017

Sebastian bietet im Sommersemester 2017 die Vorlesungen Advanced Algorithmics an.



Maximum Likelihood Java Bytecode Analyzer

MaLiJAn is a tool implementation of Maximum Likelihood Analysis introduced in Maximum Likelihood Analysis of Algorithms and Data Structures. It allows automatic average case analyses of Java Bytecode programs with arbitrary input distributions. The generated results may be in terms of abstract cost measures like number of comparisons in sorting algorithms (provided by the user through code annotations), or the exact number of executed bytecode instructions.

To try MaLiJAn out, simply download the client application below, extract the tar archive to some folder and run java -jar malijan-client.jar. For parts of the computations, MaLiJAn uses a Mathematica server backend hosted on our servers, so you will need internet access.

The example project shows an analysis of a classic Quicksort implementation in the random permutation model. There, MaLiJAn reproduces the expected numbers of swaps and comparisons known from the literature. It also determines the expected number of executed bytecode instructions to be roughly 18 n ln(n).


If you encounter any problems or you have suggestions relating to MaLiJAn please feel free to write an email to Sebastian Wild.


Detailed manual of MaLiJAn.

The MaLiJAn main application.

Needed for in-code cost annotations and custom InputProviders (not needed to try MaLiJAn).

Classic Quicksort Implementation w/ random permutations


Ulrich Laube and Markus E. Nebel, Theoretical Computer Science, Vol. 411, No. 1 (2010), 188-212

Sebastian Wild, Markus E. Nebel, Raphael Reitzig and Ulrich Laube, ACM-SIAM Meeting on Algorithm Engineering & Experiments 2013 (ALENEX13)

Ulrich Laube and Markus E. Nebel, to appear in Algorithmica (2015). DOI: 10.1007/s00453-015-9998-5