Growing with the Web

Top articles

Here is a collection of my favourite articles I've written. I hope you enjoy them and learn something!

AVL tree

Published , updated
Tags:

The AVL tree, named after its inventors Georgy Adelson-Velsky and Evgenii Landis, is a type of self-balancing binary search tree. The tree re-organises itself after every insert and delete so that the tree height is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.

Fibonacci heap

Published , updated
Tags:

A Fibonacci heap is a heap data structure similar to the binomial heap, only with a few modifications and a looser structure. The Fibonacci heap was designed in order to improve Dijkstra’s shortest path algorithm from O(m \log n) to O(m + n \log n) by optimising the operations used most by the algorithm. Its name derives from the fact that the Fibonacci sequence is used in the complexity analysis of its operations.

Binomial heap

Published , updated
Tags:

A binomial heap is a priority queue data structure similar to the binary heap only with a more strict structure, it supports quicker merging of two heaps in Θ(\log n) at the cost of a slower find minimum operation. A binomial heap is made up of a series of unique ‘binomial trees’ which are constructed from smaller binomial trees.

Binary heap

Published , updated
Tags:

A binary heap is a binary tree data structure that typically uses an array or list as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to its fast extraction of either the minimum or the maximum element in a collection.

Design patterns in software engineering are generic solutions to some commonly occurring problems encountered when creating software. They are incredibly useful tools for both communicating a solution to a problem to other developers and also for saving time solving problems that have already been solved in quite elegant ways. Learning the big design patterns is a also just a great way to improve your skills as a software developer.

Triangles in CSS

Published , updated
Tags:

Creating triangles with CSS is a pretty good way to reduce the number of images within an application. They’re a bit tricky to get your head around at first but once you understand them it’s really easy.

I’ve compiled some information about time complexity and underlying data structures of .NET simple collections and dictionaries. It was difficult to find some of this information on official sources like MSDN and non-official sources seemed to differ, so I used reflector and actually had a look at the .NET framework code to confirm these cases.

Quicksort

Published , updated
Tags:

Quicksort is an O(n^2) sorting algorithm that runs in O(n \log n) time on average. It has a number of favourable qualities; it’s an in-place sort, requiring O(\log n) auxiliary space in the worst case; and is also a divide and conquer algorithm making it easy to parallelise. Unfortunately however it’s not a stable sort.

Merge sort

Published , updated
Tags:

Merge sort is a sorting algorithm that runs in O(n \log n) time. It is a divide and conquer algorithm, so it can get the most out of today’s multi-cored systems. It works by continually splitting up the array until each item stands on its own. The items are then merged back with the items that they were split with in the correct order.

Game development introduced me to programming when I was around 10 years old, and I’ve loved it ever since. One of the first formal algorithms I learned before entering university was A* (pronounced “A star”), and I really had a great time learning about it. It’s one of the most widely used pathfinding algorithms and is one that you would likely be introduced to first when approaching the subject of pathfinding. A pathfinding algorithm takes a start point (also known as a node) and a goal and attempts to make the shortest path between the two given possible obstacles blocking the way.