A Software Engineering Space

Iterable Hash Tables Redux: Separate Chaining

In my earlier post on implementing Iterators for hash table based data structures I covered how to write an iterator for tables utilizing open addressing collision strategies – quadratic probing to be precise. In this post I’ll be covering implementing Iterators for a hash table that uses separate chaining for handling collisions. Separate chaining is […]

Fast sub string searching in amortized O(d) with Suffix Trees

There are a lot of ways to test if a string is contained within another string. Unfortunately, when it comes to searching in strings the algorithms are either incredibly complex and sensitive to implementation details (looking at you KMP) or just downright slow. In a previous article I went over a technique for accomplishing this […]

Iterative AVL Trees – Deletion

In a previous article I introduced what AVL trees are, their structure and insertion. If you have not read that article, go back and read it first, as code in this article builds off of code from there. AVL Tree’s are the original self balancing binary search tree, and as with all binary search tree’s […]

Fast string searching using suffix arrays

String searching and to a broader extent pattern matching are some of the most fundamental operations you can do on a computer. Much research has been done into pattern matching algorithms using techniques ranging from brute force, to hashing, to making use of non finite automata. One trait that many efficient pattern matching algorithms share […]

Enforcing uniqueness of objects in std::set<> and std::unordered_set<>

Unique Collections  Knowing that a collection is comprised of unique only items if a very useful thing indeed. It’s so useful that this concept is the basis of one of the fundamental data structure: the Set. While this is not the only reason for using  a set data structure, it’s probably the most common. Many […]

[Blog] The importance of studying data structures and algorithms.

Often while browsing stackoverflow and reddit, I come across alot of people stating that in todays day and age the learning data structures and algorithms is not as important as it once was. With feature rich modern languages, powerful IDE’s, and more open source libraries than you can shake a stick at, many developers don’t see […]

Searching: Different Algorithms for Different Data Structures

Different Searches for Different Data Structures This is another article developed from a question posed on Quora. A user asked how different data structures effect the search operation, and if so how? This is a great question, and indeed a fundamental question as it highlights the importance of choosing the right data structure for the […]

Left Leaning Red/Black Trees, Part 1: Theory, Rotations, Creation and Insertion.

Binary Search Trees Binary Search Trees are pervasive in computer science, their usefulness can not be overemphasized. From parsing, to searching, to sorting they pop up everywhere, even underpinning other ADT. They offer quick look up times and keep their data stored in sorted order with very little over head. They Are not without their […]