A Software Engineering Space

Bottom-up 2-3 Red/Black Trees: Let your red nodes lean how they want

Well, It appears January is the month of the Red/Black tree, because here I am with yet more Red/Black tree content! Since their introduction in 1978[1] the study of red/black trees generally focused on their isomorphism with 2-3-4 trees. And, while it was recognized that 2-3 tree’s could be made to fit the red/black framework […]

Roll your own String type

Anyone who has ever had the pleasure of working with ‘C style’ strings aka NULL terminated character arrays. Has at some point stopped and remarked about the terrible choice of implementation when it came to representing strings in C. Indeed, almost every serious security vulnerability for a long time could be traced back to a […]

Compiling Regular Expressions with Non-deterministic Finite Automata

Regular expressions: those seemingly non-sensical strings of characters that seem to magically take an input string and determine whether it matches a pattern that you have some how supposedly described with the previously mentioned non-sensical string of characters. Being a self admitted perl lover, I have always been mystified by the power of regular expressions: […]

Why Does Mergesort Get a Bum Rap?

Despite being one of the oldest sorting algorithms and possibly the first to ever be implemented on a computer, mergesort is still one of the fastest general purpose sorting algorithms available. Almost every programming languages standard library has some merge sort based algorithm present in it’s standard library. And yet many programmers hold the belief […]

A Bottom Up Natural Mergesort Variant For Linked Lists

Mergesort was the first O(nlogn) sorting algorithm used. Donald Knuth has speculated that it may have even been the first sorting algorithm ever programmed into a computer, with John Von Neuman being aware of it as early as 1945.[1] For all of its history, and despite the desirable properties of O(nlogn) worst case complexity and […]

Zero sum games & state space search: Tic-Tac-Toe

In my previous post I covered using search to solve puzzles by abstracting the state space into a tree structure and using various graph searching algorithms to find a solution. In this post I will be following up this concept by applying its use to adversarial zero-sum games – that is, a turn-based game where […]

Solving Tile Sliding Puzzles With Graph Searching Algorithms

Puzzles are good way to kill some time when you’re bored. I was at a doctors office the other morning, and in the waiting room they had sliding tile puzzle that I played around with for a little bit while waiting to be called in. Personally, I find writing algorithms to solve the puzzles for […]

m-Ary heaps for sorting and priority queues

For most people “heaps” are synonymous with an array based heap ordered binary tree, commonly used as a priority queue. But the forest of heap ordered trees is rich in diversity, with variants including Leftist heaps, Fibonacci heaps, binomial heaps, and randomized meldable heaps just to name a few. Some of these data structures are […]

Algorithm Visualization Techniques & Data Observation

Often times when designing or learning a new algorithm it is beneficial to have a visual representation of what is “going on inside” an algorithm. As with self balancing binary search tree’s it is often helpful to know how the data is currently being organized compared to how it should be organized when trouble shooting a […]

Langton’s Ant: Exploring State Machines through Cellular Automata

I’ve been covering some heavy topics lately with my Stack Machine & Compiler series, so I figured I would break things up with a light interlude on a topic that is both fascinating, easy to follow, and most of all fun: Cellular Automata. Cellular automatons, such as John Conways “The Game of Life”, and in […]