Bloom Filters
Bloom filters have been around for a while, 1970 to be exact. They're not exactly the star of any university data structures class. There are much "sexier" (yeah, i know.) data structures like self balancing search trees, hash t
Part 2: expanding the collision resolution repertoire
Welcome back for part two of my articles on hash tables. In my previous article i covered the basics of linear probing. In this article i will discuss another popular collision resolution t
In part one of my article on open address hash tables i discuss hash functions, initializing the table and buckets, as well as insertion and searching via linear probing.
Exploring binary heaps for efficiently implementing the Priority Queue ADT.
The Priority Queue ADT
Unlike a regular queue which operates on a first-in first-out fashion, or the Last-in First-out ordering of a stack, a priorit
Displaying Binary Search Trees
Despite the various methods for traversing a tree, displaying the actual structure visually is a more difficult task than one would think. We know that a pre-order traversal gives us some
-
Parsing Regular Expressions with MGCPGen
-
Determinization: Converting εNFA to DFA
-
Implementing Lexical Scoping: Resolving Variable Names with De Bruijn Indices
-
Improving Balance of Ternary Search Tries
-
Making Sense of LALR Parser Construction
-
Compiling Set Comprehensions to Bytecode: an exercise in managing abstractions
-
Fast Multi-Pattern String Searching with the Aho-Corasick Algorithm
-
Capture Groups: Tracking Regular Expression Sub Matches
-
Resolving Shift/Reduce Conflicts With Operator Precedence
-
Squeezing DFAs with Pair Compression