Tuesday, November 25, 2014

Code to generate all possible combinations of balanced parentheses (equal to Catalan number) using recursion

Earlier, I thought that Catalan numbers were limited to my CS lab assignment only, but when I searched for it and looked for further details of it on wiki, I was fascinated by its applications in mathematics. I would write about it later when I understand those concepts to make it clear for others.

But right now, I am writing this post because I got an assignment in my DS lab and they wanted me to do this : given a number n,  print all the possible combinations of balanced parentheses, the total number of which would be ( for now, let us assume mysteriously ) equal to  the Catalan number, and yeah that too using recursion.

Here, n represents pairs of parentheses.
For example, n=1  =>  ()
                       n=2  =>  () ()

I hope this makes the question a bit clear before going for the code part.

I searched for the program on the net after spending a few hours on it, but to no rescue. Every single code here was using an explicit stack. So, I decided that I would post once I code it, and see here I am. I would like to explain the code, and would surely do it someday. But, for now I am just pasting the code so that, if in any confusion or problem, you can have a look at it, and if someone is truly interested, can also understand it. I would update it with the explanation part in the near future. Till then, have fun time breaking the code and building your own!!


int flag=0;    // I needed this, you will understand this if you go through the program

int balanced(char *a, int n, int i, int count1, int count2);
void catalan(char *a, int n, int i, char ch);

int main()
printf("how many pair of parentheses do you want : ");
int n;

char a[n];

catalan(a,n,0,'(');       // calling the Catalan function
return 0;

int balanced(char *a, int n, int i, int count1, int count2)
       // in this function, I am checking whether the generated pair is balanced or not
      //i assigned -1 to '(' and +1 to ')'
               return  -1 + balanced(a,n,++i,count1,count2);
else if(*(a+i)==')')
               // if closing braces are more, it can never be balanced, and there we need a global variable
if(count2>count1)   flag=1;
   return 1 + balanced(a,n,++i,count1,count2);
           return 0;

void catalan(char *a, int n, int i, char ch)
static int k=0;             // needed it, see below
           // if the below condition for k is not taken, we will get duplicates for every pair
           // reason -> have a look at the recursive conditions, the answer lies there
if(i==n && k%2!=0)      
int result=balanced(a,n,0,0,0);

if(result==0 && flag==0)
int j=0;
{ printf("%c",*(a+j));

Wednesday, November 19, 2014

My bill in the Youth parliament session "Educated India Enable India - Quality Education for All" organised in my college

Day before yesterday, a Youth parliament session was organised in my college and I fortunately got an opportunity to participate in it and I made it to the top among all other students, giving me a chance to visit the Indian Parliament the next summer :D  I would write a post regarding my experience with college parliament session in the near future and would update here with the link.

But today I was asked to give a digital version of my bill along with answers to a few questions so that they can get it published in the newspaper :D  Okay, once published I would surely attach a news pic with this post. But till then, I thought it would be a good idea to post my ideas on the blog as such.

  1. What motivated you to participate in the Youth parliament session “Educated India Enable India - Quality Education for All” ?

Being a student was more than enough to motivate me to attend this session because it’s when you are a part of the system, you not only see but feel the drawbacks of the system. Our education system suffers from a lot of issues like the lack of accessibility of the education to all, the low quality of teaching, or the persistent job oriented mentality of the society.

A dream, a vision of mine to bring about the required changes and reforms, not just on papers but in real life, it’s this thing that motivated me to participate in this session.

  1. Suggest the two most important steps according to you, need to be taken to take Indian Higher Education system to International standards.

First and foremost that I consider is to improve the quality of teaching, which is a must to make the process of learning enjoyable. Today, most of the teachers don’t feel accountable for the performance of their students. The reason is also quite clear, there is no incentive system to motivate the teachers to perform better.
This further leads us to a society whether there is no passion among the youth to pursue a career in teaching. Top performing countries in education across the globe recruit their teachers from top 5-10% of their best universities. But here if you can’t make anything out of your life, you become a teacher.
A change in this mentality has become the need of the time and it can be brought by implementing the incentive system, a new system design to recruit the teachers with the principal focus on quality, and to make the teaching more creative and less robotic, with less focus on a sequence of dull memorised steps and more focus on applications, reason and logic.

Second step that I would recommend is to provide education to the poor kids who are often neglected in this system or considered of very little importance, and yet they have shown time and again that they are equally brilliant as anyone who goes on to take the benefits of our “elite education system”. This poor India has to put up with very poor government schools in the deep interior. Majority of this poor India drops out of school before they get to the 10th grade. If our country could manage to provide them with the same level of education that we get, India would definitely not be at this state of development.  

  1. Propose a bill that you wish to present in the youth parliament.

My bill tries to bring something that almost most of our schools lack and that is encouraging creative and innovative thinking among its students.  I have named my bill “YOUTH ENTREPRENEURSHIP BILL
The bill proposes the integration of entrepreneurship in a creative way in our classrooms so that people can go on to pursue their dreams, to do what they really wanted to do in their life.
The bill provides the steps for the same-
  1. providing more active and vocational courses where education doesn’t look like a burden to them but rather they go on to actively participate even in their least favourite subjects. Taking the example of maths which unfortunately happen to be one of the least liked subject among the students, maths problems should be motivated not just through the sciences, but also through the arts: puzzles, toys, magic, poetry, music- these should all form a key part of the mathematics.
  2. a regular visit to different NGOs to see what all work they are doing and getting some inspiration from them, a visit to different villages to realize that life is not that good what it looks like and to see the facilities that these places lack from, a visit to towns like Firozabad to feel the drawbacks of the present system, and to encourage them to present their views and what all innovative ideas they do have to better such situations, and, motivating and helping them to even implement their ideas to whatever extent it is possible and providing them the thrust to look for even more such ideas and their effective implementations.

The reason for this bill goes on with the theme “Educated India, Enable India”. We do have the people who are educated but most of their education is job-oriented and never let them ponder over the issue of building an “Enable India”. This bill of mine inspires them to think of it, it lets them broaden their vision from merely getting a job to the point of joining hands with each other to develop a stronger, talented and developed India.

Friday, November 7, 2014

What do 5, 13 and 563 have in common?

Well, nowadays it seems like I am getting more interested in number theory with time. I picked this one at random from Numberphile and it felt good to have one more thing in your basket -- this time the wilson's prime and the wilson's theorem. Have a look at them!!