A road named NoNameUno

It is one of Phil Collin's best song that I ever heard. If you have not, fire up the Youtube and listen...

But here it is about solving puzzles like problem, prove the solution for correctness, then write a program. These problems are not the ordinary problems we ordinarily deal with like: sorting, searching, max, min, queues, stacks, lists, arrays etc., etc. 

If you solve couple of them on your own, you appreciate the meaning of the song. Yes here she is nothing but Algorithm. So let's get to one such problem.

One thousand coins of different denominations are placed on a large table. They are placed side by side forming a line. You are asked to pick a coin from one of the two ends of the line, then your opponent will pick one from the end of the resultant line. At the end of the process you have to make sure that you win or at least make it a draw and your opponent never wins. Win means you managed to grab more money than your opponent. The only rules for picking your coin from one of the two ends of line, and in case of the last coin, one has to pick that if it is his/her turn.

If you never seen this problem, don't even read the rest, take the problem and try to come up with steps that will guarantee a win or at least a draw. If you seen this type of problem, rest of this article is a waste of time for you!!! By the way, it took me a while to solve this problem.

Give yourself a long pause, and don't try to look further, if clueless then look at the hint only, then stop and go back to your note book to solve it!

Don't read any further .....

Hint: Label the coins' position. You may win if you pick the coins from the odd positioned and you may win by picking the even positioned coins. Further more it could be One million coins or even more than that.

I will send the solution upon request, but if you can solve it by yourself that is the best and treat yourself.

Easy Lover, she'll get a hold on you ...

This theory says, Do the same thing again and again and expect a different results. This is my own experience when it comes to recursion. Many moons ago, I used to derive and check if a graph is recursive or not, and my thesis was to categorize different types of recursion when it comes to graph theory. Now quite often I bumped into implementation of recursive algorithm, and find myself totally confused...

 So I thought that I would discuss a bit about this recursion, and if possible induction. The approach would be to give a famous example Fibonacci sequence, tear it apart. Then the general approach to tackle recursion when it comes to implementing recursive algorithms. 

The general form of the Fibonacci sequence (Fib) is usually defined as -  Fib(n) = Fib(n- 2) + Fib(n-1) when n >= 2. And Fib(0) =0, Fib(1) = 1. The general class of these sequences are called additive sequence, and has rich structure when dealing with advanced level of Finite Mathematics.

As you can see the nature of recursion is too prime the algorithm with Fib(0) and Fib(1) then generate the sequence.  Note that there is a concept of Generating function, but that is not the immediate topic here.

For the iterative, straight forward implementation -

unsigned int Fib_n_2 = 0;

unsigned int Fob_n_1 = 1;

for ( i = 2; i <= n; i++) {

     Fib_n = Fib_n_1 + Fib_n_2;

     Fib_n_2 = Fib_n_1;

     Fib_n_1  = Fib_n;

}

The complexity is O(n).  

Straight forward recursion would be -

unsigned int rec_fib ( unsigned int  n)

{

        if ( n == 0 ) return 0;

        if ( n == 1 ) return 1;

        return (  rec_fib ( n - 1)  + rec_fib(n-2) );

}

This is again O(n). But it has more computation than the first one. You will see it if you draw the recursion tree based on the invokation. Since we are invoking two recursion, it would be a binary tree. But there is lot of redundant computation. For a better view, just draw the invocation graph for n equals, say 4 and see yourself.

Now this Fibonacci sequence is an instance of a class of sequence, usually called additive sequence. It is sometime used for linear extraplolation with history and sometime it is in the larger domain of Finite differences. An aside, Finte Difference is the analog of derivatives in continuous math. Finite difference leads to difference equation that is the discrete analog of differential equation. For our discussion, we can ignore this for now.

So for additive sequences, the first n terms could have initial value and the next term is derived by addition of the previous n terms. So two things are important (1) it is not necessary that first and second term have to be 0 and 1 (2) it does not have to be that the there is only two terms to start with. But for us, lets assume that there are only two terms to being with, just like Fibonacci sequence.

 Now the observation, for Fib(n), if we start from Fib_1 instead of FIb_0, we need to know the value of Fib_1 and and Fib_2, and we have to go only n-1 steps instead of n steps... So we have a function like the following

AddSequence ( int n, int term_0, term_1) and we could do a recrusive computation of Fib(n).

 int AddSequence( int n, int term_0, int term_1)

{

      if ( n == 0 ) return term_0;

      if ( n == 1)  return  term_1;

      return ( AddSequence ( n-1, term_1, term_0 + term_1) );

}

int Fib ( int n )

{

     return AddSequnce(n, 0, 1);

}

Now the recursion tree is really a chain, and there is no redundant computation. So it is at per with the iterative procedure given earlier. Still O(n). Now there are two observations. One is about the matrix representation of the recurrence relation. Which is as follows -

 --

|  Fib(k+2)  |                  |  1    1  |             |  F(k+1) |

|                 |          =      |            |       X    |             |

|  Fib(k+1)  |                  |   1   0  |             |   F(k)     |

where  the left side of the equation is a vector of dimenstion 2 by 1, and it is obtained by multiplying the 2 by 2 matrix on the left of the vector F(k+1), F(k).  Substituting k=0, you can see how the recurrence starts. 

Now if we start the same multiplication, we make forward progess in the sense of finding the next fibonacci number. Hence, finding Fib(n) is nothing but exponentiating the matrix to the nth power, and interpret the result appropriately.

We know that multiplication of a 2 by 2 matrix is constant time with respect to n. 

