Time: 11:00am Thursday, 28th May.
Location: SIT 123
Speaker: Prof. Ian Munro, University of Waterloo
Title: Succinct Data Structures: Equivalence Classes and Unlabelled Permutations Point and interval contention
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.