2022/02/24 by Ruyi Ji, Tianran Zhu, Ji, Ruyi +5
Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Machine Learning and Algorithms #Programming Languages (cs.PL) #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.2202.12208
openalex publication_date 2022/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Dynamic programming is an important optimization technique, but designing efficient dynamic programming algorithms can be difficult for even professional programmers. Thinning, a technique developed for systematically deriving efficient dynamic programming algorithms, has received much attention in studies because of its effectiveness for a large class of problems. Despite the success of thinning in theory, its practical usage is still limited because (1) applying thinning requires mathematical and algorithmic background, and (2) applying thinning solely may not be enough to generate algorithms as efficient as proposed by human experts. In this paper, we propose two approaches, MetHyl and MetHyl+, to resolve both problems. First, MetHyl automates the application of thinning via program synthesis and thus eliminates the burden to the user for applying thinning. Second, MetHyl+ integrates three rules into MetHyl that optimize three important factors on the time complexity of dynamic programming algorithms that are ignored by thinning, and thus make it able to automatically generate expert-level dynamic programming algorithms on many tasks. We evaluate our approaches on 37 tasks related to 16 optimization problems collected from Introduction to Algorithm, a popular textbook for algorithm courses. The results show that MetHyl+ achieves exponential speed-ups on 97.3% of tasks with an average time cost of less than one minute. Moreover, MetHyl+ generates algorithms that are as efficient as the reference programs provided by human experts on 70.3% of tasks.