About educcess

Posts by educcess:

For loop VS While Loop – which is faster ?

Many times I have come across a very basic question Whether For loop is faster ? or While loop is faster in C and other languages. Most of the times an unexperienced developers use to ask this question to me. So I thought to write an article on this .

The answer to this question is – there are no difference in performance , both For and While loop perform same , but this may differ a little for different compilers. It may slightly differ for different compilers because it depends on how a compiler compiles and generates machine code for the same. Even thought those factors are negligible .

I managed to figure it out by looking into the intermediate assembly code generated for both For loop and while loop. Looking at the assembly instructions generated for both , it shows that both have similarly equal number of instructions and similar instructions.

Instead of explaining it in text, I am posting screenshot of assembly code generated with marking of details. The assembly code is generated in Mac OS X , XCode by using Assemble option.

For Loop Assembly Code

For Loop Assembly Code

 

While Loop assembly code

While Loop assembly code

 

 

Endianess – When it matters ?

We all knew what is an endianess in computer architectures , the big endian and little endian architectures works different. Big endian where most significant bit stored at smallest address where as in little endian least significant bit stored at smallest address.

The world’s most popular processor Intel is little endian machine, where world’s most oldest motorola processors are all big endian. All the network protocols , routers works in big endian architecture.

Most of the time endianess doesn’t come into picture , because programmers doesn’t deal with very low level bits. Ideally when I say int number = 4; the program runs properly in both kind of architecture. The reason is when the value is processed , it will be always in processor registers, not directly into memory. Endianess comes into picture when we deal with memory bits.

For example – If we are applying some effects or transform on an image by using shift operators or some standard APIs, then the things might go wrong. OpenGL APIs internally deal with shifting the bits in memory to perform certain operations in such cases the entire image may look inverted.

The common convention followed in networking is big endian , all TCP/IP protocols and other network protocols deal with big endian data. Those who work on networking should be aware of endianness. 

 

Let us take an example how endianness might be a problematic

Assume that a System 1 is sending an ip address to System 2 , If system 1 is 80×86 processor which is a little endian and System2 is SPARC machine which is a big endian. An ip address 192.168.2.1 sent from System 1 , will be received by SPARC machine and converts it to big endian format.

 

If I consider 192.168.2.1 , let us convert this to Hex value

ip address to Hex a logic =  take each octet , multiply it by 256 ^ n, where n is zero based index

= (1 * 256 ^ 0) + (2 * 256 ^ 1) + ( 168 * 256 ^ 2) + (192 * 256 ^ 3)  

= 1 + 512 + 11010048 + 3221225472

= 3232236033 ( decimal )

= C0A80201 ( Hex )

System 1 is sending value C0 A8 02 01 , but System 2 will interpret it as 01 02 A8 C0

This kind of issues happens due to endianness.

 

 

 

Recursion VS Iteration – An Analysis with fibonacci and factorial

Recursion VS Iteration – An Analysis with fibonacci and factorial

It is always difficult to choose one over the other , but recursive and iterative methods can be chosen wisely by analysing the algorithm with certain input values. Let us study the usage of recursive methods and let us analyse how recursive call works internally.

How Recursion  Works ?

The concept of stack frame comes into picture when we deal with recursion, for each call a stack frame will be created and the values will be pushed into stack. Once the recursive call reach the final condition, the program will start popping out from the stack frame and returns the values . A C program to find factorial of given number and analyse it using recursive method. 

Let us take an example –

Finding Factorial of a Number

long int count = 1;
long int factorial(long int n){
  count++;//to count how many times the method getting called
  if (n == 0) {
   return 1;
  }
  return n * factorial(n - 1);
}

int main(int argc, const char * argv[])
{
   int n = 13;
   printf("Factorial of %d = %lu , number of time called %lu\n",n,factorial(n),count);
   return 0;
}

Let Analyse how it works ? 

When factorial(n) will be called every time , a stack frame will be created and the call will be pushed to stack, the entire call stack looks like below. The below image shows stack operations for a given recursive call.

StackFrame

If I give input as 10, the recursive method will be called 12 times,

