Rosiane de Freitas

Isac M. Lacerda, Eber A. Schmitz, Jayme L. Szwarcfiter et al.

This paper presents an empirical performance analysis of three project scheduling algorithms dealing with maximizing projects' net present value with unrestricted resources. The selected algorithms, being the most recently cited in the literature, are: Recursive Search (RS), Steepest Ascent Approach (SAA) and Hybrid Search (HS). The main motivation for this research is the lack of knowledge about the computational complexities of the RS, SAA, and HS algorithms, since all studies to date show some gaps in the analysis. Furthermore, the empirical analysis performed to date does not consider the fact that one algorithm (HS) uses a dual search strategy, which markedly improved the algorithm's performance, while the others don't. In order to obtain a fair performance comparison, we implemented the dual search strategy into the other two algorithms (RS and SAA), and the new algorithms were called Recursive Search Forward-Backward (RSFB) and Steepest Ascent Approach Forward-Backward (SAAFB). The algorithms RSFB, SAAFB, and HS were submitted to a factorial experiment with three different project network sampling characteristics. The results were analyzed using the Generalized Linear Models (GLM) statistical modeling technique that showed: a) the general computational costs of RSFB, SAAFB, and HS; b) the costs of restarting the search in the spanning tree as part of the total cost of the algorithms; c) and statistically significant differences between the distributions of the algorithms' results.

Lucas Castro, Rosiane de Freitas

The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation and uses $O(m \log m)$ space, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) priority queues can cost $O(\log m)$ time per operation and use $O(m)$ space. So far, it remains open whether these bounds can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue that costs $O(\log m)$ time per operation and uses $O(m)$ space, achieving the same bounds as a standard priority queue.

Víctor A. Braberman, Flavia Bonomo-Braberman, Yiannis Charalambous et al.

The emergence of prompting as the dominant paradigm for leveraging Large Language Models (LLMs) has led to a proliferation of LLM-native software, where application behavior arises from complex, stochastic data transformations. However, the engineering of such systems remains largely exploratory and ad-hoc, hampered by the absence of conceptual frameworks, ex-ante methodologies, design guidelines, and specialized benchmarks. We argue that a foundational step towards a more disciplined engineering practice is a systematic understanding of the core functional units--generative transformations--and their compositional patterns within LLM-native applications. Focusing on the rich domain of software verification and falsification, we conduct a secondary study of over 100 research proposals to address this gap. We first present a fine-grained taxonomy of generative transformations, abstracting prompt-based interactions into conceptual signatures. This taxonomy serves as a scaffolding to identify recurrent transformation relationship patterns--analogous to software design patterns--that characterize solution approaches in the literature. Our analysis not only validates the utility of the taxonomy but also surfaces strategic gaps and cross-dimensional relationships, offering a structured foundation for future research in modular and compositional LLM application design, benchmarking, and the development of reliable LLM-native systems.