Experimental analysis of algorithms (thesis)

Catherine Cole McGeoch

This thesis examines the application of experimental, statistical, and data analysis tools to problems in algorithm analysis. Note that algorithms, not programs, are studied: “results” in algorithm analysis generally refer to abstract cost functions, are independent of particular machines or implementation strategies, and express functional relationships between input parameters and measures of algorithmic performance. The study of algorithms presents special problems and opportunities for experimental research.