Ferragina P. Pearls of Algorithm Engineering

Cambridge: Cambridge University Press, 2023. — 319 p.There are many textbooks on algorithms focusing on big-O notation and basic design principles. This book offers a unique approach to taking the design and analysis to the level of predictable practical efficiency, discussing core and classic algorithmic problems that arise in the development of big data applications, and presenting elegant solutions of increasing sophistication and efficiency. Solutions are analyzed within the classic RAM model and the more practically significant external-memory model that allows one to perform I/O-complexity evaluations. Chapters cover various data types, including integers, strings, trees, and graphs, algorithmic tools such as sampling, sorting, data compression, and searching in dictionaries and texts, and lastly, recent developments regarding compressed data structures. Algorithmic solutions are accompanied by detailed pseudocode and many running examples, thus enriching the toolboxes of students, researchers, and professionals interested in effective and efficient processing of Big Data.This book offers advice for programmers and software engineers: no matter how smart you are, in the field of algorithm engineering, the proverbial ffive-minutethinking will not be enough to get a reasonable solution for real-life problems. Real-life problems have reached such a large size, machines have become so complicated, users so demanding, applications so resource-hungry, and algorithmic tools so sophisticated that you cannot improvise being an algorithm engineer: you need to be trained to be one.The following chapters bear witness to this situation by introducing challenging problems together with elegant and efficient algorithmic techniques to solve them. In selecting their topics I was driven by a twofold goal: on the one hand, to provide readers with an algorithm engineering toolbox that will help them tackle programming problems involving massive datasets; and, on the other hand, to collect together the scientific material that I would have liked to have been taught when I was a master’s/Ph.D. student. Some of the following sections, typically (though not always) at the ends of chapters, have their titles completed by the superscripted symbol?; this indicates more advanced contents that the reader can skip without jeopardizing the reading of the book. As a final note for the reader passionate about programming, I point out another specialty of this book related to the fact that array indexes start from 1, instead of the classic 0 usually adopted in coding because in this way algorithms may be paraphrased more easily and formulas do not become complicated by the presence of ±1.