A Software Engineering Space

Pseudorandom Number Generation via LCG’s

Random numbers are incredibly useful, from running simulations to procedural terrain generation in video games and million other uses in between, they come up all. the. time. Ironically, it is almost impossible to generate truly random numbers. And actually IS impossible to do it via an algebraic formula. Thats why random number generators are actually […]

In-place Merge Sorting

If you’re familiar with the C++ Standard Library, and the C++ Standards at large, you know that certain performance requirements are laid out for the algorithms it contains. The built in sorting algorithms are no exception. It is well known that std::sort is the reference implementation of Introspective Sort, designed specifically for STL. std::stable_sort does […]

Computing the Convex hull of a given set of points

Convex hull algorithms fall into the category of “computational geometry”. Computational geometry has a wide range of applications in many different fields, ranging from computer graphics, to ecology, city planning, and much, much more. In this post I will cover one of the simplest ways to compute the convex hull of a polygon: the gift […]

Comparing Balanced Search Tree Algorithms

There is a long standing debate amongst developers on which Self Balancing Binary Search Tree is better: AVL Trees or Red Black Trees. It’s one of those age old debates the inspires religious like fervor in those which choose a side. The situation only became more complicated with the introduction of Left Leaning RedBlack trees, […]

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