Simple Algorithms

Safe average of two numbers

Obvious solution

$(a + b) / 2$

This is correct but the danger lies in the overflow issues. Let’s assume a and b are the maximum Integer values available (in Java it would be 2147483647). The sum would be over the maximal value. Yielding the incorrect result. One could also cast to the the bigger type (e.g from int to long) but this is not a solution. It only kicks the can down the read (how would averaging on max long look) and doesn’t solve it.

Safe option

$ a + (b - a) / 2$

This seemingly strange looking formula produces the correct average result in every case. Let me break it down:

$ \frac{a + b}{2} = \frac{a}{2} + \frac{b}{2} = a - \frac{a}{2} + \frac{b}{2} = a + \frac{b - a}{2}$

Dutch National Flag Problem

Problem definition

There is an array of balls. Each one of them is one of the three colours: red, white and blue. The question is: how one could rearrange balls so they ordered from red to white to blue. This problem was proposed by Edsger Dijkstra.

Solution

Firstly, let’s create pointers that should indicate where each colour starts. With those 3 pointers named: red, white and blue; red and white are initialized as 0, blue is initialized as array.length - 1. The whole algorithm is executed within a while loop with condition of white <= blue. To recap, currently we are only checking balls from left to right with white pointer being the worker pointer. The algorithm works as following. If the white pointer is at red ball - we are swapping red with white and increase both red and white pointers. If the white pointer is at white - increase the white pointer by 1 If the white pointer is at blue - we are swapping the blue with white but crucially we are still staying at this position and decreasing the blue pointer by 1. This prevents us from skipping a missing white ball if it was placed last - 0121110 - like here.

Example

Balls: BRWRWR

[] - indicates white pointer

1. [B]RWRWR || SWAP(B, R) and decrease blue--

2. [R]RWRWB || Increase white++ and red++

3. R[R]WRWB || Increase white++ and red++

4. RR[W]RWB || Increase white++

5. RRW[R]WB || SWAP(R, W (at position 2)) increase white ++ and red++

6. RRRWW[B] || DONE

Knapsack Problem

In general, you will have n items with v values and w weights. The goal of the task is to maximize the value that can be stored in some kanpsack with arbitrary capacity of K.

The solution for 0-1 Knapsack

This variation of the problem deals with a possibilty of taking an item or not. Hence the 0-1 in the title.

How to reason about the solution

In the centre for this problem lies of capacities by values. X-axis will represent the numbers from 1 to K (capacity of knapsack). Y-axis will represent the different wights.

1. It start with going Down - Right.
2. First we fill the column for knapsack of size 1.
3. We check can we fit an item in? if w[i] > capacity
4. If this is true, it indicates we can not add this item so simply take the previous value result[i, capacity] = result[i-1, capacity]
5. However what happens if we CAN fit an item? Either we take the previous value or we try to add the new value on top of it. This means there is a max() in there.
6. The sample solution broken down will look like that

result[i, capacity] = max(result[i-1, capacity], result[i-1, capacity - w[i]] + v[i])

Quick explainer of the second part. We check the previous

Tree Traversal

Order!

Inorder - [Left, Root, Right] Preorder - [Root, Left, Right] Postorder - [Left, Right, Root]