Advanced Data Structures

Fall 2003

Assignment: Implement in pseudocode the ADT T (Dynamic Sparse Table) that will guarantee constant time set, access and initialization operations.
Operations:
Set: T, D,R -> T
(* for an f in T and an x in D, assigns value of y in R to f(x) *)
Access: T, D -> R
(* returns the value of f(x) *)
Init: -> T (* returns the constant function with all values d *)
Axioms:
Access (Set(f,x,y), z) := if x=z then y else Access(f,z)
(* retrieve default unless previously set *)
Access (Init,x) := d (* obviously *)
Set(Set(f,x,y),u,v) := if x=u then Set(f,x,v) else Set(Set(f,u,v),x,y)
(* only the most recent assignment for a given domain element is relevant *)
Background: Many functions over a finite discrete domain D have only few points that differ from a default value d. We implement such functions as sparse tables, indexed by the domain values; in general the question is posed as "how to save space to represent sparse tables." The obvious solution is to store compactly the non-default values (together with their indices), which most often involves some searching for the proper index. Our problem is wanting to save time (rather than space); this seems to require non-constant time to assign the default values to most of the entries.