If I give input as 14, the recursive method will be called 16 times,

If I generalise the number time of call then it will be – n + 2 times.

This looks ok, but let us take different example and try to compare both. A program to find fibonacci number and analyse it with respect to call stack.

Finding Fibonacci number 

long int count = 1;
long int fibonacci(int n){
    count++;
    if (n <= 1) {
        return n;
    }else{
        return fibonacci(n-1) + fibonacci(n - 2);
    }
}
 
 
long int fibonacciIteration(int n) {
    int x = 0, y = 1, z = 1;
    for (int i = 0; i < n; i++) {
        x = y;
        y = z;
        z = x + y;
    }
    return x;
}
 
int main(int argc, const char * argv[])
{
    int n = 4;
    printf("fib value recursive %lu ",fibonacci(n));
    n = 100; // let us give 100 as input for iterative method
    printf("\nIterative method %lu ",fibonacciIteration(100));
    printf("\nnumber of time called %lu\n",count);
    return 0;
}

Now the call stack looks as follows, memory layout of call stack for a given recursive call of fibonacci program. 

Call stack of Fibonacci

Call stack of Fibonacci


Let us analyse this example ,

If we observe the callstack , fib(2) , Fib(1) and Fib(0) called multiple times, which is not necessary as the value will be calculated .

For input n = 4 , the total number of times the fibonacci method called = 10.

Now let us take few more inputs and check how many times the function is getting called.
n = 5 => 16 times,
n = 6 => 26 times ,

If I generalise the number of time the function called will give us an astonishing result ,
number of times fib function calls = (2^n – C), Where C is constant, and very less ~ 2^n

Let us take some interesting inputs 🙂
n = 30 => 2692538 times
n = 31 => 4356618 times (just by increasing n by 1 , the number of times function called became so huge)

n = 42 => 866988874 times , Unbelievable !!! These results shows how recursive method is dangerous in this case.

n = 43 => my program not even stopping , even after 5 minutes .

Let us look on iterative method 

long int fibonacciIteration(int n) {
    int x = 0, y = 1, z = 1;
    for (int i = 0; i < n; i++) {
        x = y;
        y = z;
        z = x + y;
    }
    return x;
}

This method will return , fibonacci value within few seconds even if input n = 100 .

Conclusion is , selecting between iterative and recursive methods should be decided based on the problem statement, the problem looks simple with simple inputs, but analysing the problem with bigger inputs will actually shows the big picture .

Update: Complexity of recursive Fibonacci –

The recursive equation for this algorithm is T(n)=T(n1)+T(n2)+Θ(1)

For this it will be T(n)=Θ(ϕn)

where ϕ is the golden ratio (ϕ=(1+5) / 2).

I strongly recommend to read Introduction to Algorithms 3rd edition : Purchase in FlipKart

 

Understanding of computer Memory With a C Program

Memory is one of the important resource , we can say its a crucial resource in computers. In a limited amount of memory an operating system tries to satisfy all the applications and the need of memory.

Let us try to understand how a memory looks – the theory and an example simple program to understand the concept in a better way.

Memory –

 memory

 Understanding Of Memory

When we say a memory is allocated for an instance ! How exactly you visualise the memory and allocation ?

A memory is array of smallest unit of space which is nothing but a byte of space location. If a variable holds an integer, float or any type of data, it occupies certain set of such memory locations. Typically it looks like below.

Array of memory locations

In the above memory structure we can see how data is stored in memory.

The String “XYZ” , the number 15 , it looks like at location 12, number 15 is stored, starting from location 21, string XYZ is stored.

