A guide to experimental algorithmics by Catherine C. McGeoch

By Catherine C. McGeoch

"Computational experiments on algorithms can complement theoretical research by way of displaying what algorithms, implementations, and speed-up equipment paintings top for particular machines or difficulties. This publication courses the reader in the course of the nuts and bolts of the key experimental questions: What may still I degree? What inputs may still I try? How do I examine the knowledge? Answering those questions wishes principles from set of rules design Read more...

Show description

Read or Download A guide to experimental algorithmics PDF

Best programming languages books

A guide to experimental algorithmics

"Computational experiments on algorithms can complement theoretical research through exhibiting what algorithms, implementations, and speed-up equipment paintings most sensible for particular machines or difficulties. This e-book courses the reader during the nuts and bolts of the main experimental questions: What may still I degree?

Extra resources for A guide to experimental algorithmics

Sample text

Designs for these types of functions should choose levels at the discontinuity points. The lines show results of measuring costs at n = 2k and n = 2k + 1. increase the range between the minimum and maximum n values in the design. That is, halving n twice may be enough to distinguish between (n) and (n2 ), but greater range may be needed to separate (n) from (n log n). • If very little is known about f (n), try using many levels of n within a large range. This allows a better view of how f (n) may converge to its asymptotic behavior.

Panel (a) shows the original coloring. Panel (b) shows the vertices reordered by the reverse rule, which reverses the color groups. Panel (c) shows a recoloring with vertices, considered by color group (blue, green, yellow, red) and colors considered in a new order: green, blue, red, yellow. This implementation of SIG employs four vertex rules and six color rules, which are selected randomly at each iteration according to probabilities specified by vectors VWEIGHTS and CWEIGHTS. In addition to the color count, the algorithm keeps track of a “color score” that incorporates more details about the coloring.

Another early experimental goal is to get a rough idea of the functional relationship between key parameters (especially input size) and algorithm performance. A good design strategy in this situation is to try a doubling experiment. Sedgewick [22] points that the growth rates of many common functions in algorithm analysis are easy to deduce if cost is measured as n doubles. For example, suppose we measure cost C(n) at problem sizes n = 100, 200, 400, 800 . .. The results can be interpreted as follows: 1.

Download PDF sample

Rated 4.68 of 5 – based on 49 votes