What do you think?
Rate this book
A Guide to Experimental Algorithmics
Computational experiments on algorithms can supplement theoretical analysis by showing what algorithms, implementations, and speed-up methods work best for specific machines or problems. This book guides the reader through the nuts and bolts of the major experimental What should I measure? What inputs should I test? How do I analyze the data? To answer these questions the book draws on ideas from algorithm design and analysis, computer systems, and statistics and data analysis. The wide-ranging discussion includes a tutorial on system clocks and CPU timers, a survey of strategies for tuning algorithms and data structures, a cookbook of methods for generating random combinatorial inputs, and a demonstration of variance reduction techniques. Numerous case studies and examples show how to apply these concepts. All the necessary concepts in computer architecture and data analysis are covered so that the book can be used by anyone who has taken a course or two in data structures and algorithms. A companion website, AlgLab (www.cs.amherst.edu/alglab) contains downloadable files, programs, and tools for use in experimental projects.
272 pages, Paperback
First published January 30, 2012
22 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 of 1 review
August 19, 2022
I found this book interesting, and I believe I will find it useful. While the book is dedicated to techniques for determining the performance of algorithms in various situations and with various inputs, much of the logic should also apply to what you might call "black box" performance problems, such as the behavior of a query in a DBMS.
The book says right off that it assumes the reader has some undergraduate computer science experience, and I did find my (41 year-old!) computer science degree helpful, but if you have some familiarity with Big O, Omega, and Theta notation and are reasonably comfortable with basic statistics, you should be OK with this book. Most of it is about logic, algorithms and coding, and only the last part of chapter 3 (What to Measure) and the last two chapters (Creating Analysis-Friendly Data and Data Analysis) are particularly math-heavy.
This is a very practical book, clearly by someone who has spent time in the trenches with her hands deep in the guts of the code, and has practical advice. Perhaps there is a little too much emphasis on the use of random inputs, but there is encouragement for use of real world data as well (in my experience real world data is often more surprising, and thus dangerous, then random data).
The book is (as of the time of this review) 10 years past its publication date, and it shows it when dealing with concurrency. It admits to the difficulties involved in dealing with algorithm experiments involving multicore systems, but doesn't go into any detail. There is no mention of other forms of concurrent algorithms , such as algorithms that run on GPUs or algorithms for running in distributed processing environments (such as Map/Reduce). And none of the special issues of developing algorithms for the cloud are discussed (including the lovely cases where the costs of the algorithm you're concerned with are in cash!).
The book is fairly language agnostic (although there is no discussion of garbage collection); code snippets are sketched a C-like pseudo code form that anyone with any experience of any Algol-descended language should have no problem following.
The book says right off that it assumes the reader has some undergraduate computer science experience, and I did find my (41 year-old!) computer science degree helpful, but if you have some familiarity with Big O, Omega, and Theta notation and are reasonably comfortable with basic statistics, you should be OK with this book. Most of it is about logic, algorithms and coding, and only the last part of chapter 3 (What to Measure) and the last two chapters (Creating Analysis-Friendly Data and Data Analysis) are particularly math-heavy.
This is a very practical book, clearly by someone who has spent time in the trenches with her hands deep in the guts of the code, and has practical advice. Perhaps there is a little too much emphasis on the use of random inputs, but there is encouragement for use of real world data as well (in my experience real world data is often more surprising, and thus dangerous, then random data).
The book is (as of the time of this review) 10 years past its publication date, and it shows it when dealing with concurrency. It admits to the difficulties involved in dealing with algorithm experiments involving multicore systems, but doesn't go into any detail. There is no mention of other forms of concurrent algorithms , such as algorithms that run on GPUs or algorithms for running in distributed processing environments (such as Map/Reduce). And none of the special issues of developing algorithms for the cloud are discussed (including the lovely cases where the costs of the algorithm you're concerned with are in cash!).
The book is fairly language agnostic (although there is no discussion of garbage collection); code snippets are sketched a C-like pseudo code form that anyone with any experience of any Algol-descended language should have no problem following.
Displaying 1 of 1 review