Average Case-Analysis of Algorithms

Research project P 14200 Average Case-Analysis of Algorithms Peter KIRSCHENHOFER 11.10.1999 Analysis of algorithms is a rapidly growing area of research at the borderlines between Mathematics and Computer Science. From the applications point of view it is a question of major impact to analyze the dominating cost parameters of specified algorithms like running time, storage recquirements etc. This general observation holds in particular for the study of numbertheoretic algorithms, too. We explicitly subsume here also the analysis of algorithms which heavily rely on digital properties of the involved objects. Within the area of algorithm analysis two different main viewpoints may be distinguished. In the worst case scenario we are interested in the behaviour of algorithms under circumstances that make them behave extraordinarily bad. Although this type of analysis leads to a wealth of sophisticated mathematical problems in constructing extreme situations, it does not give good over-all information on the behaviour of the considered algorithms in general since extreme situations tend to occur rarely. In contrary to this type of analysis the average case scenario tries to evaluate the over-all behaviour of the important parameters of an algorithm by studying, expectations, higher moments or even limiting distributions of the quantities in question under certain probabilistic input models. It turns out that from the mathematical point of view the average case-analysis needs a variety of toolkits from different mathematical areas like Combinatorial Theory, Real and Complex Analysis or Probability Theory. In a number of instances the algorithms may be considered as acting on certain combinatorial objects (e.g. 0,1-strings or binary trees). The known relations between the parameters in question (e.g. recurrence relations) may often be preferably described in terms of well-suited generating functions, where they translate into functional equations, differential equations or more general functional relations. In order to gain explicit or asymptotic information about the coefficients of these functions (which bare the information on the cost parameters in question) analytical methods like singularity analysis, integral transforms etc. can be applied. It turns out that methods from analytic number theory play an important role in the study of the behaviour of these functions, since special functions like the Riemann or the Hurwitz zeta-function are frequently involved within their Mellin transforms. Transformation results, like the functional equation of Dedekind`s etafunction and related formulae, are a key tool in the asymptotic analysis of higher moments of certain cost parameters of algorithms. It is the aim of this project to develop further the toolkit of average-Case analysis of algorithms within several directions, as there are: - the development of methods detecting immediately the asymptotic behaviour of certain types of alternating sums occuring frequently in the analysis of data structures based on digital properties of keys; - the exploration of combinatorial and analytical aspects of certain families of orthogonal polynomials that play an important role in recent problems on diophantine equations; - the average case-analysis of digital number theoretic functions from an automata theoretic point of view; - the transfer of recurrences and combinatorial decomposition results to more or less immediate information on the (asymptotic) behaviour of certain cost parameters of algorithms. - Additional research problems are assumed to arise from other projects in this research area, especially from the projects submitted by Drmota, Hellekaiek, Larcher, and Tichy and Kirschenhofer.

In this project algorithmic questions of number theoretic origin have been investigated using tools from combinatorial theory. Starting from May 1, 2002, this project has been integrated into the FSP "Number Theoretic Algorithms and Applications" under the title "Combinatorial Tools for the Analysis of Number Theoretic Algorithms". The main contents of this project has been the investigation of combinatorial foundations and methods for questions in connection with algorithmic problems in number theory. A first part of the project has focussed on diophantine equations, that is equations whose solutions are sought within the set of integers. Questions in context with equations of this type have been investigated since thousands of years. Several actual research problems in this area are of an algorithmic nature. In this project equations between polynomials have been studied which originate from combinatorial enumeration problems. It could be shown, that for several classes of such polynomials that originate from structurally related combinatorial problems, the set of solutions of the corresponding polynomials diophantine equations is finite. For certain values of the parameters a constructive version of these results could be established. The proofs rely on methods from enumerative combinatorics as well as results on special functions like systems of orthogonal polynomials. A second main part of the project has been the investigation of number systems and digital functions for algebraic number fields using combinatorial methods from automata theory. The main questions are existence and properties of number systems like the Gaussian integers or more general ones. Results within this area are of great importance e.g. for the construction of cryptographic systems, that is systems for the encryption of data. A geometric realisation of the numbers with "integer part" equal to zero results in a fractal for most of these number systems. In the present project so called counting automata from the theory of formal languages have been used in order to gain results on these fractals, that give important information on the referring number systems. A considerable amount of research within this project was performed in cooperation with projects of the FSP "Number Theoretic Algorithms and Applications" of the FWF.