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

Dobravec, Tomaž (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: algorithm evaluation, algorithm modeling, experimental algorithmics, experiment reproducibility, open science, test case generation
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2026
• Št. strani: Str. 26-41
• Številčenje: Vol. 56, iss. 1
• PID: 20.500.12556/RUL-177845
• UDK: 004
• ISSN pri članku: 0038-0644
• DOI: 10.1002/spe.70020
• COBISS.SI-ID: 264024323
• Datum objave v RUL: 09.01.2026

Gradivo je del revije

• Naslov: Software : practice & experience
• Skrajšan naslov: Softw. pract. exp.
• Založnik: Wiley
• ISSN: 0038-0644
• COBISS.SI-ID: 5222919

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: vrednotenje algoritmov, modeliranje algoritmov, eksperimentalna algoritmika, ponovljivost eksperimentov, odprta znanost, generiranje testnih primerov