Recursion

Every passionate programmer through one stage of his career must have tried this out and surely must have loved it. .These are not the best methods to solve problems, yet many complex problems have their natural solution as recursive ones. We have a lots of recursive patterns in nature to be observed. One of the most common is  a tree of which each branch is a tree in itself (though smaller  in size).

  

Even some geometric shapes (fractals) can also be observed to have recursive patterns. You can observe the repeating pattern which is being created recursively.

       

My python function for Koch-Snow flake (fractal) .

def flake(self,length):
if length < 10:
self.move_forward(l)
self.c.update()
return
else:
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)
self.rotate_right(120)
self.flake(length/3)
self.rotate_left(60)
self.flake(length/3)

My code for the above is available here

Ackermann function

One of the most interesting recursive problems I’ve encountered.

def A(m,n):
if m == 0:
return n + 1
elif n == 0:
return A ( m - 1 , 1 )
else:
return A ( m - 1,  A ( m, n - 1 ) )

It will be observed the behaviour of the function can not be predicted unless the values of the parameters ‘m’ and ‘n’ are known.

This kind of programming might be simple enough but it has its own drawbacks too. These kind of programs might not be supported at production level as they might eat up the system stack and affect the performance drastically.

The size of process stack(8MB) on a standard linux machine can be easily be manipulated with ‘ulimit’ utility.

ulimit  -a

A simple C code to observe how a recursive program eats up the process stack.


void foo( int i ) {
char temp[ 1024 * 1024 ]; //1Mb of memory will be allocated from the stack-frame
printf (" %d \n", i );
foo ( i + 1 );

}

int main() {
foo( 1 );
}

Each time the ‘foo’ is invoked a new stack frame is created and a character array of 1 MB size is allocated from it  .So after a definite number of recursive calls when their is no more memory left it results in ‘‘segmentation-fault” when the program tries to allocate memory in the new frame( outside of process’s address-space).

Changing the size of the array ‘temp’ and size of stack using

‘ulimit    -s    <value>’

will give interesting results.

Tail-Recursion

Here the recursive procedure call is kept at the bottom of the procedure. This is of significant importance because an optimization technique can be used where no new stack frame is allocated for a recursive procedure call, instead the new frame can be used to replace the current frame.  This kind of optimization is called tail-call-optimization . Many functional Programming languages like to cope with this situation has implemented

I tried out some of both basic & classical recursive problems during my graduation years. Anyone who is interested with recursive patterns I suggest you to try out the below problems.

Eight Queens Problem  ,  Towers of Hanoi.  , Min-Max Algorithm   ,Creating  Fractal shapes SICP Chapter-1 (a lot of mind-bending problems are in there)

Leave a comment

SL4A for Android SDK

                    Some years back Application development for Android was restricted to only Java lovers. Thanks to SL4A (Scripting Layer For Android) ,Scripting languages like Python , Perl  were introduced to Android Application Environment increasing the population of developers considerably. It attracts the developer by allowing them to edit and execute scripts on the Android device. Furthermore scripts can run interactively in a terminal or in background . These scripts have access to many of API‘s available to full-fledged Android Applications. Presently Scripting languages like Python , Perl , JRuby , Lua , BeanShell ,Javascript ,Tcl and Shell are supported on the SL4A.

Python On Android SDK 

      Following steps will lead to the installation of python interpreter on Android SDK.

Step 1: Add the path of tools directory to the environment

         Add the path of the directory  ‘andoid-sdk/tools’ to the path variable by executing the command

                            

                              $PATH =  $PATH:path_of_android-sdk/tools/                       


Step 2:  Create a SDCARD for storing application on Android.

          As Andoid API  2,.2 allows the user to save applications in sdcard insted of using the phone’s memory .So for that purpose a SDCARD of apprpriate size has to be created by executing the command

                              mksdcard    ‘size’M   ‘ sdcardname’ 


This creates a sdcard of  size of ‘size’ MB  with name as  ‘sdcardname’ .

              

Step 3:  Download the package from the following link



Step 4:  Start the Android SDK and install the SL4A

   Open the terminal and Start the Android-SDK by executing a command like

                              emulator @’avd-name’  -sdcard   ‘sdcardname’


     now  without closing this start a NEW terminal  and  install the sl4a package downloaded earlier by executing the command .

                             adb install  ‘sl4a_rx.apk’


