/Succinct-structure

CMSC858D succinct structure assigment

Primary LanguageR

Succinct-structure

CMSC858D succinct structure assigment

There are three folders in this repository, each folder is for a specific computing task of this assignment.

  1. O(1) time rank operation for bit vector using a succinct data structure.
  2. O(logn) time select operation for bit vector using a succinct data structure
  3. A wavelet tree data structure for strings over an arbitrary alphabet. 
     This wavelet tree can offer O(logn) time rank and select operation.

All files are written in R with no dependency to any additional packages.