Access Restriction

Author Mcgeoch, Catherine
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1992
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Experimental analysis of algorithms ♦ Move-to-front rule ♦ Self-organizing sequential search ♦ Statistical analysis of algorithms ♦ Transpose rule ♦ Variance reduction techniques
Abstract Although experimental studies have been widely applied to the investigation of algorithm performance, very little attention has been given to experimental method in this area. This is unfortunate, since much can be done to improve the quality of the data obtained; often, much improvement may be needed for the data to be useful. This paper gives a tutorial discussion of two aspects of good experimental technique: the use of variance reduction techniques and simulation speedups in algorithm studies.In an illustrative study, application of variance reduction techniques produces a decrease in variance by a factor 1000 in one case, giving a dramatic improvement in the precision of experimental results. Furthermore, the complexity of the simulation program is improved from $&THgr;\textit{mn}/H\textit{n})$ to $&THgr;(\textit{m}$ + $\textit{n}$ log $\textit{n})$ (where $\textit{m}$ is typically much larger than $\textit{n}),$ giving a much faster simulation program and therefore more data per unit of computation time. The general application of variance reduction techniques is also discussed for a variety of algorithm problem domains.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1992-06-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 24
Issue Number 2
Page Count 18
Starting Page 195
Ending Page 212

Open content in new tab

   Open content in new tab
Source: ACM Digital Library