Analysis of Algorithms (AofA): Part I: 1993 - 1998 ("Dagstuhl Period")

This is the rst installment of the Algorithmics Column dedicated to Analysis of Algorithms (AofA) that sometimes goes under the name Average-Case Analysis of Algorithms or Mathematical Analysis of Algorithms. The area of analysis of algorithms (at least, the way we understand it here) was born on July 27, 1963, when D. E. Knuth wrote his \Notes on Open Addressing". Since 1963 the eld has been undergoing substantial changes. We report here how it evolved since then. For a long time this area of research did not have a real \home". But in 1993 the rst seminar entirely devoted to analysis of algorithms took place in Dagstuhl, Germany. Since then seven seminars were organized, and in this column we briey summarize the rst three meetings held in Schloss Dagstuhl (thus \Dagstuhl Period") and discuss various scienti c activities that took place, describing some research problems, solutions, and open problems discussed during these meetings. In addition, we describe three special issues dedicated to these meetings