Lifetime Achievement Award 2016

Ian Munro – University of Waterloo

Professor J. Ian Munro is an international leader in the field of algorithms and data structures. He is Canada’s authority on data structures and has made fundamental contributions to the field. Over the past 45 years, he has changed views on both the practice and the theory of data structures and algorithms. He helped to shape the field of algorithm design particularly with respect to space efficient data organization. He has been recognized for his research achievements as:

• Fellow of the Royal Society of Canada (2003).

• Fellow of the Association for Computing Machinery (2008).

• University Professor (2006) at the University of Waterloo.

• Canada Research Chair in Algorithm Design (Tier 1, 2001-present).

Dr. Munro’s current research focusses on space efficient data organization. The key idea is the creation of methods by which the structural information necessary for efficient processing in large scale applications can be represented, and effectively used, in a provably (near) minimal amount of space. In some applications, this structural information dominates “raw data” by a factor of up to 50 (and potentially more). Taking more space can dramatically increase processing time due to the level of memory on which this information must reside. The area is one of tough mathematical problems, requiring techniques for proving that a minimum of a particular amount of auxiliary information is necessary to perform a search task quickly. It is also an area of great potential for substantial advances in computational practice. A second area of work has been in the computational complexity of comparison based problems (e.g. sorting) where he and colleagues have solved the 35-year-old problem of partial sorting. Another long-standing data organization question, one that essentially dates from the 1970’s, was very recently solved by Munro and his colleagues. This problem is to quickly find the most efficient search structure possible for a set of values, given the probability of a request for each value and for a value falling between each pair.

Professor Munro has published over 85 journal papers and 135 conference papers. In addition to his research, Munro has become involved in attracting top students to Computer Science through programming contests at the national and international levels. He has led the Canadian team at the International Olympic in Informatics and served on the International Scientific Committee of the IOI for three years.