Binomial heap

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.

Just like a regular binary heap, the binomial heap can be either a min heap or a max heap. It also follows the properties of the heap data structure; all nodes must be smaller than their children for a min heap, or larger for a max heap.

The animations in this article will only work in certain browsers, it has been tested in the latest Chrome and Firefox.

The visitor design pattern

The visitor design pattern provides a method of separating an algorithm on an object and the object's actual class implementation. This allows the programmer to easily follow the open/closed principle;

software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification

Object-Oriented Software Construction, Bertrand Meyer

That is, modifying an entity's behaviour without modifying the underlying source code. Following the open/closed principle provides many quality-related benefits as the original code never changes.

Benefits

• Follows the open/closed principle
• Allows a new operation to be defined without changing the implementation of the class
• A visitor object can have state

Drawbacks

• If a new visitable object is added then all visitors need to be modified

Selection sort

Selection sort is an \(O(n^2)\) sorting algorithm that works by searching through a list to find the minimum element and swapping it for the first in the list. After every swap, selection sort is performed on the list with the head removed (ie. the minimum element). Due to the way that elements are swapped anywhere in the list, this is not a stable sort.

Selection sort is similar in complexity to insertion sort but almost always performs worse. This is due to the fact that selection sort has an exact number of comparisons based on \(n\), which can be defined using the arithmetic progression:

$$(n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2$$

This makes its best case always contain the same amount of comparisons as its worst.

While selection sort is faster than most \(O(\log n)\) sorts for small lists, insertion sort is normally the preferable choice. It's main favourable property is that it will perform at most \(n - 1\) element swaps, so it may be useful if swapping is expensive.

Greatest common divisor (GCD) with working

The one thing I hated about maths in school and university was the fact that I had to show my working. Of course I knew that it helped the marker see that you understood the problem, but I just found it incredibly tedious. Particularly when I knew the answer right after reading the question.

I recall back in university I was asked many times to find the greatest common divisor (GCD) of two integers using Euclid's algorithm. This is basically the exact situation I described above, you can work out the greatest common divisor in your head fairly easily with a smallish number but to actually show your working can take a quite a bit of writing.

Find the greatest common divisor of 108 and 30

108 = 30 x 3 + 18
 30 = 18 x 1 + 12
 18 = 12 x 1 +  6
 12 =  6 x 2 +  0
       ^

gcd(108, 30) = 6

So after doing it a couple of times I went ahead and spent a few minutes writing a little program that solved the problem with working shown. I lost the original source but have reproduced it for a little fun. :)

Algorithm: The Fibonacci Sequence

Problem

Implement a function that returns the Fibonnaci number for a given integer input.

Analysis

The Fibonacci sequence is the recurrence defined as

$$f(n) = f(n - 1) + f(n - 2)$$ $$\text{where }f(0) = 0\text{ and }f(1) = 1$$

Or in simpler terms, it's the sequence of numbers starting with 0 and 1 that is constructed by adding the previous 2 numbers together. Here are numbers 0 through 15:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Algorithm: Implement a queue using 2 stacks

Problem

Implement a queue using two stacks.

Analysis

A queue can actually be implemented using a single stack, this method makes use of recursion however which makes uses another stack of sorts, the call stack. This method involves popping each item off the queue and then recursively calling itself until the last element is found, on the way back down the call stack we push the items back on to the stack.

queuepop()
  value ← stack.pop()
  if stack is empty
    return value
  else
    result ← queuepop()
    stack.push(value)
    return result

This isn't very efficient though considering that the pop function is \(O(n)\), we can do better.

So how can we make use of the second stack to better the running time of the algorithm? Think about what a stack and a queue actually is, if we have a stack and reverse it, it will be in the order in which a queue would serve it up.

Algorithm: Reverse a string

Problem

Reverse a string in the most efficient way possible. For example an input of "abc123" will result in the output "321cba".

Analysis

This is a very common interview question, it tests whether a candidate understands how string concatenation and immutability works. A simple algorithm that does the job loops through each character and constructs a string in reverse order.

function reverse (text)
  define result ← ""
  foreach character c in text
    result ← c + result
  return result

The above algorithm is not very efficient though. This is because strings are immutable which means they cannot be modified after they are created. The algorithm creates a new string every iteration which takes worst case \(O(n)\), making the algorithm \(O(n^2)\).

The string can be reversed in \(O(n)\) time with a couple of different methods: using StringBuilder to construct the string as above, or by converting the string to a character array and back.

Algorithm: Integer division without the division operator (/)

Problem

Implement a function that performs integer division on two integers without the use of the division / operator. For example for the input of 10 and 4 should result in the output of 2.

Analysis

If you have not thought about this problem before you may be a little taken aback. It's actually a fairly simple problem, think about what division actually does, it counts how much of a certain number (the divisor) makes up another number (the dividend). One way we could do this using just the minus - operator is to count how many times you can subject the divisor from the dividend before 0 is reached.

Algorithm: All permutations of a set

Problem

Implement a function that gets all possible permutations (or orderings) of the characters in a string. For example for the input string "abc", the output will be "abc", "acb", "bac", "bca", "cab" and "cba".

Analysis

This problem is very similar to all combinations of a set, though the actual computing of the values will be quite different. Let's start by defining the inputs and outputs.

ArrayList<String> getPermutations(String characters);

Now let's look at how this problem is naturally solved. When I write down a set of permutations by hand, I tend to start with the first letter (a), and then find all permutations without that letter in it. So for "abc" I would write:

a bc
a cb
b ac
b ca
c ab
c ba

Algorithm: All combinations of a set

Problem

Implement a function that gets all possible combinations (or subsets) of the characters in a string with length of at least one. For example for the input string "abc", the output will be "a", "b", "c", "ab", "ac", "bc" and "abc".

