you're reading...

Basser Seminar: Succinct Data Structures

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers