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);

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.

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.

Insertion sort

Insertion sort works by looking at each item in an array (starting with the second) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next item.

As you probably guessed, insertion sort isn't one of the fastest sorts, running in \(O(n^2)\) worst case time. It does have a few benefits however:

• It is faster than most \(O(n \log n)\) sorting algorithms for small lists.
• It is very memory efficient requiring only \(O(1)\) auxiliary space for the single item that is being moved.
• It is a stable sort; equal elements appear in the same order in the sorted list.
• It is an adaptive sort; it's fast when sorting mostly sorted lists or when adding items to an already sorted list.
• It is really easy to implement.

Merge sort

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.

Merge sort is also a stable sort, this means that if there are elements considered equal, they will be in the same order in the final list. This is illustrated in the below image, teal and blue (9) are in the same order in both the source and sorted lists.

Big-O Notation

Introduction

Big-O notation (pronounced 'Big Oh') is used in computer science as a means to describe the worst-case performance of an algorithm. It's one of the things you really should learn if you're interested at all in designing efficient algorithms.

The formal definition is as follows:

f(n) = O(g(n)) means c*g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c*g(n), for large enough n (i.e. , n ≥ n₀ for some constant n₀).

The Algorithm Design Manual, Steven S. Skiena

This definition is a very format way of saying that Big O-notation is the upper-bound/worst-case of a function.

The A* pathfinding algorithm

Game development introduced me to programming when I was around 10, 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 doing so. It is one of the most widely used pathfinding algorithms and it's likely the one you'd be introduced to first when approaching the subject of pathfinding. A pathfinding algorithm takes a start point (also referred to as a node) and a goal and attempts to make the shortest path between the two given possible obstacles blocking the way.