Brushing Up On Algorithms

TLDR; In my spare time, I now experiment with various algorithms and data structures.

Although I’ve hacked together a few ranking algorithms here and there, I never did pursue traditional sorting/recursion algorithms and data structures. Well now after wrapping up a few projects, I’m suddenly craving something new…

A week ago, I started working on a repo called fun-with-algos to compile a list of popular algorithms, including Binary Search, QuickSort, Fibonacci and more, based off of descriptions and pseudocode from Wikipedia articles and other references. Some of the algorithms really started to click for me, while others not so much. Nonetheless, I started to see patterns.

Any good search algorithm- e.g. Binary Search- requires that the array be already sorted so that it can use less-than/greater-than comparisons to filter out irrelevant entries.

Sorting algorithms tend to have at least one anchor point- a value that each other value is compared to then swapped to the left or right of.

With recursion, the input usually starts at a specified value then decreases with each iteration until it reaches one or zero, at which point recursion terminates and a final value is returned.

Then I tried creating a custom Array Flatten algorithm without the help of map, reduce or any other high level prototype methods. Although I needed a funky hack to get rid of circular references, it passed the tests. To my surprise, the solutions on StackOverflow varied drastically and the official ECMAScript standard seemed rather complicated for my needs.

I will continue to add more algorithms to the repo as I discover them.

Save The Trees… Quad Trees

Afterwards, I moved onto a data structure. Linked lists are hardly any more useful than arrays, but tree structures are pretty interesting. A few years ago, I created a location-based photo sharing app called ThatSnap. Although the app ceases to exist anymore, the lessons continue to resonate in my work.

I remember needing to use a Quad Tree structure to quickly query objects on the map within a specified bounding box (the viewable area of the device). Sometimes there could be hundreds or thousands of markers on the map. You only need to render what’s visible. And on top of that, you’d want to cluster the markers in order to reduce visual chaos and further improve performance.

At the time, I had pulled some implementations for Swift (iOS) and Java (Android) from GitHub. With some minimal tweaking, I was able to get Quad Trees working on both versions of the app. But I didn’t need to understand how that structure worked.

Well for the last few days, I’ve dug deep into Quad Trees and I now see just how beautiful they are- both visually and theoretically. Check out the repo.

It’s actually fairly simple. You start with one huge quad. It has a max capacity of 4 items (or whatever we want). Before you insert a 5th item, the quad splits into 4 equally sized child quads. You then proceed to then fill those up,  ensuring that each point actually belongs in the quadrant it’s placed in. Rinse and repeat.

When you query within a specified bounding box, you first identify each overlapping quad within that range, then you find overlapping points within those overlapping quads. The process is repeated recursively for child quads, just how insertion is.

Although I’ve primarily used the data structure for geolocation/mapping, I am curious about applications regarding computer vision and collision detection.

As a side note, this is my first non-trivial use of C++. It wasn’t too big of a jump from Java-which I had used for the last 3 years for Android dev- but I was always intimidated by the C++ build system and compiler mumbo jumbo. After fiddling with CMake, that part became simple. Classes, abstract classes, static methods and data types were all mostly the same as Java.

It has been a blast so far. Let’s see how much deeper down the rabbit hole I go.

Go here for the fun-with-algos repo and here for the quad-tree-cpp repo,

Leave a Reply

Be the First to Comment!

wpDiscuz