If I dig into the depth of it, every thing in computers will be converted into binary , so ‘X’ will be converted into binary which occupies 8 bits , similarly each character will be converted to its ASCII and the ASCII value will be converted to binary ( Ref – http://sticksandstones.kstrom.com/appen.html )

Let us consider one example and try to fill the memory locations 

char subjects[3][2][25] ;

The above character multidimensional array will holds 2 subjects of 3 semesters each of length 25 characters.

subjects[0] -> will give you 2 subjects of first sem, each subject of 25 characters.

subjects[1] -> will give you 2 subjects of second sem, each subject of 25 characters.

If I assign the subjects to this array , the subject names in memory looks like below

charArrayinMemory

For better understanding just check the below diagram of memory layout

Memory Layout

 

How string copy becomes costly – An Analysis

Let us try an interesting example , a simple but an interesting analysis at the end.  Let me start with a requirement by taking an example .

Assume that you are getting ‘ N ‘ number of strings from an xml file , where ‘ N ‘ is really huge. Each string is again having too many characters. A library is being used to parse the strings from the xml file, library will return the strings one by one.

The library returns string and the length of the string in a callback method, our program has to copy the string to keep a copy of it.

Let me write a simple code for this , to make the code simple for better understanding I will avoid library usage and all other stuff. Just let us focus of core problem , that is copying ‘ N ‘ strings.

int main(){
   getStrings();
  return 1;
}

void getStrings(){
   int numberOfCharacters = 2014; // this length will be returned by Library after parsing xml file
   char *string1 = (char*)malloc(numberOfCharacters); // to hold string
   strcpy(string1,"This string we will get  from library, for this example we are hard coding it");
   char *string2 = (char*)malloc(numberOfCharacters); // to hold string
   strcpy(string2,string1); // have a  copy of string returned by library .
}

The above problem looks very simple, but the last strcpy() call will become costly for you since number of strings are too big. 

How strcpy is costly ? 

strcpy typically looks like below –

char* strcpy(char * string1, const char * string2){
  char * originalStringPointer = string1;
  while(*string2 != '\0'){
    *string1++ = *string2++;
  }
 *string1 = '\0';
 return originalStringPointer;
}

So behind the screen for every string copy ( for all your N strings, where N is too big ) , strcpy method iterates each character and copies .

Let us take one example and analyse this – 

Analysis I –

If I have 100 strings all of same length say 10

then the number of times the loop in strcpy runs is 

100 * 10 = 1000  times, this doesn’t make much difference .

Analysis II – 

Let us take bigger value , 

If I have 3000 strings of length 100 each 

then your loop in strcpy runs 3000 * 100 = 3,00,000 times 

3,00,000 times is big, also we assumes all strings are of same size and that is just 100, but in realworld example that might be different again.

So in such a scenario your strcpy becomes very costly for you, your application performs really bad that too if you didn’t handle this case properly. If by chance you are reading all the strings during the app launch, your application takes several seconds to show the first screen.

A clever programmer finds a better way to achieve this with better way.

Better approach for better performance –

If you observe the problem statement, just notice that we have a string and its length both. so instead of using strcpy we can go for memcpy which actually just transfers chunk of data from one location to another location rather than copying it character by character.

so just replacing strcpy() by memcpy() avoids 3,00,000 loop executions in your second analysis .

your getStrings method looks like below now

void getStrings(){
  int numberOfCharacters = 2014; // this length will be returned by Library after parsing xml file
  char *string1 = (char*)malloc(numberOfCharacters); // to hold string
  strcpy(string1,"This string we will get  from library, for this example we are hard coding it");
  char *string2 = (char*)malloc(numberOfCharacters); // to hold string
  memcpy(string2,string1,numberOfCharacters); // have a  copy with memcpy.
}

 

It is always a very good practice to find best possible way to do something, even a one line code which runs hundreds, thousands of times will become bottleneck. 

Introduction to Struts

Struts is an open source web application framework which will be used to develop the web-
based applications. Struts framework was implemented based on 3 popular design patterns.

  • MVC design pattern.
  • Front Controller design pattern.
  • Application Controller design pattern.

MVC design pattern :-

There are 3 layers in MVC Design pattern

I.  Presentation Layer

II.  Controller Layer

III.  Model Layer

Capture1

I Presentation Layer :-

It contains the presentation logic and can be implemented with JSP or with any other presentation frameworks like flex, velocity etc. Struts Presentation Layer contains following components.

1)     JSPs/HTMLs
2)      Struts custom tags
3)      Form Beans
4)      Message Bundles

1)     JSPs/HTMLs:

In struts presentation layer JSPs will be used to display the data to the client and also used to receive the input data from the client.

