Mark Daniel Ward - Analysis of algorithms on strings and trees

September,  2010

Writer(s): Jeremy Troisi, Ph.D. candidate in Statistics
mdw-t.jpg

The algorithms used to analyze large data sets are becoming increasingly complex and therefore often require large amounts of computational time. Professor Mark Daniel Ward understands that asymptotic analysis of algorithms is of crucial importance for investigation of large data sets. He studies the precise time and memory required by algorithms and data structures on strings and trees. This area of study lends itself well to Professor Ward's experience in theoretical computer science. His research yields precise mathematical descriptions of the asymptotic properties, rather than bounds on the performance. Due to the randomness involved in the data sets and the operations of some algorithms, his background in probability theory complements these applications.

"Data sets investigated today are really large. Even though computers have large memory capacities, merely having upper bounds on asymptotics will result in an over allocation of valuable memory. Furthermore, scientists working with large data sets—from biologists to economists—are also interested in more precise asymptotics," explains Ward. He also has research interests in applied probability theory, including leader election algorithms; pattern matching algorithms and data structures; data compression; information theory; game theory; and large-scale, parallel computation.

Dr. Ward is also especially fond of interdisciplinary problem solving, in which problems from one subject are solved using apparently unrelated methods. For instance, in spring 2010, he solved one of Herbert Wilf's eight "Unsolved Problems." The problem was to determine the precise asymptotic properties of a method for approximating Pi. His solution utilized methods from a different area of mathematics—complex analysis—in particular, singularity analysis, a Hankel contour, and transfer theorems.

In addition to his research in analysis of algorithms, Dr. Ward has a very active role as the Chair of the Undergraduate Committee in Statistics. One of his goals is to have an especially welcoming culture for students in the mathematical sciences. For example, together with his family he hosts a dinner every semester for each of his classes. His office door at MATH 540 (covered with paintings and pictures from his children) is always open to students. He is also the Associate Director of the Actuarial Science program, which has doubled in size (to approximately 290 students) in the last five years. Further, he is committed to growing the 5th Year Masters Program where students pursuing an undergraduate major in Mathematical Statistics can earn a Masters degree in Statistics with only one additional year of study.

A small cohort of faculty at Purdue are invited to teach for the University Honors Program (UHP), which features courses limited to 20-30 students. In fall 2009, Dr. Ward's "Lies, Damned Lies, and Statistics" program was the first course in the mathematical sciences offered by the UHP. In fall 2010, Dr. Ward is introducing a second new course for the program, called "Probability: The Science of Uncertainty."

Dr. Ward received his Ph.D. in Mathematics with Specialization in Computational Science from Purdue University in 2005. He was a Lecturer for two years in the Department of Mathematics, University of Pennsylvania. In 2007 Mark joined the Department of Statistics, Purdue University as an Assistant Professor. Currently, he is a senior personnel member of the newly founded National Science Foundation Science and Technology Center on Emerging Frontiers of Science of Information, for which Purdue University is the lead institution. For more information about Professor Ward, please visit his homepage.