now the icon for sl4a can be seen in the menu of SDK .

                                           

                             


Step 5: Installing python from SL4A. 

Now the python interpreter is to be selected in Sl4A . After clicking on the SL4A icon , click on the menu button on the SDK and then click on ‘View’ button  on screen .

then among the list displayed under the ‘View’ button click on the ‘Interpreter’

then among the list of Interpreter’s select Python.

                                              it will download python interpreter and install it.

finally the interactive python shell can be seen on the ‘Android SDK’.

This was helpful to me as my B.tech major project was to develop a Scheme to Python compiler for Android Simulator. So for that purpose it was necessary to get an environment setup where python code can be run for Android OS.

2 Comments

Concurrency in Ruby

I ve been using Ruby for quite a while now and there’s a lot of things I like about it. Somehow I m gonna write about something where Ruby is not really good at. Ruby VM is not really known good for handling concurrency.

Upto Version 1.8.7,  Ruby threads  were known as ‘Green Threads‘ as these implementations were not using the native OS kernel threads instead they were using the threads created by the MRI  in the user space thus making its operations quite costly.  In the Ruby version 1.9.2, YARV ( Yet Another  Ruby VM) was integrated with the Ruby VM, here although ‘Green Threads’ were mapped in one-to-one relation with the native kernel threads, they never are excecuted in parallel due to ‘Global Interpreter Lock’ put on by Ruby MRI. This version can never utilize the multi-cored systems efficiently thus Ruby 1.9.2 too was devoid from true concurrency.

Ruby threading models

A better solution for having true concurrency is to rely on the Java VM whose threading model has proven itself over the years and use JRuby.  JRuby  use system kernel Threads and the threads can run parallely in a multi-cored system.

Reference :

http://www.slideshare.net/ThoughtWorks0ffshore/concurrency-patterns-in-ruby-3547211

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-core/10252

http://www.infoq.com/news/2007/05/ruby-threading-futures

Leave a comment

Euler Project: Problem No .12

Although Euler Project  questions are designed to be solved sequentially. I wasn’t able to hold myself from giving it a try when I saw some of my roommates trying out this problem.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

I tried out the above problem and got myself a  solution using two basic rules from mathematics.

  1. The nth triangular number can easily be obtained as : (n * n-1) / 2
  2. If a number ” n ” can be written as a multiple of two consecutive numbers “p”  and “q” ie:  if n = p * q then number of factors of n = number of factors of p * number of factors of q – 1

My Solution is available at my git-hub id:

git@github.com:rohitnjan88/Euler-problems-in-Python.git

My solution clocked below 1 seconds.(  0.244 seconds to be exact ) .

Leave a comment

Face-Detection with OpenCv

Image manipulation of image stills taken from live camera has always fascinated me. For the beginners, it is  best to use the library ‘OpenCV’ . In my earlier post about OpenCV ,I was able to get image frames from the webcam  at a rate of about 30 images per second and then displayed it onto a window.
Object detection with OpenCV

         The task of Object Detection from a still image can be made simpler with the help of this library. Here for an object to be detected a cascade of boosted classifiers has to be trained and then used. A large set of over-complete haar-like features provide the basis for the simple individual classifiers.
A cascade of classifiers is degenerated decision tree where at each stage a classifier is trained to detect almost all objects of interest while rejecting a certain fraction of the non-object patterns.  Each stage was trained using the Discrete Adaboost algorithm .Discrete Adaboost is a powerful machine learning algorithm. It can learn a strong classifier based on a large set of weak classifiers by re-weighting the training samples.
For this (haar training procedure)  a large set of positive samples and negative samples are needed. Positive samples are those image set containing the object of interest and negative samples don’t have features of object of interest. For example if object of interest is face, then about 5000 image samples containing (the frontal face) and about 5000 negative image set(not having face) is needed.  OpenCV provide utilities to train the haar classifiers from the image samples collected (both positive and negative) .Finally , when a haar-classifies is trained, a xml file is created containing the features of object of interest. This ‘xml’ file can be used as per our needs for detecting the object from an image.I tried to detect faces from the images taken from the webcam and drew a circle on them.The haarcascade xml file was available with OpenCV documentation which is available in the standard linux distribution.So finally ,when the piece of code is executed, a window appears which displays the video taken from the webcam and draw a circle on the faces present in it.    Some images are

