Implementing Set Operations in Linear Time in Maple.

Michael Monagan, Simon Fraser University

June 15th, 2005 at 3:30pm in K9509.

Abstract: 
Coding algorithms which do a sequence of insertions (or delections)
into Maple sets or lists will generally lead to O(n^2) running time
and O(n^2) space instead of O(n log n) time and O(n) space.
This is because sets and lists are represented as arrays of pointers,
and insertion and deletion in a Maple set or list costs O(n) time and space.
In Maple, one can either hash tables or one can simulate linked lists
to achieve linear time.  I'll show how to do this on a basic
operation for the graph theory package.