Tuesday, September 29, 2015

Integer Data Structures + Hashing Notes

The last week I covered the fourth integer data structure lecture and the hashing lecture. The hashing lecture mostly pertained to hash tables, with a focus on collision management and hash suitability.

Monday, September 21, 2015

Integer Data Structures

This previous week in my advanced data structure independent study I covered integer data structures applied to the predecessor problem.

The predecessor problem asks for the predecessor or successor element for a given key, even if there is no value in the data structure with that key. This problem is actually fairly difficult if one considers that key/value mappings such as hash tables are no longer applicable. Likewise, many problems can be decomposed into special cases of the predecessor problem. 

"Integer" data structures actually don't involve properties of the mathematical definition of integers at all. They are a model of computation that is closer to the actual machine than a pointer machine. Where a pointer machine only has references, an integer data structure will typically exploit properties of pointers and the ability to encode information in machine-word-sized bit vectors. 

The Van Emde Boas structure and Fusion Trees are introduced in these three lectures, as is the trick of "indirection" for keeping algorithmic bounds low by routing to chunks of information. The proof of the running times of these structures is quite mind-expanding, as it treats the algorithm as a communication between the data structure and the reading party and uses information-theory to prove a lower bound on communication. 

Fusion trees are very interesting, using "sketching" and bit vectors to add parallelism to the tree search. This entire section has been a collection of algorithmic "tricks" that have a lot of power for optimization.

My notes for the lectures are in the blog post body after the break.

Sunday, September 13, 2015

Memory Hierarchies

This last week, I covered both of the Memory Hierarchy lectures. I chose to skip over dynamic optimality, as tree optimality should be covered later in this study with more of a focus on the papers of note which have been published.

My notes for both Memory Hierarchies lectures have been included below:

Monday, September 7, 2015

Relaxed Radix Balanced Trees

RRB trees are an implementation of persistent ordered sequences with O(1) time for all operations. The paper is fairly straightforward. The existence of a reference C implementation is nice.



Higher-Dimension/Geometric and Kinetic Data Structures

While at ICFP this last week, I covered the second week of MIT's

My condensed notes have been typed up below.