#algoritms

A Totally Misused Concept: the Average

In our Thinkibility nibble What Is An Interesting Book? we suggested that books with intellectual value should be categorized by the publisher into categories:

Mainstream

Improvement

Criticism

Provocation and Alternatives

We propose a strong candidate for category 4: Provocation and Alternatives: The End of Average: How We Succeed in a World That Values Sameness

Subversive

Dispels a myth

For the…

Day 20 - Minimum Spanning Tree (Prim’s)

A Minimum Spanning Tree represents the shorted path connecting all vertices in a graph (A data structure where each node is weighted against each other node).  In this case the graph is constructed so the euclidean distance between points represents the edge weight.  Prim’s algorithm chooses a root vertex, looks through all other vertices and finds the minimum weight edge.  This process repeats until all min weight edges are found.

Remember when I told you how that we where goint to learn about how we can design algorithms efficiently form the start. Then dont worry that we got you covered! 

First of all let’s state what a sub problem is. So we have this big problem that we want to solve, and we look for similar and smaller solutions to that initial problem. Most of the times the first set of sub problems are still hard to solve themselves, so we create sub problems from those sub problems. We continue on unitl we have such a simple sub problem that is solved. Then those bottom sub problem can join to solve the more intermidiate subproblems, until we reach the top problem we wanted to solve, and wemagaged to solve the initial problem. All problems that can be solved this way aare said to have optimal substructure. 

Does that style of programming remind you of anything? YES: Recursion! If we can identify the optimal substructure of an algorithm, we can then apply dynamic programming to solve an algorithms. Let us try a quick example:

5! = 5*4*3*2*1 or 5! = 5*4!  .... n! = n*(n-1)!

To calculate 5!, we need to know 4! first, and to calculate 4! we need to know 3! and so on. The bug problem is calculate 5!, the intermidiate solutions would be 4! or 3! etc, the base sub problem is 1!, which is defined as 1! = 1. Therefore we divide 5! into 5*4! and divide it to 5*4*3! and so on, until we reach 1. Then we go back up, and start multiplying the known values, until we reach 5! the top of the subproblem. This type of design is called bottom-up calculation.

This is great! We can implement this for any natural number! Let’s say just after that calculation we want to calculate another factorial number, like 9! Then we have to calculate 8!, 7!, ... , and so on first. The way our algorithm is defined, we have to do all that work again, including the previously calculated 5! Calculating 5! over and over again can be very time consuming! 

Now we introduce you memoization. Memoization is nothing else than storing different values of a sub problem on a table (ex. arrays), so instead of calculating the whole sub problem again, we check the table to see if we have previous records of a solution of a sub-problem. So now When we calculate 7! after 5!, we only have to calculate 6! and 7! This greatly improves the running time of an algorithm! 

In summary, dynamic programming can be described as finding the optimal substructure of a problem, building a bottom up recursion solution for each sub problem, and storing the solution of each sub-subproblem on a memoization table (memo-table for short). 

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. This tend to be instructions such as adding up two variables, comparison operations, assigning values to varables. For example:

[1] Void Saple_Function(int num) [2] { [3] var value  = num; [4] if(num > 0); [5]         print(‘message’); [6]         return value; [7] return -1 * value; [8] }

Instructions on lines 4-7 cost 1 each. So calling ‘Sample_Funciont’ would have a running time of 5.  So if where to call ‘Sample Function’ let’s say 1000 times, the running time T(n) would not be 5000, or T(n) = 5 for simplicity.  When an algorithms runs through the max number of operations is called the worst case running time of an algorithm.

Keep in mind that the ‘if-statement’ on line [4] is not always going to execute. Suppose that the algorithm ran a bunch of times, but  we always got num to be less than 0 ALWAYS. Then the Running time of the Sample_Function would be 3 (lines 3,4 and 7 are the only ones being executed). When the least number of instructions of instructions of an algorithm are executed is called the best case running time of said algorithm.

In practice, we would get a miex between the best andthe worst case. If we ran Sample_Function 1000 times with different values of num, we could get a running time of T(n) = 5000, or as low as T(n) = 3, but we know that it would most probably be between best and worst. It could even be slighly more costly on avarage. But all depends on the value given to num. 

Let’s look at another example, this time with bubble sort:

[1] for (c = 0; c < ( n - 1 ); c++) [2]   for (d = 0; d < n - c - 1; d++)     [3]      if (array[d] > array[d+1])       [4]        swap = array[d];       [5]        array[d] = array[d+1];       [6]        array[d+1] = swap;      //n is the size of the array

All the operations inside the if-statement (and the ‘if’itself) in lines 3-6 have a running time T(n) = 3. Those 3 operations are inside a for-loop that runs n times (size of the array). That for loop is nested inside another for-loop that also runs n times. So the running time T(n) of bubble sort is: T(n) = n (n(3)) = 3n^3 on it’s worst case, T(n) = n * n (1) on it’s best case, and let’s say avarage somewhere in the middle of the two for simplicity.