Sorting with Predictions
Authors: Xingjian Bai, Christian Coester
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | An experimental evaluation against existing adaptive and non-adaptive sorting algorithms demonstrates the potential of applying learning-augmented algorithms in sorting tasks. ... Finally, through experiments on both synthetic and real-world data, we evaluate the proposed algorithms against existing (adaptive and non-adaptive) algorithms. Results demonstrate their superiority over the baselines in multiple scenarios. |
| Researcher Affiliation | Academia | Xingjian Bai Department of Computer Science University of Oxford, UK xingjian.bai@sjc.ox.ac.uk Christian Coester Department of Computer Science University of Oxford, UK christian.coester@cs.ox.ac.uk |
| Pseudocode | Yes | Algorithm 1: Sorting with dirty and clean comparisons; Algorithm 2: Sorting with complexity on η i; Algorithm 3: Double-Hoover Sort |
| Open Source Code | Yes | The source code used for experiments is available at https://github.com/xingjian-bai/ learning-augmented-sorting. |
| Open Datasets | Yes | We also utilize data from a real-world setting. We draw the annual population ranking of countries and smaller regions from 1960 to 2010 from World Bank (2023). |
| Dataset Splits | No | The paper does not explicitly provide specific training/validation/test dataset splits with percentages or sample counts. It mentions 'synthetic data' and 'real-world data' but no detailed split methodology. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used for running the experiments (e.g., GPU/CPU models, memory). |
| Software Dependencies | No | The paper mentions 'Tim Sort (Peters, 2002), which is the standard sorting algorithm in a variety of programming languages' and 'Powersort (Munro and Wild, 2018), which recently replaced Tim Sort in Python s standard library', but does not list specific version numbers for software dependencies. |
| Experiment Setup | No | The paper describes synthetic data generation processes ('class setting' and 'decay setting') and mentions baselines, but does not specify experimental setup details such as hyperparameters, learning rates, batch sizes, or optimizer settings for their algorithms. |