Monday, December 27, 2010

Freeware Android Paint with source code...

Here is one of my freeware android apps called AndroidPaint. You can install it from the Google Play. Or you can download it from here or through

Using the Android Paint app, one can draw geometrical shapes and free hand drawing on an Android device. In the future version i will refine the app to give the user more drawing options and more regular shapes to draw.

To start with, one will have to choose from the menu options and then draw.

The screenshot of this application is as follows:


Here goes the source code of this application...

There are lots of scopes to re-factor this application... for example we can introduce a singleton factory class which will be responsible for creating different shapes... i thought of making the source code available to everyone after i did these kinds of refactoring... but i have lost the momentum... it will be really nice if someone works upon these...

Monday, October 4, 2010

Structure Alignment - my understanding...

The data should be properly aligned for better efficiency. The CPU accesses the memory on WORD (4 byte) boundary...
Thats the reason we add padding bytes in a structure for proper alignment...

The the result of  my research on structure alignment using a gcc compiler is given below... The alignments of the structures are implementation specific... Typically a char will be 1 byte aligned, a short will be 2 byte aligned, an int will be 4 byte aligned and a pointer will be 4 byte aligned... this means that a char can appear at any boundary, a short can appear at any even boundary, and an int can appear at a four byte boundary...

To test the alignment of a structure and the offset of one of its member, i wrote this code:

And the result of alignment was 4.

The result of offset of the integer was 4.

If we use gcc, the size of a long double will be 12 bytes whereas its alignment will be 4 for a IA32 machine.

For different structures, the alignment of its members have influenced the size of them as follows:

typedef struct XYZ
{
//total 12 bytes
/*char c;//1 byte + 3 padding bytes
int x;//4 bytes
short s;//2 bytes
char d;//1 byte + 1 padding byte
}MyStruct1;


typedef struct XYZ
{

//total 8 bytes
/*short s;//2 bytes
char c;//1 byte + 1 padding bytes
int x;//4 bytes*/
}MyStruct2;


typedef struct XYZ
{

//total 12 bytes
/*char a;//1 byte
char c;//1 byte
short s;//2 bytes
int x;//4 bytes
char d;//1 byte + 1 padding byte
short s1;//2 bytes*/
}MyStruct3;


typedef struct XYZ
{

//total 12 bytes
/*char a;//1 byte
char c;//1 byte
short s;//2 bytes
int x;//4 bytes
char d;//1 byte 
char e;//1 byte + 2 padding bytes*/
}MyStruct4;


typedef struct XYZ
{

//total 16 bytes
char a;//1 byte + 1 padding byte
short s1;//2 bytes
char c;//1 byte + 1 padding byte
short s;//2 bytes
int x;//4 bytes
char d;//1 byte + 3 padding byte
}MyStruct5;


typedef struct XYZ
{
//total 20 bytes


char a;//1 byte + 1 padding byte
short s1;//2 bytes
char c;//1 byte + 1 padding byte
short s;//2 bytes
double x;//8 bytes
char d;//1 byte + 3 padding bytes
}MyStruct6;