2)      Struts custom tags:

Apache has implemented various custom tags for the struts based application development and are categorized as follows.

  • Html tag libraries
  • Bean tag libraries
  • Logic tag libraries
  • Tiles tag libraries
  • Template tag libraries
  • Nested tag libraries
  1. Form Beans:

Form bean is a simple java bean styled class which stores the data. When we are writing the form bean java class, the bean class must be a subclass of one of the following.

  • ActionForm
  • DynaActionForm
  • ValidatorForm
  • DynaValidatorForm
  • ValidatorActionForm
  • DynaValidatorActionForm

 

  1. Message Bundles:

Message Bundles are nothing but property files which contain key value pair. Mainly message bundles will be used to achieve i18n (internationalization).

II Controller Layer :-

The Controller portion of the application is focused on receiving requests from the client (typically a user running a web browser), deciding what business logic function is to be performed, and then delegating responsibility for producing the next phase of the user interface to an appropriate View component. Following are the various components which we use in struts controller layer.   

   i)   ActionServlet

   ii)  RequestProcessor

   iii)  Action class

 i) ActionServlet:

ActionServlet is the one and only servlet for the entire struts application which is implemented based on Front controller design pattern and this servlet is loaded during server startup time. ActionServlet is responsible for receiving all incoming request and delegating to RequestProcessor. It also initialize the struts-config.xml file.

 ii)  RequestProcessor

RequestProcessor is responsible for processing all incoming request. It is implemented on Application Controller Design pattern. RequestProcessor is responsible for identifying the incoming action class and its form bean, it is also responsible for managing life cycle of form bean. After getting response, it manages to return to corresponding jsp by using ActionForward.

iii)  Action class

Action Class is the beginning of application’s business logic.

III Model Layer : –

Since there are no predefined components for model layer in struts like presentation layer and controller layer, so struts will not deal with model layer. But struts allows us to make use of any of the following model layer.

i)    Simple JDBC component

ii)   DAO + Hibernate

iii)  DAO + JDBC

iv)  Spring

v)   Web services     etc…

STRUTS FLOW

Capture1flow diagram showing struts flow

Steps for the flow         

  • When we submit the request after entering value in jsp form, request will be submitted to ActionServlet which is configured in web.xml.
  • This ActionServlet is responsible for initializing struts-config.xml and this struts-config.xml file is     configured in web.xml.
  • ActionServlet delegates the request to RequestProcessor
  • RequestProcessor takes the incoming request uri and tries to find the matching <action> tag in struts-config.xml. If no matching action is found, then client will get “cannot retrieve mapping for action”.
  • Once matching action is found for the incoming request uri, then corresponding “name” will be taken and tries to find the corresponding <form-bean> under <form-beans> configuration. If no matching <form-bean> is found then client will get the error called “cannot retrieve definition for form beans”.
  •  Once matching is found, RequestProcessor is responsible for managing form-bean life cycle.
  •  RequestProcessor takes the <action> “type” which is Action java class and create the instance    for the first time. With that Action class instance, execute() method  will be called.
  •  Once execute() method is completed ActionForward will be returned to RequestProcessor with      the forward name associated with the ActionForward object and RequestProcessor will try to  identify corresponding <forward> inside struts-config.xml file.
  •  Once the forward is found then its path will be taken and will be forwarded to the client.
  •   RequestProcessor takes the <action> “type” which is Action java class and create the instance     for the first time. With that Action class instance, execute() method  will be called.
  •  Once execute() method is completed ActionForward will be returned to RequestProcessor with  the forward name associated with the ActionForward object and RequestProcessor will try to  identify corresponding <forward> inside struts-config.xml file.
  •  Once the forward is found then its path will be taken and will be forwarded to the client.

 

A Bird eye on Education System

This article is neither to judge quality of education nor to conclude on any plans or steps that have been taken by Government of India(GOI) to improve the literacy rate in the country.

The purpose of this article is just to provide certain facts and I would like to leave analysis of these facts to reader. Report on your analysis is welcomed through comments; do share your thoughts related to this article. All the data is collected from the reports which have been published by Government of India for public domain.

