Basser Seminar Series

Succinct Data Structures: Equivalence Classes and Unlabelled Permutations

Speaker: Professor J. Ian Munro
Cheriton School of Computer Science, University of Waterloo

When: Thursday 28 May, 2015, 11am. Please note different day and time to usual.

Where: The University of Sydney, School of IT Building, SIT Lecture Theatre (Room 123), Level 1

Add seminar to my diary

Abstract

A succinct data structure is a representation of a combinatorial object, in close to the information theoretic lower bound, that permits the appropriate operations to be performed quickly. The “classic example” is the representation of a binary tree in about 2n bits permitting the operations of parent and child to be performed in constant time. A key tool is the ability to name the nodes, as values in [1,n].

After a brief introduction to the overall area, we focus on two closely related combinatorial objects: equivalence classes and unlabelled permutations. Cycles of a permutation can be viewed as equivalence classes, so the objects are clearly related. With equivalence classes, we want the operation “are A and B in the same class”, whereas with permutations we might like the operation pi(A). We give structures for both classes showing tradeoffs between extra space to represent the structures and time to perform the appropriate operations.

Speaker's biography

Ian Munro is University Professor and Canada Research Chair in Algorithm Design in the D.R. Cheriton School of Computer Science at the University of Waterloo, where he has been a faculty member since completing his PhD at the University of Toronto in 1971. His research has concentrated on the efficiency of algorithms and data structures. He has authored about 150 research papers and supervised more than a dozen Ph.D.'s on the subject. Dr. Munro has held visiting positions at a number of major universities and research labs, including AT&T Bell Labs, Princeton University and the Max Planck Insitute for Informatics. His consulting activities have included work with government and several major computer companies. He has served on the editorial boards of CACM, Inf & Comp, and B.I.T., and the program committees of most of the major conferences in his area. He is a former Director of Waterloo's Institute for Computer Research. He is presently a member of the board of the Centre for Education in Mathematics and Computing. He was elected Fellow of the Royal Society of Canada in 2003 and made University Professor in 2006.