A Software Engineering Space

An Iterable Hashtable

The iterator pattern as it is described in the GoF book[1] bears very little resemblance to what those of us familiar with the C++ standard library know as iterators. The example described in Design Patterns[1] being closer in spirit to how it is implemented in the JDK, the underlying concept is the same. Unfortunately, such […]

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 […]