Experimental Algorithmics

From Algorithm Design to Robust and Efficient Software

By: Rudolf Fleischer (Editor), Bernhard Moret (Editor), Erik Meineche Schmidt (Editor)

Write A Review

Paperback | 13 December 2002

Sorry, we are not able to source the book you are looking for right now.

We did a search for other books with a similar title, however there were no matches. You can try selecting from a similar category, click on the author's name, or use the search box above to find your book.

Experimental algorithmics, as its name indicates, combines algorithmic work and experimentation: algorithms are not just designed, but also implemented and tested on a variety of instances. Perhaps the most important lesson in this process is that designing an algorithm is but the first step in the process of developing robust and efficient software for applications.

Based on a seminar held at Dagstuhl Castle, Germany in September 2000, this state-of-the-art survey presents a coherent survey of the work done in the area so far. The 11 carefully reviewed chapters provide complete coverage of all current topics in experimental algorithmics.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Computer Programming & Software Development Algorithms & Data Structures Computer Science Software Engineering Graphical & Digital Media Applications 3D Graphics & Modelling Databases Data Capture & Analysis Mathematics Applied Mathematics

Algorithm Engineering for Parallel Computation	p. 1
Introduction	p. 1
General Issues	p. 3
Speedup	p. 5
Why Speed?	p. 5
What is Speed?	p. 5
Speedup Anomalies	p. 6
Reliable Measurements	p. 7
Test Instances	p. 9
Presenting Results	p. 10
Machine-Independent Measurements?	p. 11
High-Performance Algorithm Engineering for Shared-Memory Processors	p. 12
Algorithms for SMPs	p. 12
Leveraging PRAM Algorithms for SMPs	p. 13
Conclusions	p. 15
References	p. 15
Examples of Algorithm Engineering for Parallel Computation	p. 20
Visualization in Algorithm Engineering: Tools and Techniques	p. 24
Introduction	p. 24
Tools for Algorithm Visualization	p. 26
Interesting Events versus State Mapping	p. 30
Visualization in Algorithm Engineering	p. 33
Animation Systems and Heuristics: Max Flow	p. 33
Animation Systems and Debugging: Spring Embedding	p. 39
Animation Systems and Demos: Geometric Algorithms	p. 41
Animation Systems and Fast Prototyping	p. 43
Conclusions and Further Directions	p. 47
References	p. 48
Parameterized Complexity: The Main Ideas and Connections to Practical Computing	p. 51
Introduction	p. 51
Parameterized Complexity in a Nutshell	p. 52
Empirical Motivation: Two Forms of Fixed-Parameter Complexity	p. 52
The Halting Problem: A Central Reference Point	p. 56
Connections to Practical Computing and Heuristics	p. 58
A Critical Tool for Evaluating Approximation Algorithms	p. 64
The Extremal Connection: A General Method Relating FPT, Polynomial-Time Approximation, and Pre-Processing Based Heuristics	p. 69
References	p. 74
A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation	p. 78
Introduction	p. 78
Organization	p. 80
Cache Aware Search	p. 80
Cache Oblivious Search	p. 82
Program Instrumentation	p. 84
Experimental Results	p. 87
Conclusion	p. 90
References	p. 91
Using Finite Experiments to Study Asymptotic Performance	p. 93
Introduction	p. 93
Difficulties with Experimentation	p. 97
Promising Examples	p. 99
Theory with Simplifications: Writing to Parallel Disks	p. 99
"Heuristic" Deduction: Random Polling	p. 100
Shellsort	p. 102
Sharpening a Theory: Randomized Balanced Allocation	p. 103
Empirical Curve Bounding Rules	p. 105
Guess Ratio	p. 107
Guess Difference	p. 107
The Power Rule	p. 108
The BoxCox Rule	p. 109
The Difference Rule	p. 110
Two Negative Results	p. 111
Experimental Results	p. 112
Parameterized Functions	p. 112
Algorithmic Data Sets	p. 118
A Hybrid Iterative Refinement Method	p. 120
Remark	p. 121
Discussion	p. 123
References	p. 124
WWW.BDD-Portal.ORG: An Experimentation Platform for Binary Decision Diagram Algorithms	p. 127
Introduction	p. 127
WWW Portal Sites for Research Communities	p. 127
Binary Decision Diagrams	p. 128
A Benchmarking Platform for BDDs	p. 129
To Publish Code is not Optimal	p. 130
What is Really Needed	p. 131
A Web-Based Testbed	p. 131
The WWW Interface	p. 131
Implementation	p. 132
Available BDD Tools	p. 132
Added Value: A BDD Portal Site	p. 133
Structure of a Conventional Portal	p. 133
Shortcomings of Conventional Portals	p. 134
The BDD Portal	p. 134
Online Operation Experiences	p. 136
Related Work	p. 136
References	p. 137
Algorithms and Heuristics in VLSI Design	p. 139
Introduction	p. 139
Preliminaries	p. 140
OBDDs - Ordered Binary Decision Diagrams	p. 140
Operations on OBDDs	p. 141
Influence of the Variable Order on the OBDD Size	p. 143
Reachability Analysis	p. 144
Image Computation Using AndExist	p. 145
Heuristics for Optimizing OBDD-Size - Variable Reordering
Sample Reordering Method	p. 147
Speeding up Symbolic Model Checking with Sample Sifting	p. 149
Experiments	p. 151
Heuristics for Optimizing OBDD Applications - Partitioned Transition Relations	p. 152
Common Partitioning Strategy	p. 153
RTL Based Partitioning Heuristic	p. 154
Experiments	p. 156
Conclusion	p. 157
References	p. 160
Reconstructing Optimal Phylogenetic Trees: A Challengein Experimental Algorithmics	p. 163
Introduction	p. 163
Data for Phylogeny Reconstruction	p. 165
Phylogenetic Reconstruction Methods	p. 166
Algorithmic and Experimental Challenges	p. 167
Designing for Speed	p. 167
Designing for Accuracy	p. 167
Performance Evaluation	p. 168
An Algorithm Engineering Example: Solving the Breakpoint Phylogeny	p. 168
Breakpoint Analysis: Details	p. 169
Re-Engineering BPAnalysis for Speed	p. 170
A Partial Assessment	p. 172
An Experimental Algorithmics Example: Quartet-Based Methods for DNA Data	p. 172
Quartet-Based Methods	p. 172
Experimental Design	p. 174
Some Experimental Results	p. 175
Observations and Conclusions	p. 176
References	p. 178
Presenting Data from Experiments in Algorithmics	p. 181
Introduction	p. 181
The Process	p. 182
Tables	p. 183
Two-Dimensional Figures	p. 184
The x Axis	p. 184
The y Axis	p. 187
Arranging Multiple Curves	p. 188
Arranging Instances	p. 190
How to Connect Measurements	p. 191
Measurement Errors	p. 191
Grids and Ticks	p. 192
Three-Dimensional Figures	p. 194
The Caption	p. 194
A Check List	p. 194
References	p. 195
Distributed Algorithm Engineering	p. 197
Introduction	p. 197
The Need of a Simulation Environment	p. 200
An Overview of Existing Simulation Environments	p. 202
Asynchrony in Distributed Experiments	p. 204
Difficult Input Instances for Distributed Experiments	p. 206
The Adversarial-Based Approach	p. 206
The Game-Theoretic Approach	p. 209
Mobile Computing	p. 212
Models of Mobile Computing	p. 213
Basic Protocols in the Fixed Backbone Model	p. 214
Basic Protocols in the Ad-Hoc Model	p. 218
Modeling Attacks in Networks: A Useful Interplay between Theory and Practice	p. 222
Conclusion	p. 226
References	p. 226
Implementations and Experimental Studies of Dynamic Graph Algorithms	p. 229
Introduction	p. 229
Dynamic Algorithms for Undirected Graphs	p. 231
Dynamic Connectivity	p. 231
Dynamic Minimum Spanning Tree	p. 243
Dynamic Algorithms for Directed Graphs	p. 252
Dynamic Transitive Closure	p. 252
Dynamic Shortest Paths	p. 264
A Software Library for Dynamic Graph Algorithms	p. 271
Conclusions	p. 273
References	p. 274
Author Index	p. 279
Table of Contents provided by Publisher. All Rights Reserved.