The second observation is that there is  log(n) bits to represent n in binary. So any n can be represented as a polynomial of base 2 with at most log(n) terms in that polynomial. So that will give you at most log(n) multiplications to raise the matrix to the nth power. Hence we have a O(log(n)) algorithm to produce Fib(n).

Conclusion is that if I try to solve some recursion without touching the topic for six months or longer, I always make stupid mistakes - so that is the theory of insanity. 

Thanks much Rod, that's an awesome song!

What is time? And why it is so important specially in computing?

It is important, just because lot of computing resources are being shared between contending customers. Here the customers are mainly applications, and in this sense operating systems are also customers. And the only canonical measure of sharing or in general for everything else in life is Time. Yeah, we all know the New yourker joke "What Time is it? - That's none of your business."

So for sharing resources by time, there has to be a controller and in our case it is the OS that needs of have the control of the processing and decide who gets what resources, but mostly the CPU time is what it is concerned of. And in order to get the control, the hardware has to assert interrupt every once in a while. That is the key design issue. If the hardware does that more frequently, it would be interrupt storm, and if it does less frequently the sharing is not very granular, hence average waiting time to get hold of CPU would increase.

 How often the hardware interrupt for time slice is a reasonable question. In lot of cases it is every 10 millisecond. So for the timer processing the OS would get control thru timer ISR every 10 or so milliseconds.

Now the questions like the following must come to your mind, if you want to get just a tad bit deeper -

1) What if I want to have a synchronous delay that is less than 10 ms?

2) What if the timer processing takes a significant part of the the 10 ms epoch?

3) etc., etc.

For question number (1), you can always refer to the linux implementation of BogoMIPS ( i.e Bogus Mips ) and how it derives micorsecond or nano second delay. For (2), the ISR processing should be alpha * epoch, where epoch equals 10ms in our case and  alpha is defined to be 0 < alpha < 1. If alpha is 1/2 then half the time goes just to process the interrupt service. This gives us a clue that if the processor speed grows exponentially, we might even see 5ms timer interrupts or even less...

Well that's 'bout it - now let me go to YouTube to listen one more time - Young heart be free tonight, TIME is on your side.

Variety is a good thing in life!. Well, to me it is not always.

Back in the days, when it was almost a requirement to code some parts of your software in assembler and some other parts in C, it was always the question what library you include when you use the link editor to link several such object files into a program. For example, if I don't use any math routines, I don't need to include the math lib but the standard c runtime is automatically included.

Now when you come down to craft a little program in assembly language, it again pops up in strange ways !!!

An example at hand is to use the AT&T as assembler in Mac OS X and Linux. Under linux one will cook up a function like the following -

#exit.s file

.section data

#data section

.section .text

.globl  _start

movl $1, %eax     #sys call number for exit

movl $0, %ebx     # ret code stored in ebx

int $0x80             # system call interrupt

----

So nothing fancy, this routine by itself a program. Using the following commands 

as exit.s  -o exit.o

ld  exit.o  -o exit

 I should have the program ready. But if you take this and try to use it on Mac OS X, it would surely complain when you assemble using 'as'  command. Once you get over that problem, the linker would complain too.

If you dealt with these problems, you will see symbols like main, _main, __main, start, _start, __start and what have you.

First the assemble would complain that it needs a comma after the section definitions, so you add the commas in two section assembler directives. Now compiler is happy to produce the object file.

Now if you try the link-edit phase, again you will run into quite a few problem. First it would say oops, I can not seem to find the crt1.o object file. Uh, I thought I don't need to mention anything about c runtime, right? Where the heck c runtime comes from? Then after couple round of circus if I say the following -

ld exit.o -lc -o exit

I get the link-editor to get out of that crt1.o not found. Now I will have to tackle about the symbol 'start', but I did put '_start' since that is what linux would take without complaining. So what I do is to take what you like

.globl  start, _start

start:

_start:

That it, now I can assemble and test that little program. 

Transporting information across different source and destination is part and parcel of computer stuff. So it is required that some sort of protocols has to be in place between the two source and destination. Now one of the basic thing a protocol needs to handle is to make sure the feeding of information does not over feed the destination too frequently. So the source needs to pace itself by obeying the order destination provides. And that is the essence of flow control.

Source, destination, and intermediaries all try to pace things based on their capability too. And that capability is usually to hoard stuff, we call it buffering. Buffer requirement is essentially a part of flow control, yeah come to think about it! Estimation of buffer requirement is a fundamental design criteria for all sorts of devices that represent source or intermediate device or destination. As a simple example if a device has, in theory, infinite buffer, then it does not care about flow control. Whatever is you feeding rate, the device would be happy to take, assuming there is no processing bottleneck.

But that is not the case, every device will have some fixed finite number of buffers.  And the estimation is really based on a whole lot of things, such as - (a) traffic pattern (b) traffic intensity (c) processing capacity (d) and other stuff.

 As an example, lot of higher level protocols like TCP / SNA etc., does have flow control. Some busses have flow control, and most of the device also have flow control. They are different in architecture and implementations as well, but the main point is that there are multiple level of flow controls among different levels of processing informations. And often one face with the debate that why do we need so many flow controls. For example is not it enough to just have TCP level flow control and no network device level flow control. Well the answer to that would be a definite NO. The reason is that if the device talks to another device that does not have TCP/IP layer processing, it needs a lower level flow control. For example switches is one of the main reasons that network device need lower level flow control. On the top of it, there are other source and destinations even at a lower level. For example, the PCI-E transactions between PCI-E elements. Yes once again these need flow control, and it is one of the reason that PCIE is a serial bus with full of protocols.

So the main idea is - minimizing information loss while in transit and minimizing the retransmit.