Analysis

Firstly we will define our method signature. It's fairly simple as it's described in the problem, the input is a String and the output is a list of Strings

ArrayList<String> getCombinations(String characters);

Splay tree

The splay tree is type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.

The worst case height of a splay tree is \(n\), this could be the case if all nodes were accessed in ascending order for example.

This makes the worst case complexity of the splay tree's operations \(O(n)\). Since all operations also splay the tree on the node, the tree ends up roughly balancing itself, this results in a \(O(\log n)\) amortized worst case time complexity for all operations.

The splay tree is a particularly good choice as a data structure when it's likely that the same nodes will be accessed multiple times in a short period. This is where the real power in the splay tree lies, in its ability to hoist nodes up to the root when they are accessed, giving speedy access for nearby successive accesses.

Binary heap

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

Heaps come in two flavours, the min-heap which allows quick \(O(\log n)\) extraction of the minimum element, and the max-heap which allows the same for the maximum value. Before it is possible to extract values, the heap must first be constructed. This is done by going through the first half of the elements (in the array) starting from the middle and calling 'heapify' on each element, running in \(O(n)\) time.

It is typical to implement priority queues using heaps due to their \(O(\log n)\) extract min/max time.

Manipulating the size of List<T>

.NET allows us to set the size of a List<T> in the constructor if we know the capacity ahead of time. This will save the List's inner (dynamic) array from being reassigned (and copied) when items are added. While usually this will make a minuscule change to your program, if the list is large enough it saves quite a few operations.

The capacity constructor runs in O(n) time. Whereas Add(T) runs in O(1) time or O(n) time when the capacity needs to be increased.

The facade design pattern

The facade design pattern is a very simple pattern that provides a simplified interface to other code that may not be structured the same way. If we look facade up in the dictionary, this is one of the definitions we get:

An outward appearance that is maintained to conceal a less pleasant or creditable reality.

Google dictionary

This is the primary purpose of the pattern; to conceal a piece of code that isn't very nice to use and replace it with something better. That's all it is really, a class that calls code elsewhere.

Benefits

• Can change a badly-designed or hard to use API into an easy to use API
• Can merge multiple APIs into a single API
• If all calls to a function are done through a facade then it is very easy to refactor

Drawbacks

• Could possibly add unnecessary complexity if overused or used incorrectly

Data structure: Red-black tree

The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it 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.

Insert and delete are also performed in \(O(\log n)\) time. The 'fixup' operations where the balancing occurs after insert and delete have quite complex implementations as you will see below. This is because we need the properties of the red-black tree to hold otherwise it may not be balanced.

Quicksort

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.

It works by first selecting a 'pivot' element, then re-ordering either side of the list so that everything before the pivot is less than the pivot and everything after is greater. Quicksort is then called recursively on either side of the pivot.

Despite quicksort having a worst-case performance of \(O(n^2)\), it is sometimes regarded at the same level performance-wise as \(O(n \log n)\) sorts like merge sort or heapsort. This is due to its average case being \(O(n \log n)\), it will often perform even better in practice than the \(O(n \log n)\) sorts.

The factory method design pattern

The factory method design pattern attempts to implement the concept of real-world factories within your program. Instead of the object creating itself, the task of creation is given to a 'factory' object.

Factory method effectively encapsulates the creation of objects within another class, one benefit of this is that it allows access to resources or objects that may not be available within the class constructor. For example a UI framework may have a createWidget factory method, this method not only returns the new object but also adds it to the list of widgets to be drawn and updated. This is one of the most common usage examples for factory method.

Benefits

• Provides a centralised location for pre- or post-constructor logic
• Allows access to resources that may not be available within the class being constructed
• Encapsulates the creation of objects

Drawbacks

• A factory can only be used for a single family of objects
• Can potentially overcomplicate a solution
• Factory methods are not as easily identified as constructors are

Enabling USB debugging on your Nexus 10 under Windows

I just received my new Nexus 10 and am loving it. As usual when it comes to setting up Android development, I had a few issues. It was really never the smoothest process in my experience, at least it's nice and smooth for the most part when it's all up and running. Not many relevant results came through so here's how I got it up and running under Windows 8.

1. Install the USB drivers using the Android SDK Manager
   
   
   
   
   
2. Open Device Manager and update the drivers for the device under "Other Devices" as described here.

Now go have some fun optimising your apps for XHPDI!

Heapsort

Heapsort is an \(O(n \log n)\) sorting algorithm that works by first constructing a heap out of the list and repeatedly pulling the root off the top of the heap and reconstructs it until there are no items left in the heap. The values that are pulled off of the top of the heap come out in sorted order. If the heap used was a min-heap, the resulting list will be in ascending order, and a max-heap will give them in descending order.

Unfortunately heapsort is not stable so sorting a list that is already sorted could quite possibly end up in a different order.

Algorithm: Binary search

Binary search is a decrease and conquer search algorithm than can be used on a sorted array. It operates by determining whether the search value is less than or greater than the middle value and recursively calling itself on the lower or upper half of the list respectively until either the value is found or not found.

The binary search algorithm is very similar to the binary search tree's search operation though not identical. Binary search's average and worst case time complexity is O(log n), while binary search tree does have an average case of O(log n), it has a worst case of O(n). Namely when the tree's height equals the number of items in the tree (incredibly unlikely in any real scenario).

The real power in binary search shows itself when we use it to search a huge list of items, much like any logarithmic algorithm. Exponential functions work by looking at the whole input data when considering each item. Logarithms (inverse-exponential functions) work by repeatedly halving the input data. Consider a list that contains 1 million items, if this list happens to be sorted we can use binary search to search for an item in no more than 20 steps.