Skip to main content
  • Mark Daniel Ward

  • Professor
    Purdue University

    I analyze algorithms and data structures using analytic combinatorics and probabilistic methods. I am also greatly interested in information theory and combinatorial game theory. My goal is the probabilistic analysis of algorithms and data structures for string processing, using stochastic assumptions about the string that are sufficiently robust for practical applications. This analysis consists of first-order asymptotic descriptions of performance characteristics (i.e., the precise rate and leading coefficient, e.g., 6ln(n); not O(ln(n)) or Theta(ln(n))), and possibly lower-order terms and fluctuations. Currently, such precise analysis is almost always limited to a combinatorial or other memoryless model of the string. Combinatorial and all other memoryless models are special cases (with m=0) of Markov models of order m. I will develop, utilize, and disseminate methods of analysis of algorithms on strings when the string follows a Markov probability model of order m >= 1. In the long run, I will work toward analogous milestones for mixing models, Hidden Markov Models (HMMs), and dynamic models.