Lecture notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/7 • [previous page] • [next page] • [PDF]
| [+] Succinct: rank, select, tries | Scribe Notes [src] | |||||
| This lecture is the first of two about succinct data structures—data structures using very close to the minimum amount of space (“just the data”). In particular, we'll see how to store an n-node binary trie in 2n + o(n) bits (which is optimal up to the little-oh term) and still be able to navigate to a node's left child / right child / parent in constant time per operation, as well as be able to compute the size of the subtree rooted at a node in constant time. Along the way, we'll see how to store an n-bit string in n + o(n) bits (which is again optimal up to little-oh) and be able to compute the number of 1 bits left of a given bit, and find the ith 1 bit, in constant time per operation. These data structures form the basis of many succinct data structures. | ||||||
|
Lecture notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/7 • [previous page] • [next page] • [PDF] |
|
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.