AG Algorithmen und Komplexität
>

ECCB 2014

Prof. Nebel ist Mitglied des Programmkomitees der European Conference on Computational Biology, die in diesem Jahr in Straßburg stattfindet; Details siehe hier.


 

ANALCO Minischool

Zusammen mit Conrado Matinez (Barcelona) wird Prof. Nebel auf dem ACM-SIAM Symposium on Discrete Algorithms 2014 in Portland eine Minischool zum Thema Analytic Combinatorics organisieren und dort das Thema Analytic Combinatorics in Bioinformatics unterrichten. Details können hier nachgelesen werden.


 

Sommersemester 2014

In diesem Semester bietet die AG die Vorlesungen Algorithm Engineering und Algorithmen der Bioinformatik 2 - Signale, Phylogenien und Strukturvorhersagen an.

Details zu den Inhalten finden Sie in den entsprechenden Seiten der Rubrik Lehre.


 

AofA 2014

Prof. Nebel ist Mitglied des Programmkomitees der diesjährigen Tagung zu probabilistischen, kombinatorischen und asymptotischen Methoden zur Analyse von Algorithmen. Details zur Konferenz können hier nachgelesen werden.


 

PARC

Am 15. zund 16. April 2014 findet an der Simon Fraser University, Burnaby CANADA, ein PIMS Workshop zum Thema Analytic RNA Combinatorics statt. Prof. Nebel wird dort einer der Referenten sein, Details zum Programm können hier nachgelesen werden.


 

MaLiJAn

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).

Contact

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

Downloads

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

References

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, SIAM Meeting on Algorithm Engineering & Experiments 2013 (ALENEX13)