Experimental Algorithmics

From Algorithm Design to Robust and Efficient Software

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Algorithms & Data Structures

Addiction by Design

Machine Gambling in Las Vegas

Bioengineering and IoT

Shaping the Future of Healthcare

Heuristic Algorithms Design

A Methodological Approach

The Man Who Solved the Market

How Jim Simons Launched the Quant Revolution SHORTLISTED FOR THE FT & MCKINSEY BUSINESS BOOK OF THE YEAR AWARD 2019

Artificial Intelligence Programming with Python

From Zero to Hero

Introduction to Machine Learning with Python

A Guide for Data Scientists

Learning Spark

Lightning-Fast Data Analytics

Python for Algorithmic Trading

From Idea to Cloud Deployment

Code Dependent

Living in the Shadow of AI - Shortlisted for the Women's Prize for Non-Fiction

Speak Data

Artists, Scientists, Thinkers, and Dreamers on How We Live Our Lives in Numbers

HBR's 10 Must Reads on Data Strategy

HBR's 10 Must Reads

Data Structures and Algorithms Essentials You Always Wanted to Know

Master Python, Recursion, Dynamic Programming, and Greedy Algorithms With Hands-On Examples

Data Structures and Algorithms Essentials You Always Wanted to Know

Master Python, Recursion, Dynamic Programming, and Greedy Algorithms With Hands-On Examples

New Storytelling

Learning through Metaphors

Applied Data Science in FinTech

Models, Tools, and Case Studies

Applied Data Science in FinTech

Models, Tools, and Case Studies

Computer Science Why

Answers to Computer Science Questions They Don't Cover in Class

Computer Science Why

Answers to Computer Science Questions They Don't Cover in Class

Ethics and Governance of Artificial Intelligence

Frameworks, Risks, and Society

Ethics and Governance of Artificial Intelligence

Frameworks, Risks, and Society

Soft Computing Techniques in Connected Healthcare Systems

Biomedical and Robotics Healthcare

Python 3 Using DeepSeek

Uncertain Data Analysis

Fuzzy Vector Algorithms

Uncertain Data Analysis

Fuzzy Vector Algorithms

This product is categorised by