Automating algorithm experiments with ALGator : from problem modeling to reproducible results

Dobravec, Tomaž (author)

Background: Theoretical algorithm analysis provides fundamental insights into algorithm complexity but relies on simplified and often outdated computational models. Experimental algorithmics complements this approach by evaluating the empirical performance of algorithm implementations on real data and modern computing platforms. However, the absence of standardized, reproducible experimental environments limits the reliability and comparability of results. Objective: This work aims to establish a formal and reproducible framework for algorithm experimentation and to provide a practical platform that enables researchers to model problems, execute experiments, and share results transparently. Methods: We propose a comprehensive experimentation model that formalizes all key entities of algorithm evaluation, including inputs, outputs, test cases, test sets, parameters, algorithms, and performance indicators. The model is implemented in ALGator, an open-source system that automates test case generation, algorithm execution, output validation, and result presentation, while supporting collaborative development and public dissemination of experiments. Results: The capabilities of ALGator are demonstrated through a case study on the array-sorting problem. Experiments comparing Hoare’s and Yaroslavskiy’s Quicksort implementations reveal nuanced performance differences: Hoare’s version excels on random inputs without duplicates, whereas Yaroslavskiy’s performs substantially better when input data contain many duplicates. All experimental data and configurations are openly available through the ALGator platform. Conclusion: The combination of a formal experimental model and its open-source implementation in ALGator provides a robust foundation for reproducible experimental algorithmics. This approach promotes transparency, facilitates independent verification, and enables researchers to extend existing experiments with new test cases and performance metrics, advancing the reproducibility and reliability of empirical algorithm evaluation.

• Language: English
• Keywords: algorithm evaluation, algorithm modeling, experimental algorithmics, experiment reproducibility, open science, test case generation
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: Str. 26-41
• Numbering: Vol. 56, iss. 1
• PID: 20.500.12556/RUL-177845
• UDC: 004
• ISSN on article: 0038-0644
• DOI: 10.1002/spe.70020
• COBISS.SI-ID: 264024323
• Publication date in RUL: 09.01.2026

Record is a part of a journal

• Title: Software : practice & experience
• Shortened title: Softw. pract. exp.
• Publisher: Wiley
• ISSN: 0038-0644
• COBISS.SI-ID: 5222919

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: vrednotenje algoritmov, modeliranje algoritmov, eksperimentalna algoritmika, ponovljivost eksperimentov, odprta znanost, generiranje testnih primerov