Some links which can be usefull
My program for the above can downloaded from my git hub id
 git@github.com:rohitnjan88/Face-detection.git

Leave a comment

The Metacircular Evaluator







              While reading one of the classical texts in the field of   computer science,  
‘Structure and Interpretation of Computer Programs’  (also known as the ‘Wizard’ book), I went through the concept of  ‘Metacircular Evaluator ‘ in the fourth chapter of the book ,where a ‘language interpreter’ for lisp is implemented and language used for
 this purpose is lisp itself.That sounded a bit confusing to me at first ….. but as i went through the structure of the program, it really amazed me as here in program the syntactic simplicity of the language ‘lisp ‘ was exploited to its best. As each and every expression in the language lisp was written as an S-expression (in prefix format, where the operation was written at first in the rest of the list),  the expression recognition was made simpler .   
                            The program in the book is the lisp formulation of environmental model of evaluation. There are two main things done here
  •               A complex procedure is evaluated by splitting it up into simpler subexpression which can be evaluated and the value is applied to the operand subexpression.
  •              2) A compound or user defined procedure is evalauted in a new environment, which can be created by extending the current environment by adding a frame.   
                      The environment here means that the variables are bound to a specific environment which helps to diffrentiate the local variables from global one’s. This is a great way to simulate the evaluation environment where a variable is assigned a value in a specific environment . Here the environment is implemented using  list data structure .

The Core of the Evaluator
                     The two main procedures in the evaluation processs are ‘eval‘ and ‘apply’

  •                ‘eval’  procedure is responsible for  evaluating an expression in it’s environment. This procedure takes the expression and the environment as input parameters. It is this function where the determination of type of expression is done and the corresponding action is invoked.
  •                 ‘apply’ procedure takes the operation and the parameters as the input and it applies the operation to it. This procedure diffrentiates between a primitive procedure to apply the primitives and a compound procedure , the body of whose is evaluated sequentially.

Leave a comment

Memory inspection using ‘Valgrind’



            Valgrind is a a programming tool suite used for debugging, profiling and detection of memory leaks which are quiet common in C,C++ programs. Detecting memory leaks is done by ‘memcheck’ tool  ,which by other means is a very difficult task to do .

To detect a memory leak using ‘Valgrind’ ,let us take an example code which does memory leak .For Example

                                           
Here in the example
   1)  in function ‘f‘  a char * variable ‘k’ is declared and  memory block of 100 bytes are allocated  to it from the heap. That means , the variable ‘k’  resides  on stack and it contains the  address of a memory block which is there in heap .
   2) the function ‘f’ tries to write in a memory block which has not been allocated to it .That is 
when we write
                                                 k[105] = 10 ;
 we are trying to access the memory byte which lies at an offset of 105 from the ‘k‘ . This memory byte was not allocated to ‘k‘ , hence can lead to serious untrackable bug and mysterious behaviour of the program . When the code is compiled using ‘gcc’ not even a single warning is given , forcing the programmer to believe that the function behaves normally.
                         Apart from this the when the function ‘f’ returns  to the ‘main’ function , the stack frame where the local variables of function ‘f’   (for example ‘k’) gets deallocated, so in this case the value in ‘k‘  ( the address of the 100 byte block) gets lost and thus memory leak occur. For this again, compiler can’t generate error or warning messages.

     So for coping with these kind of problems ,valgrind can be used.  

Using Valgrind  for detecting memory  leaks

    For using Valgrind the program has to be compiled with  ‘-g’  option  

as shown

                    gcc  – g   ‘program_name’.c

then the ‘Valgrind’ program can be used to  generate usefull information 


                    valgrind   –leak-check=yes   ./a.out

For example for the above piece of code it will generate meassages as

Here  in above messages,

   1)  In   ==5124==  , 5124 is the process id .  It is not that important
   2)  Display a stack trace showing where the problem occured. It can be usefull in large complex code.
   3)  Error messages show memory addresses involved as the second component.


Memory leaks  can be analysed by analysing the error messages



Conclusion

            This Dynamic analysis tool is usefull in detecting memory bugs and memory leakage.

Leave a comment

Follow

Get every new post delivered to your Inbox.