This web page accompanies our conference paper "Inducing Suffix and LCP Arrays in External Memory", which we presented at the Workshop on Algorithm Engineering and Experiments (ALENEX 2013). A PDF of the publication is available from this site as alenex13esais.pdf or from the online proceedings. The paper was joint work with my colleagues Johannes Fischer and Vitaly Osipov.

The slides to my presentation of the paper on January 7th, 2013 in New Orleans, LA, USA is also available: alenex13esais-slides.pdf . They contain little text and an example of the eSAIS algorithm with a simplified PQ.

Our implementations of eSAIS, the eSAIS-LCP variants, DC3 and DC3-LCP algorithms as described in the paper are available below under the GNU General Public License v3 (GPL).

The algorithm implementations requires a special version of the STXXL library, which is also listed above. For more information about compiling and testing the implementation, please refer to the README included in the source.

This semester I had the pleasure to take part in a lab exercise course supervised by Prof. Thomas Linß at the FernUniversity of Hagen. The objective was to comprehend, implement and evaluate a particular recent advancement in the field of numerical mathematics. My topic was finding the roots of a polynomial by clipping in Bézier representation using two new methods, one devised by Michael Bartoň and Bert Jüttler [1], the other extended from the first by Ligang Liu, Lei Zhang, Binbin Lin and Guojin Wang [2].

My implementation of this topic was done for the lab course in C++ and contains many in themselves interesting sub-algorithms, which are combined into the clipping algorithms for finding roots. These sub-algorithms may prove useful for other purposes, which is the main reason for publishing this website. Among these are:

• Polynomial classes for monomial and Bézier representations: PolynomialStandard and PolynomialBezier.
• Algorithms to convert from monomial to Bézier representation and vice versa: PolynomialStandard::toBezier() and PolynomialBezier::toStandard().
• Evaluation algorithms for both representations: Horner's Schema and the Algorithm of de Casteljau.
• Another version of de Casteljau's Algorithm to split a polynomial in Bézier representation into two parts.
• Jarvis' March aka gift wrapping (run time O(hn)) to calculate the convex hull of the Bézier polygon: PolynomialBezier::getConvexHull().
• Cardano's formulas to find all real roots of any cubic polynomial: PolynomialStandard::findRoots().

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf (6 pages). The report contains a short description of the algorithms together with execution and convergence speed measurements, which verify the original authors experiments. For presenting the lab work I created these Slides.pdf , which however are not self-explanatory due to my minimum-text presentation style.