Memoization

Computers are very fast machines. But the computation time
also depend on the algorithm we choose. It can happen that
if a proper algorithm is not chosen, it may take a very long
time for execution.

On writing a simple recursive fibonacci generator function for
the nth element, fib(n), we will get fine results, but only for low
values of n. This is because fib(n) has exponential complexity.
Such functions grow very fast, so fast that even for small
values of `n' (where `n' is the size of the input), our program
will take a long time to finish.

Memoization is the process by which we speed up the situation.
The underlying principle is to create an associative array, say  
dict, which contain keys = n, and values = fib(n). Each time a
fib(n) is called, the associative array will be checked whether it
contain the key 'n'. If yes, just return dict[n]. Otherwise, create
a new key: value pair for dict. Thus, the number of recursion will
be drastically reduced, with this look-in-the-lookup-table policy.

Ofcourse, memoization is an upgrade to time compplexity, but
will consume space.
The implementation in Python looked like:

def memoized_fib(x):
if dict.has_key(x):
return dict[x]
else:
dict[x] = fib(x)
return dict[x]

def fib(n):
if n == 0: return 0
elif n == 1: return 1
else: return memoized_fib(n-2) + memoized_fib(n-1)

 dict = {0: 0, 1: 1}


In Python, the recursion limit is fixed by the interpreter itself. It can
be found in:
sys.setrecursionlimit(<limit>)

Now, set a very high limit, and run the code. If its high enough, u will
deplete the stack memory size (8 MB) of the C backend of your Python
virtual machine, leading to a segmentation fault there, which is
propagated back to your Python interpreter, crashing Python itself!

To fly with the Phoenix ...

Well, I must say, simplicity and brilliance is what a FOSS meet will be
all about, if you watch the proper people. For the National Conference
on Free Software And Education, September 10-12, 2010, me and
my four friends Prasanth, Remya, Sumith and Sunil geared up with a handy electronic instrument called the Phoenix(aptly named), and barged in
through the front gates. We came to know about the Phoenix from our
teacher, Mr. Pramode C. E., and beacme interested. This interest made
us to take it to the FOSS meet and do a few tricks with it, with guidance
from Pramode Sir. Some mistakes and pitfalls happened too.

First of all, whats 'Phoenix'? Its an electronic gadget with an Atmel
ATmega16 mcu inside it, with hardware peripherals including a DAC, ADC,
digital I/O pins, comparator, waveform generator, amplifier, etc,
necessray to build a simple circuit. The point? The whole Phoenix board
is set up such that a large variety of experiments from Physics can be
conducted with ease. Highly accurate measurements are thus possible.
Experiments include a simple charging-discharging cycle of a capacitor,
to alpha particle radiation measurement from a radiative source. Plus,
the board runs in C, with the computer front-end being Python. Hows
that? An 'open hardware', it may be called, maybe the first of its kind.

Coming back, the first day was at Tagore Centinery Hall, Calicut Town.
A banner highlighted by the face of Richard Mathew Stallman a.k.a
R. M. S. greeted us. Volunteeers and coordinators from NIT Calicut, gave
a brief picture of the schedule. Understood that, only the inaugral
ceremony with a keynote address from R. M. S. will be arranged that day.
At the far end, some tables were set up, and many free software users
were vigorously working with their laptops.

We were to see Mr. Sasikumar, the 'R. M. S.' of Kerala. Till then, we
were just standing their groping with our belongings, not knowing what
to do. Once we met him, the situation changed abruptly. We were greeted
with a warm, enthusiastic, polite smile, and ushered to the expo area.
The volunteers were asked to allot a table for us. Then, we became a
part of the event.

Till the original R. M. S. arrived on the scene, the expo continued. A
few people came to visit the 'stalls'. There were students, enthusiasts,
Physics teachers, and others who came to see what Phoenix was. There
were Phoenix users among them too, who wanted to see if any newer
features have been developed for the Phoenix.

Finally, I learned that R. M. S. had arrived, and has gone inside the
Hall, while my back was turned. Soon, everyone got inside, and I saw
the guy for the first time. I was seeing a cute-in-an-odd-kind-of-way,
big, living genius. I stared at him for long, with only one thought in
mind. I had to hear his voice too. Meanwhile the guest were asked to
get on stage. R. M. S. chose a side chair, but was ushered to the
center of the dias. Later, I saw him, kneeled down on his left leg,
drinking water from a bottle, kept on a table infrot of him. Well,
everything he did seemed cute and nice. A few moments later, he simply
yawned, and I couldnt help but smile.

There were to be about 8 more felicitations before the keynote address
from R. M. S. We couldnt wait that long, we had to get to our staying
places. We reached NIT Calicut, next day by noon. We arrived before for
the lunch session and quickly set up the table. Many people came to us
during the break, to know about Phoenix. There was a Physics teacher,
who believed Physics has to be 'touched and learned'. But i had a
counter-point that Phoenix could do things otherwise impossible in a
lab. One particular student was so excited to hear about Phoenix,
because he had been looking around for such a low cost instrument for
obvious purposes. There was a table for IIT Bombay, who had come with
their project to create spoken-tutorials for all the major free
software applications available now. Shortly after the lunch session
was over, we packed our things and got out, because we had to reach
our shelters in the same day itself.

Mistakes:
1. I didnt take photographs all through the event.
2. Didnt bring a banner or charts (showing the details of Phoenix) for
    display purposes.
3. Didnt bring a better experiment apparatus, perhaps it could have
    gained more attention.

Pitfalls:
1. We totally lost control of time. We were running for shelter to
    sleep, running to be present at the meet.
    In a nutshell, we couldnt sit for a single talk.

What we learned:
1. What to expect and what not to in a FOSS meet.
2. The feeling when someone like Dr. Prabhu Ramachandran whizzes past
    you, and you continue to stare blankly, unable to utter a single word.
3. How it is to bring 'something' to the meet and to bring 'some real
    thing' to the meet, from the fact that, we had also brought along an
    elementary study report on the TinyPy Virtual Machine v1.1.