India is struggling with many issues, issues with respect to caste, religion, politics, languages , the mindset of people across the country varies a lot with respect to all the above factors. Despite of being such a diverse society, I would say India has achieved and reached many milestones in every sector. Considering education sector for this article, let us see what the report says.

Find out best realtime examples, interesting facts on concepts and all the formulas. The best mobile application for 10+ students (PUC I and II year students)

https://play.google.com/store/apps/details?id=com.dhi.educcesspu&hl=en

Android Mobile Application for 10+ students

Android Mobile Application for 10+ students

Achievements during 11th Five-year plan period

The result of 2011 census reveals that despite an impressive decadal increase of 9.2 percent points in literacy, national literacy levels have risen to no more than 74.0 percent (from 64.8 percent in 2001) Only 15 States/Union Territories, namely Kerala, Lakshadweep, Mizoram, Tripura, Goa, Daman & Diu, Puducherry, Chandigarh, Delhi, Andaman & Nicobar Islands, Himachal Pradesh, Maharashtra, Sikkim, Tamil Nadu and Nagaland could achieve 80 percent or above literacy rate.

The 2011 Census has shown that female literacy has increased much more than male literacy. While male literacy rate increased by 6.86 percent 279 points from 75.26 percent in 2001 to 82.14 in 2011, the female literacy increased by 11.79 percent points from 53.67 to 65.46 percent during the same period. Thus, by the end of the 11th Five Year Plan in 2012, the three Plan Targets would not have been achieved: overall literacy rate being short by five percent points.

Increase in literacy between 2001-2011 at National level:

There has been a substantial progress in literacy with the planned intervention and sustained effort from 64.83 per cent in 2001 to 74.04 per cent in 2011, an increase of 9.21 percentage points.

edu

Sakshar Bharat

The Prime Minister launched Saakshar Bharat, a centrally sponsored scheme of Department of School Education and Literacy (DSEL), Ministry of Human Resource Development (MHRD), Government of India (GOI), on the International Literacy Day, 8th September, 2009.

Despite significant accomplishments of the Mission, illiteracy continues to be an area of national concern. 2001 census had revealed that there were still 259.52 million illiterate adults (in the age group of15 +) in the country.

Fund utilization and capacity building to achieve the milestone in education

During the financial year 2011-12, a total amount of Rs.488.50 crores was provided for Sakshar Bharat programme as Central share. An amount of Rs.429 crores was released till December 2011 to State Level Mission Authorities (SLMAs). A total of 1098.33 crores was released by NLMA to SLMAs during the last three years.

Government is keep trying and funding to increase the literacy rate within the country, in this process government has moved from SSA(Sarva Shiksha Abhiyan) Program to RTE ( Right to Education ).

RTE-SSA Financial Allocation

The Governmentn of India approved an outlay of Rs 71,000 crore for SSA in the 11th Five year plan. Considering the increased requirements, ,the Government of India approved an outlay Rs 2,31,233 crore for the combined RTE-SSA programme. This increased outlay was for a five year period from 2010-11 to 2014-15 to be shared between the Center and the State on a 65:35 ratio (90:10 for North Eastern States). The Finance Ministry allotted Rs 25,555 crore for the RTE-SSA programme for 2012-13. Just check the report chart below, government has spent 19,103,22cr upto January 2012.

incrores

Considering all the facts, percentile of literacy between 2001 – 20011, a 10 year period, the amount of money spent on it, the results may not be satisfactory, the reason is that focusing only on spending and opening schools doesn’t give the expected result, but focusing and executing the program towards quality education does bring the change. The path towards achieving really quality education is not an easy, more and more educated people has to come front to bring the change, it is not just the effort of government.

Interesting way of explaining Pythagoras Theorem

Pythagoras Theorem Explained – Mathemagic with Bawa

Sources of data

http://mhrd.gov.in/sites/upload_files/mhrd/files/RPE_2011-12.pdf

http://saaksharbharat.nic.in/saaksharbharat/homePage

http://ssa.nic.in/

An yearly report

http://mhrd.gov.in/documents/term/140