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

[B]RWRWR  SWAP(B, R) and decrease blue

[R]RWRWB  Increase white++ and red++

R[R]WRWB  Increase white++ and red++

RR[W]RWB  Increase white++

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

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 01 Knapsack
This variation of the problem deals with a possibilty of taking an item or not. Hence the 01 in the title.
How to reason about the solution
In the centre for this problem lies of capacities by values. Xaxis will represent the numbers from 1 to K (capacity of knapsack). Yaxis will represent the different wights.
 It start with going Down  Right.
 First we fill the column for knapsack of size 1.
 We check can we fit an item in?
if w[i] > capacity
 If this is true, it indicates we can not add this item so simply take the previous value
result[i, capacity] = result[i1, capacity]
 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.  The sample solution broken down will look like that
result[i, capacity] = max(result[i1, capacity], result[i1, 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]