Pearls of Algorithm Engineering

This book covers algorithmic problems in big data applications, presenting solutions over hierarchical-memory systems along with pseudocode.

Paolo Ferragina (Author)

9781009123280, Cambridge University Press

Hardback, published 22 June 2023

326 pages
25.1 x 17.6 x 2.2 cm, 0.71 kg

'There are many textbooks on algorithms focusing on big-O notation and general design principles. This book offers a completely unique aspect of taking the design and analyses to the level of predictable practical efficiency. No sacrifices in generality are made, but rather a convenient formalism is developed around external memory efficiency and parallelism provided by modern computers. The benefits of randomization are elegantly used for obtaining simple algorithms, whose insightful analyses provide the reader with useful tools to be applied to other settings. This book will be invaluable in broadening the computer science curriculum with a course on algorithm engineering.' Veli Makinen, University of Helsinki

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 analyses 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.

1. Prologue
2. A warm-up!
3. Random sampling
4. List ranking
5. Sorting atomic items
6. Set intersection
7. Sorting strings
8. The dictionary problem
9. Searching strings by prefix
10. Searching strings by substring
11. Integer coding
12. Statistical coding
13. Dictionary-based compressors
14. The burrows-wheeler transform
15. Compressed data structures
16. Conclusion.

Subject Areas: Signal processing [UYS], Algorithms & data structures [UMB]