The goal of this continuing research project is to develop more systematic theorems and methods for analyzing difficult algorithms. These methods are briefly characterized as follows: (1) Perturbation theory for recurrence equations in computer science. Perturbation theory is a mathematical technique which was developed for analyzing difficult differential equation problems in mathematical physics. The research objective is to develop a tool kit of theorems that can apply to recurrences ranging from advanced issues in hashing to the elementary concerns of basic irregular divide-and-conquer algorithms; (2) Replacing operator methods in performance analysis. Operator methods also arise in the analysis of physical methods, and have been used to establish conservation laws, and compute the time evolution of fundamental quantities such as energy in complicated physical processes. A variation on these methods has been used to analyze several complicated processes in computer science, including coalesced hashing. However, recently it has been shown that coalesced hashing can be analyzed more completely and more easily by standard analytic methods. The goal in this part is to capture algebraic properties of operator methods, to translate them into analytic formulations, and to use these translated formulations to analyze difficult algorithms; (3) Probabilistic estimates. A growing number of computer science results use large deviation bounds, including fault tolerance analysis, the analysis of throughput in probabilistic situations, and the analysis of probabilistic algorithms. Many computer science applications introduce varieties of extra constraints, which render the standard theorems inapplicable. The final goal is to continue research on probabilistic estimation methods.