We can use #pragma pack(1) directive to force the compiler to avoid the padding of the structure elements. Hence with #pragma pack (1) directive, the MyStruct5 will give the size of 11 bytes.







    I would like to end this discussion with an example of how the alignments of the structure members affect the size of a structure.

    Consider the following structure MyStruct1.

    typedef struct XYZ
    {
    //total 12 bytes
    /*char c;//1 byte + 3 padding bytes
    int x;//4 bytes
    short s;//2 bytes
    char d;//1 byte + 1 padding byte
    }MyStruct1;
     its total size is 12 bytes because of padding.

    Now let us reorder the members of the same structure as follows:

    typedef struct XYZ
    {
    //total 8 bytes
    /*char c;//1 byte 
    char d;//1 byte
    short s;//2 bytes
    int x;//4 bytes
    }MyStruct1;

    The size becomes 8 bytes. So there is a reduction of 4 bytes by just reordering the members of the structure. If we happen to do embedded programming or programming for small devices, we need to take care of this fact because memory is a major constraint in these devices...

    Tuesday, September 28, 2010

    Merge Sort - for my students...

    Using divide-and-conquer policy we can solve a sorting problem. The divide-and-conquer method suggests the sorting algorithm with the following structure.: if n is one, terminate; otherwise partition the collection of elements into two or more sub collections.; sort each; combine the sub collections into a single sorted collection.


    It can be depicted as follows:


    void Sort(a[], n)
    {
        if(n>= k) { //k is global
            i = n/k;
            j = n-i;
        Let A consist of the first i elements in a[]
        Let B consists of the remaining j elements in E
        Sort(A,i);
        Sort(B,j);
        merge(A,B,a,i,j); //merge A and B into a[]
    }
     else sort a[] using insertion sort.
    }


    In the above pseudo code, if we make k = 2, we get merge sort.

    The complete source code of Merge Sort can be found here.


    Analysis of Merge Sort:

    From the following algorithm of Merge Sort, the run time T(n) can be deduced as follows:

    void MergeSort(int a[], int low, int high)
    {
    int mid;
    if(low(high))
    {
    mid = (low+high)/2; ==> Θ(1)
    MergeSort(a,low,mid); ==>T(n/2)
    MergeSort(a,mid+1,high);==>T(n/2)
    merge(a,low,mid,high);==>Θ(n)
    }
    }

    Therefore we can write T(n) = 2T(n/2) + Θ(n)

    Comparing it with the Master theorem, we get a = 2, b  = 2 and d = 1. Hence a = bd which means it is the second condition of the Master Theorem.

    Thus we get T(n) = Θ (n log n)

    Friday, September 24, 2010

    Quick Sort - for my students...

    Quick Sort is a sorting algorithm where we apply Divide and Conquer policy. In this sorting algorithm, the n elements to be sorted are partitioned into three segments - a left segment, a middle segment and a right segment. The middle segment is called pivot. The middle segment exactly contains one element. The partition is done in such a way so that all the elements in the left segment have key less than the pivot and all the elements in the right segment have keys greater than the pivot. As a result, the left segment and the right segment can be sorted independently.

    The basic principle of Quick sort is as follows:

    • Select an element from a[0:n-1] for middle. This element is called pivot.
    • Partition the remaining element in such a fashion that all elements in the left of the pivot have keys less than the pivot, and all the elements in the right segment have keys greater than the pivot.
    • Sort left segment using quick sort recursively
    • Sort right segment using quick sort recursively
    • The answer will be left followed by middle followed by right.

    The algorithm of the quick sort can be found here.

    Debugging of the Algorithm of the code:

    Step I: To begin with we get m = 0, n = 6, hence k = 3. After doing swap(&list[m],&list[k]), we get key = 5. The following two steps make i = 1 and j = 6.

    Step II: Now the loop starts.

    II while loop fails as list[i] (7) is not less than key (5). Hence i does not increase and it remains 1. The III while loop succeeds (as list[j]  > key)and hence j is decremented. So j becomes 5. In the next iteration of the III while loop, the list[j]>k condition fails, hence j remains 5 and we exit the III while loop. So we exchange list[i] and list[j] and the array becomes {5,1,8,3,2,7,9}

    Next the II while loop succeeds and we increment i. Hence i becomes 2. The III while loop also succeeds and hence j becomes 4. So list[i] = list [2] = 8 and list[j] = list[4] = 2. So when we swap between list[i] and list[j], the array becomes list {5,1,2,3 8,7,9}.

    Next the II while loop succeeds two times and we get i = 4. The III while loop also succeeds and we get j = 3. As j becomes larger than i, we come out of the I while loop.

    Next we do swap(&list[m],&list[j]). And the list becomes list {3,1,2,5,8,7,9}

    After that we recursively sort list{3,1,2}, the left segment and list{8,7,9}, the right segment.

    See how all the elements of the left segment are less than 5 and all the elements in the right segment are greater than 5.

    This is how we achieve the Quick Sort.

    Sunday, September 19, 2010

    Pointer Semantics Vs Value Semantics

    Value semantics means we directly deal with the values and we pass copies of that value around. We can say that nobody will change the value.

    However, in pointer semantics we deal with pointer, and anyone can change the value at the pointer location.

    Consider the following program.

    /*
     * main.c
     *
     *  Created on: Sep 18, 2010
     *      Author: administrator
     */

    #include

    void f (int * p, int * q) {
    p = q;
    *p = 2;
    }

    int i = 0, j = 1;


    int main ( )
    {
    f(&i, & j);
    printf("%d %d\n", i, j) ;
    return 0;
    }

    The result will be 0 and 2. Why? Let me explain it to you.

    We have two global variable i and j and we pass the pointer of these two variables to the function f.  When we do p = q, we actually loose the reference of i, and we get two pointers namely p and q both pointing to j. then when we do * p = 2, we actually change the value of j to 2. 

    The whole thing can be depicted by the following diagram...



    However, as we lost the reference of i in the step p = q, in the main program, the value of i that gets printed is the global variable that is 0. Hence we get the result as i = 0 and j = 2.

    Hope this explains the pointer arithmetic to my students...

    Wednesday, August 25, 2010

    Handy Maths to solve Data Structure Problem

    Let me first define the problem:

    Prob: F(n) is a function defined as :

    F(n) = 1 ; n = 1

    F(n) = F(n-1) + 1/n ; n>1

    Prove that Big Oh of F(n) is log n

    Solution:

    F(n) = F(n-1) + 1/n
    = F(n-2) + 1/(n-1) + 1/n
    =F(n-3) + 1/(n-2) + 1/(n-1) + 1/n

    This kind of series is called the Harmonic Series and can be represented as 1 + 1/2 + 1/3 + 1/4 + ......+ 1/n

    Mathematically we can prove that the sum of an Harmonic series is ln n + gamma( a constant). This constant is called Euler's constant and its approx value is 0.57721

    Therefore, we can say limit   f(n) = limit ln n + gamma
                                   n->infinity       n->infinity

    Hence                limit   f(n)/log n 
                             n->infinity 
                           = limit (ln n + gamma)/log n
                              n->infinity
                           = limit ln n/log n  +  gamma/limit log n
                               n->infinity                  n->infinity
                           = ln 2 + 0
                           = ln 2

    Hence we can say F(n) = O(log n)

    You can find the document here.

    Thursday, August 19, 2010

    For my Data Structure Students - Insertion Sort

    The Algorithm -

    Lets define a function to insert an integer into a non-decreasing sorted array. See the function void insert(int x[], int& length, int& number_to_be_inserted). What it does, is that it starts scanning the array from the end - the maximum number (as it is a non-decreasing array). Whenever it finds that the number_to_be_inserted is less than than the number in the array, it shifts the position of that number in the array towards right. Otherwise it inserts the new number in that position. This principle can be applied to Sort an array. We will start with an one element array. It is obviously sorted. We will pick up the next element and put it in the right place of the sorted array. Thus we get a two element sorted array. Similarly we can get a sorted array of size n.

    In the following code snippet, the Method I is the Algorithm with a separate Insert Function. The method II is the sorting algorithm with the Insert function inbuilt into it.

    The source code of Method I can be found here.

    The output of this program is as given below


    The source code of Method II can be found here.

    The output of this program is given below


    Hope you enjoy this study.

    For my Data Structure Students - Selection Sort

    As mentioned earlier, i have started writing code and analyzing of various data structure area of computer science... Here is one such Sorting Algorithm called Selection Sort. In the first pass, it just finds the minimum number and exchanges it with the first place, in the second pass it finds out the second most minimum number and exchanges it with the second position.


    Please find the source code of the Selection Sort from here.


    The result of the code is as shown below. Please look at how at each outer loop pass, the small numbers occupy the places in the beginning of the sorted array...






    Analysis:

    For first outer loop, the inner loop goes for n-1 times, for the second outer loop, the inner loop goes for n-2 times and so on. The outer loop itself goes for n-1 times.

    Hence f(n) = (n-1) + (n-2) + (n-3) + ....+ 2+1 = n*(n-1)/2

    Hence O(n) = n^2

    Hope you enjoy this...

    For my Data Structure Students - Bubble Sort...

    As a professor of computer science i have started recapitulating the basic theoretical computer science. Few days back i have written the code for bubble sort and did its analysis. I would like to share it with the student community...

    You can find the source code from here.

    The result of the above program is shown below.



    Please have a look at how at each pass of the outer loop the large numbers are pushed towards the end.


    Analysis:


    The outer loop of the bubblesort algorithm does n times. For first outer loop the inner loop is for n-1 times, for second outer loop the inner loop is for n-2 times and so on.

    Hence total loop count is (n-1) + (n-2) +........+2+1 = n*(n-1)/2

    Hence O(n) = n^2

    Hope this discussion helps the student community...

    Friday, August 13, 2010

    For my Microprocessor Students

    I got this resource by googling. Hope this helps the student community.

    Microprocessor Training

    A good simulator for 8085 programming on PC is GNUSIM8085 and it is available at http://gnusim8085.org/


    The interface of GNUSIM8085 looks like the following.

    Monday, July 19, 2010

    Ubuntu video screen capture - XVidCap

    I was wondering if i could get any tool for video screen capturing for Ubuntu. With a little bit of googling, i found XVidCap. Here is my first experience with the video screen capture of one of my Android Applications.



    Hope this information helps others...

    Monday, March 29, 2010

    My first experience with OpenCV

    OpenCV is an opensource library for computer vision. It is available at http://sourceforge.net/projects/opencvlibrary/

    With the help of some of the internet samples, i tried to play around with OpenCV from past two days. And here is one such application. It actually plays an AVI file.


    You can find a nice tutorial on OpenCV at http://www.site.uottawa.ca/~laganier/tutorial/opencv+directshow/cvision.htm

    Here is a glimpse of how my application will look like.



    Hope it gives some insights to others who are interested in computer vision.

    Friday, March 12, 2010

    Cubicles in Indian IT companies...

    The way we behave in a crowd or in solitude is totally different from the way we behave in a place surrounded by few known people... In the first case we become carefree and tend to break all sorts of barriers... in the second case we restrict ourselves to some extent... in the first case when we break free, we may create something new, do something highly innovative... however its just not possible in the second case....hence i believe to get some Aha-product from our IT companies, we must first break the cubicle culture that exists now and let the developers become care-free...

    Thursday, March 4, 2010

    Training on C++, Android, UML and Design Pattern

    I am interested in providing training on subjects like C++, UML, Android, Design Pattern, Java/J2SE etc. Please have a look at my training website

    som-itsolutions

    to get an idea.

    If you are interested, please email me.

    Tuesday, February 23, 2010

    The Importance of Google...

    The usefulness of Google is not very surprising to many...however, for me its one of the greatest democratizing tools...it has democratized the concept that is called knowledge which was once a well guarded property in the hands of a few...

    let me elaborate it a bit...i think whatever little related to technology i have learnt so far, is simply by means of Googling... even these days to remove the programming errors i take the help of mighty Google...to elaborate it more, for example, today i became curious about the way WiFi can be used in the industrial automation domain... so i googled it and got a fair amount of idea which includes ZigBee to Cisco's Wireless Plant Solution...I became curious about whether the data collected by sensors in a plant can be processed via cloud...i am interested in this topic because of its social implication...think about it that if the plant's data can be processed across the continent, then no one will have to do night shift duty... So i googled about that and got some idea about Helios platform from Eurotech... when i want to know if the 802.11n has been officially released, i just google that...when i want to know if there is anything similar or dissimilar between new(noThrow) of C++ and new(ELeave) of Symbian C++, i simply google that...when i want to know about the smart pointers in boost, i just google that...

    the google doc or the other tools like picasa and google map have come recently... but i am an ardent fan of Google from its inception because i think its only because of google i did not have to depend on anybody to learn about my technological area...

    Thursday, February 18, 2010

    My First Experience with Ubuntu QT

    I had installed Ubuntu quite sometimes back. I had also installed QT. However, i got my hands dirty in QT programming in the Ubuntu environment for the first time today. Let me share my experience with you.

    First i opened the QTCreator from the Applications->Programming menu. Then went to File->New. And followed the steps as shown in the pictures.














    After the project is created, i opened the mainwindow.ui and dragged a PushButton to the center of the main window. From the property, i changed the display text of the button as Hello World. its name is changed to HelloWorldBtn.



    Then i added a private slot in the mainwindow.h file as follows:

    private slots:
    void on_HelloWorldBtn_clicked();

    It means the signal connection is automatic.

    Then i added the following handler function in the mainwindow.cpp file:

    void MainWindow::on_HelloWorldBtn_clicked()
    {
    QMessageBox::information(this,"Som", "Hello World");
    }

    And its done... Of course to compile this code, i had to do #include (QMessageBox) in the mainwindow.cpp file...

    i ran the application... And when i clicked the button it showed the messagebox as the following picture...

    Monday, January 25, 2010

    Android Graphics

    I was curious about the graphical programming in Android... Fortunately i have found the library aChartEngine... As i was trying to play around with it, i came up with few trigonometric graphs... Hope this would give some pointers to the new comers about graphical programming in Android...

    The application looks like the following...



    And the graphs are like the following:

    Sin Curve



    Cosine Curve



    Tangent Curve



    Sinc Curve



    Damped Sin Curve

    Tuesday, January 19, 2010

    Android HomeScreen Management

    As i was trying to play around with Android HomeScreen, i came up with this application to add any application to the HomeScreen. I think it can work as a good project for the beginner of Android programming.

    The home screen looks like the following after i added two of the applications to the HomeScreen -one is my own KeyPadDialer and the other is the AlarmClock.



    And the HomeScreen Management Application looks like the following in the beginning:



    And after clicking the Spinner it looks this:



    The complete source code for my application can be found here.

    The manifest file for this application can be found here.

    And the layout of the application is given here.

    Hope this idea helps others...

    Saturday, January 2, 2010

    My first experience with Java

    As most of my experience lies in C++, when i started gaining interest in Java/J2SE i started looking at it from a C++ programmers point of view. Hence the first thing i googled was how to create a canonical class in Java. And i was astonished to find out that the way we do Assignment operator in C++ is not the same in Java. After some more googling i came to know about the clonable interface in Java. And it gave me the right direction...

    Then i googled about the String class in Java and found out that a String object in Java is immutable... i became curious and opened the String class of Java... And voila... no wonder... the character array that holds the contents of the String object is final... hence it is immutable... So i asked myself what happens when we do String newString = oldString in Java. And i got the answer... As the String class is not implementing the Clonable interface, when we do String newString = oldString, the oldString's contents get a new reference in newString... We loose any reference to oldString.

    But then i wondered how String S1 = oldString + "abc" would work. Because as i was googling i found out that Java does not support operator overloading... so how come the + operator is working fine for the String class? my first stumbling block... fortunately i found out the document at http://java.sun.com/docs/books/jls/third_edition/html/expressions.html#15.18.1 and my doubts were gone...

    So i wondered if Strings are immutable in Java, are not there any way to change the contents of a String object without creating a new object? i googled a little more and came to know about StringBuffer and StringBuilder classes and their mutable char array which will store that data... i delved into the classes a little more and found out about their append function.

    So far my investigation into the Java source code is fruitful...

    Hopefully i will be able to delve more into it and find out the nitty-gritties about the Java language...

    Share