Saturday, August 11, 2012
Thursday, August 9, 2012
Count no of different places tommy can cover from home to school condition is one place can't be visited twice and after reaching school he can't proceed further.
Tommy reach school frm his home there are many places b/w their home and school connected by bidirectional paths u have to count no of different places he can cover from home to school condition is one place can't be visited twice and after reaching school he can't proceed further.
you have
given:-
Input
t
n m h s
m lines
Output:
count
t is number of test case
n is number of nodes,m id number of bidirectional path, h is home and s is school
m lines bidirectional path b/w nodes x and y.
out put count is number of different nodes he can go from school satisfying the condition.
Sample Input:
1
3 3 0 1
0 1
1 2
0 2
Sample Output:
3
Sunday, July 22, 2012
Given an integer n , you have to print all the ways in which n can be represented as sum of positive integers
#define ARR_SIZE 100
#include<stdio.h>
void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* The function prints all combinations of numbers 1, 2, ...n
that sum up to n. i is used in recursion keep track of index in arr[] where next
element is to be added. Initital value of i must be passed as 0 */
void printCompositions(int n,int m ,int i)
{
/* array must be static as we want to keep track
of values stored in arr[] using current calls of
printCompositions() in function call stack*/
static int arr[ARR_SIZE];
if (n == 0)
{
printArray(arr, i);
}
else if(n > 0)
{
int k;
for (k = 1; k <= m; k++)
{
arr[i]= k;
printCompositions(n-k,m, i+1);
}
}
}
/* Driver function to test above functions */
int main()
{
int n = 5;
printf("Differnt compositions formed by 1, 2 , 3 , 4 and 5 %d are\n", n);
printCompositions(n,n, 0);
getchar();
return 0;
}
Time Complexity O(n^m) Exponential
Space Complexity O(m)
Run Here http://ideone.com/clone/ETZTv
Thursday, July 12, 2012
find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately
Given a matrix of order M x N containing 1.s and 0's, you have to find the number of maximal squares that can be formed. A square is formed by grouping adjacent cells containing 1. A maximal square is one that is not completely contained within another square. Maximal squares that overlap partially are to be counted separately. Unit squares (length of side = 1) should be also counted.
Note that squares are filled, i.e. they cannot contain 0.s.
Number of maximal square: 6
Input specification:
The first line consists of integers M and N, the number of rows and columns of the matrix.
0 < M and N <=40
Next M lines contain N characters from the set {0, 1}.
Output specification:
An integer representing the number of maximal squares that can be formed followed by a newline.
Sample Input and Output:
Input:
4 5
11001
11110
11011
11001
Output:
9
Input:
2 2
10
11
Output:
3
Source: Heard From user Bhavesh
Friday, June 1, 2012
Know Your Indian Prime Man !!!!! , (Dr. Manindra Agarwal’s Journey to the Primality Testing)
I Found it one of the inspirable story i have ever read of any indian , So thought to share with all of you , Must read for all who really loves computer science , Yeah , Yeah , Hear you go guys !!!
It was December 2002 when suddenly a rumor spread around in the Computer Science students who had just passed out of IITK in May that year that two of their batch mates had completed their PhDs in a matter of few months. It took no time for the mails to be circulated, phone calls to be made, yahoo messengers to ring the message among the students who were either working or were furthering their studies. Two of their own batch mates, friends of many, had completed their PhD and that too How!
When few got the real scoop, the news was even more interesting than the completion of PhD. They had invented an algorithm to solve a huge problem in Mathematics. It had been an open problem for a long time. They had invented an algorithm to test if a number was prime or not. Given the computational ability of Computers, testing if a number is prime or not sounds like a mundane problem. But when the Prime numbers become bigger and bigger, the time taken to test the number for primality increases exponentially – literally!
Like if one was to test, say 5423. A small program can find this out in much less than a second. But what if one was to test 542354235423 was a prime? It would still be a little longer. What if one was to test – (5424)^5 + 1? It takes a long time, so much so that until the advent of Super Computers, there was a limit on the highest Prime Number known. But one may ask, why do you need to find out?
Finding out the largest prime number is not a huge challenge, but to reduce the amount of time taken to test if a number is prime or not, is something that has teased many mathematicians for a long time. As I said earlier, the time taken to test a number would rise exponentially as the number grew larger.
These famous folks had invented an algorithm which took much lesser time and more so as the numbers got bigger, the time did not increase exponentially. It increased in what is mathematically called Polynomial order.
As the rumor would have it – Neeraj Kayal & Nitin Saxena had completed their PhD, having solved this problem. Or more accurately Dr. Manindra Agarwal had agreed to grant them their PhDs, having solved such a remarkable problem.
So, Dr. Manindra Agarwal, Neeraj Kayal & Nitin Saxena had written a paper about their findings and it had instantly caused a storm in the international community.
It was special for all the people sitting in their corporate offices because in last six months they had realized that the intellectual challenges a job offered was not even in the same zone as this effort. Most of the graduates either take up a job or go to US for pursuing further studies. While these people had stuck around here in India to do their PhDs, working with Dr. Manindra Agarwal.
Truth be told, Dr. Manindra Agarwal had been struggling with this problem for a few years now.
Dr. Agarwal has also had a very interesting trajectory like his students Neeraj & Nitin. He graduated from IIT Kanpur in the year 1986. This was the time when there used to be a mass exodus of highly educated and very intelligent engineers or scientists to the rest of the world, read America. The news of various space crafts like Voyager/Challenger was a common news item and the fact that there were a bunch of engineers at NASA which were of Indian Origin, more specifically from IITs was also well known. One of the most common career paths for students graduating from IIT Kanpur was to take the GRE and land up in US to pursue Masters or a Phd.
The problem of brain drain was at such a high that in the same year, the then Prime Minister Mr. Rajiv Gandhi had launched a New Policy of Education. Indira Gandhi National Open University was also started in 1985. There was a new wave as far as educational reforms in India were concerned. It was in the year 1986 that the Indian population living abroad cried their hearts out listening to the song “Chitthi aayi hai, watan se chitthi aayi”. Not that the song could do much more, but crying helps.
Graduating from IIT Kanpur in 1986, Dr. Agarwal decided to stay on India and continue his Phd at IIT Kanpur. Now, he was neither a part of New Policy of Education, nor did he indulge in the sentiment of a Bollywood song but his reason for not going to US was that he could not muster enough courage to study for GRE.
He was an ace student. He had a CPI of 9.3, while the Institute average usually hovers around 7. His All Indian Rank was 38! And he was a Computer Science student. But he could not motivate himself to take the GRE. GRE is a much simpler exam than JEE and lacs of students, all over the world – especially from India – take it every year to go to USA for further studies. The exam involved mugging up virtually the whole English Dictionary. He did start the process but could never motivate himself enough to keep doing it. Thus one of the biggest factors in his staying in IIT Kanpur to continue his Phd was his inability to mug up the dictionary, consequently he did not take the GRE.
His not going to US and continuing to study at IIT K would have much larger implications in his life and around. He enrolled to do his research with Dr. Biswas in the Computer Science department at IIT Kanpur itself.
Not that that is what he wanted to do forever. There were many other tempting options like management, civil services and even other jobs. But, he had never had any inclination towards Management or Civil Services. Software industry had started functioning in its own accord. As far as software industry went, he had worked as an intern at a software firm. He had to implement Binary Tree as his assignment there – something which was far from challenging for an IIT Kanpur, Computer Science graduate. That gave him the idea that even a software job is not going to satisfy him – intellectually. So the only option that he had left for him was to pursue further studies and eventually get into research.
Coming from the background that he did, he did not face any music about making such choices. If at all, his parents were only happy that he had decided to stay back in India. Dr. Agarwal has an elder brother who is now settled in United States of America, and his brother has been almost guilty of making that choice. Similarly a distant relative had moved to US and the rest of the family did not necessarily look at it as a great achievement. This was remarkable because typically there is a lot of prize and prestige associated with a son living abroad.
Dr. Agarwal’s parents are retired teachers. His father taught Mathematics at Allahabad University and his mother taught Education there. His parents had never wanted their kids to go to the US – may be because they were from a small town – Allahabad. Allahabad, a small town from certain aspects, is otherwise a place of great importance. Allahabad also used to be a center of education until 90’s, not any more though. Allahabad is perhaps the most famous for Prayag – where the rivers Ganga, Jamuna & Saraswati come together. It is considered a great holy destination amongst Hindus.
They lived in a rather congested area called Khuldabad in Allahabad. And the people they dwelt with created no pressures on him to do anything he did not want to do. His childhood was like the childhood of any other North Indian kid – strewn with comics like Champak, Motu-Patlu, Chandamama, Nandan etc. However, he enjoyed mathematics even as a child. Living in the region in which they did, it did not offer him much opportunity for sports. Playing cricket in the lanes was where it ended. He read a lot even as a child – Enid Blyton being one of his early favorites. But he had had an early interest in Mathematics and he pretty much read any book about mathematics he could lay his hands on. However, he would never go and ask someone to get him some book or get a book from the library. He was a shy kid. He was also not particularly studious.
Looking at him one would never guess the activities he was fond of. A typical IIT grad has spent at least XI and XII just sitting on a table and chair – studying. JEE did not allow much room for entertainment. However, some of his favorite activities during those days were to bunk college regularly – go to movies (Amitabh Bachchan being his favorite. Incidentally Mr. Bachchan also hails from Allahabad), sit at a Chai shop and chat with friends, or once in a while visit a nearby girls’ college for some eye tonic. He remembers his benign ogling at girls with a mischievous grin on his face.
One would be surprised because with all this he secured 38th rank in the Joint Entrance Exam for IIT. He surprised many with this result because he studied in Government Inter College, not the best school by any stretch of imagination and there were other better schools like St. Joseph and Boy’s High School in town. He had heard from the friends of his friends that there were some very smart guys in St. Joseph’s Convent, which used to make him nervous. But the result laid his fears to rest and somewhere he felt that it was a fluke.
He continued his studies at IITK with the same indifference but like for many more people, it opened up a whole wide world to a boy, who grew up in a small town in UP. He spent a significant time smoking grass, listening to Pink Floyd and usually cramming up shortly before the exams. Pink Floyd would have never imagined, while they sat composing music in London, that their music would be appreciated so much in this technical Institute, in a small little village called Kalyanpur near a small town Kanpur in Uttar Pradesh. Like in the third of the third of the third world. Grass and Pink Floyd gave a lot of relief to people those days. However, unfortunately the trend was discontinued with US pressuring India to ban Grass. Those days Grass was sold at legal shops like some of those ‘Theka Desi Sharab’ selling local liquor.
Pink Floyd still continues to be so popular in IIT Kanpur and in most other IITs. Somehow people don’t listen to Beatles there, very few to Jethro Tull and then not much of Led Zepplin or other great musical trends but Pink Floyd. It is as if these small little institutes are holding a beacon in this part of the world as a fan following. Dr. Agarwal thinks that they have a certain Indian quality, not very definable, but some deeper connect.
Considering his interest in music, grass and fair bit of indifference to studies, it is funny that he did not have much to do with girls in his college days. IIT Kanpur boasted of one of the most open cultures in the country where boys and girls were permitted in each other’s hostels, without much restriction. He had a reputation.
Once in his third semester – second year, first semester – Dr. Agarwal and some of his friends were busy preparing for their mid-term exams while they lived in the E-Mid wing in Hall 2.
Hostels in IITK are called Halls and each floor in a block is called a wing. So say E Block would have a E-Bot (1st floor), E-mid (2nd Floor) & E-Top (3rd Floor). There are no Ground Floors in IIT Kanpur – they did away with their colonial past!
Now that wing faces the tennis courts. While these guys were busy cramming and getting frustrated, their frustration was fuelled by some M. Tech students playing tennis in the courts, with their girl friends cheering them from the sides. Instantly a bet of 20 rupees was set in their wing – the challenge was to go around the tennis courts in nothing but an underpant. Dr. Agarwal, who was so shy that he would never ask someone to get him a book, thought of this as an interesting proposition. He along with a fellow accomplice went around the court in their underpants.
IITians get more than a fare share of stories of their eccentricities but this one is truly unique. Well the tennis fan-fare stopped then and there. Later that evening the whole girls’ hostel, on the provocation of the gentlemen, landed up outside Hall 2 and demanded the culprits. But IITian males are known to demonstrate unsalable unity against females.
Finally, the issue landed in bureaucratic files, from where even demons don’t emerge.
Dr. Agarwal considers his undergraduate time as a waste of time in which he learnt nothing. And he credits his CPI to having an excellent short-term memory. He would cram up the things just before the exams and then forget all of it very soon. He regrets it.
However, he did graduate with a sense of what he liked and disliked, which is a great achievement because most of us land up living our lives without even wondering about what we really like. Leave aside, one, knowing what one likes and two, acting on it.
And act he did.
After joining under Dr. Biswas as a Phd Student he did get serious about studies and explored not just mathematics. He read up a whole lot of stuff including the Classical Indian Philosophy – Yoga Sutra, Brahma Sutra etc. Now he would hang around with a different set of people. He had now become serious and not just about his vocation – mathematics. He graduated with a Phd in the year 1991.
A lot transpired between 1991 and 1998 – he continued as a research scholar at IIT Kanpur till 93, became a Fellow at School of Mathematics, Madras until 95, Humboldt Fellow in Germany till 96, joined back at IIT Kanpur as an assistant professor in 1996.
It was in the year 1998 when he along with Dr. Biswas, who had also been his Doctoral Advisor, came across an interesting technique for Polynomial Identity Testing. Until then, most of the approaches had used random numbers to do the testing. In this paper that they found, the author used irrational numbers to evaluate an expression, which gave significantly better results. The probability of the result improved with the lesser approximations taken for irrational numbers. However, the problem of Polynomial Identity Testing still remained non-deterministic. But this gave an idea to Dr. Agarwal that he could use this approach to solve some other problem in the field of Complexity Theory, his area of specialization.
In the search of a problem to apply this solution to, he chanced upon the Primality Testing. And it became a haunting problem, as it did not lend itself to his efforts. He felt inside that if increasing the approximation improves the result at some point the problem would become deterministic.
He kept on working on this problem, while the rest of the life continued – classes, home, students and the whole works. About two years later, in 2000, with the help of a student he could prove his approach to be true for numbers as large as 10^9.
It was in the year 2001 that Neeraj & Nitin joined him for their B. Tech project -their final year of undergraduate studies. B. Tech project another perfunctory exercise for most but critical for a very select few. You choose. They worked with Dr. Agarwal till the end of their time, May 2002. And they were staying at the campus for the summers, So Dr. Agarwal also decided to stay and they continued working on this problem.
Actually Nitin and Neeraj had both applied for Phds outside of IIT Kanpur. Nitin wanted to travel to the land of milk and honey and Neeraj to TIFR, but since Nitin did not get through anywhere he decided to continue with Dr. Agarwal. And since Nitin decided to continue, Neeraj also stayed on. They continued working on various aspects of the problem and they did find some interesting results but it never came to the point where it would hold true deterministically.
It was one morning in July 2002 that things suddenly came together – a bunch of facts they had discovered were floating around. Each of these observations were very simple in themselves but they suddenly came together to solve this problem. Dr. Agarwal called on his students to verify the results, which they did in a few days. They had finally found a solution to test if a number was a prime whose running time was a polynomial over the number of digits. He was very relieved to have solved this problem, a monkey he had been carrying on his back for about 4 years.
None of them had the slightest clue about how important a result this was and what consequence this would have. The News became public in Nov-Dec 2002. The awards have not stopped pouring ever since, including some of the most prestigious awards – The Clay Research Award, Delbert Ray Fulkerson Prize, G¨odel Prize along with other and other honorary awards like the Distinguished Alumnus Award at IIT Kanpur.
It is remarkable how few things happen and a lot others don’t. Now had he been able to cram words for GRE, or had his parents wanted him to go to the US or to the Civil Services, had he decided to pursue a more lucrative corporate career or had he not come across that paper in 1998. This story would not have been told.
The Clay Research Institute has seven unsolved problems, for which there is a combined prize of 7 million USD, a million a piece. The problem consist of Reimann Hypothesis, Poincare Conjecture, Hodge Conjecture, Swinnerton-Dyer Conjecture, Solution of the Navier Stokes Theorem, Solution of Yang-Mills theory, and determination of whether NP-Problems are actually P-Problems.
Now who is smoking pot and roaming around the tennis court in his underpants?
I am Lost For Words as far as Dr. Agarwal’s story of Learning To Fly is concerned. We don’t need no Brain Drain, we need Brain Damage.
When few got the real scoop, the news was even more interesting than the completion of PhD. They had invented an algorithm to solve a huge problem in Mathematics. It had been an open problem for a long time. They had invented an algorithm to test if a number was prime or not. Given the computational ability of Computers, testing if a number is prime or not sounds like a mundane problem. But when the Prime numbers become bigger and bigger, the time taken to test the number for primality increases exponentially – literally!
Like if one was to test, say 5423. A small program can find this out in much less than a second. But what if one was to test 542354235423 was a prime? It would still be a little longer. What if one was to test – (5424)^5 + 1? It takes a long time, so much so that until the advent of Super Computers, there was a limit on the highest Prime Number known. But one may ask, why do you need to find out?
Finding out the largest prime number is not a huge challenge, but to reduce the amount of time taken to test if a number is prime or not, is something that has teased many mathematicians for a long time. As I said earlier, the time taken to test a number would rise exponentially as the number grew larger.
These famous folks had invented an algorithm which took much lesser time and more so as the numbers got bigger, the time did not increase exponentially. It increased in what is mathematically called Polynomial order.
As the rumor would have it – Neeraj Kayal & Nitin Saxena had completed their PhD, having solved this problem. Or more accurately Dr. Manindra Agarwal had agreed to grant them their PhDs, having solved such a remarkable problem.
So, Dr. Manindra Agarwal, Neeraj Kayal & Nitin Saxena had written a paper about their findings and it had instantly caused a storm in the international community.
It was special for all the people sitting in their corporate offices because in last six months they had realized that the intellectual challenges a job offered was not even in the same zone as this effort. Most of the graduates either take up a job or go to US for pursuing further studies. While these people had stuck around here in India to do their PhDs, working with Dr. Manindra Agarwal.
Truth be told, Dr. Manindra Agarwal had been struggling with this problem for a few years now.
Dr. Agarwal has also had a very interesting trajectory like his students Neeraj & Nitin. He graduated from IIT Kanpur in the year 1986. This was the time when there used to be a mass exodus of highly educated and very intelligent engineers or scientists to the rest of the world, read America. The news of various space crafts like Voyager/Challenger was a common news item and the fact that there were a bunch of engineers at NASA which were of Indian Origin, more specifically from IITs was also well known. One of the most common career paths for students graduating from IIT Kanpur was to take the GRE and land up in US to pursue Masters or a Phd.
The problem of brain drain was at such a high that in the same year, the then Prime Minister Mr. Rajiv Gandhi had launched a New Policy of Education. Indira Gandhi National Open University was also started in 1985. There was a new wave as far as educational reforms in India were concerned. It was in the year 1986 that the Indian population living abroad cried their hearts out listening to the song “Chitthi aayi hai, watan se chitthi aayi”. Not that the song could do much more, but crying helps.
Graduating from IIT Kanpur in 1986, Dr. Agarwal decided to stay on India and continue his Phd at IIT Kanpur. Now, he was neither a part of New Policy of Education, nor did he indulge in the sentiment of a Bollywood song but his reason for not going to US was that he could not muster enough courage to study for GRE.
He was an ace student. He had a CPI of 9.3, while the Institute average usually hovers around 7. His All Indian Rank was 38! And he was a Computer Science student. But he could not motivate himself to take the GRE. GRE is a much simpler exam than JEE and lacs of students, all over the world – especially from India – take it every year to go to USA for further studies. The exam involved mugging up virtually the whole English Dictionary. He did start the process but could never motivate himself enough to keep doing it. Thus one of the biggest factors in his staying in IIT Kanpur to continue his Phd was his inability to mug up the dictionary, consequently he did not take the GRE.
His not going to US and continuing to study at IIT K would have much larger implications in his life and around. He enrolled to do his research with Dr. Biswas in the Computer Science department at IIT Kanpur itself.
Not that that is what he wanted to do forever. There were many other tempting options like management, civil services and even other jobs. But, he had never had any inclination towards Management or Civil Services. Software industry had started functioning in its own accord. As far as software industry went, he had worked as an intern at a software firm. He had to implement Binary Tree as his assignment there – something which was far from challenging for an IIT Kanpur, Computer Science graduate. That gave him the idea that even a software job is not going to satisfy him – intellectually. So the only option that he had left for him was to pursue further studies and eventually get into research.
Coming from the background that he did, he did not face any music about making such choices. If at all, his parents were only happy that he had decided to stay back in India. Dr. Agarwal has an elder brother who is now settled in United States of America, and his brother has been almost guilty of making that choice. Similarly a distant relative had moved to US and the rest of the family did not necessarily look at it as a great achievement. This was remarkable because typically there is a lot of prize and prestige associated with a son living abroad.
Dr. Agarwal’s parents are retired teachers. His father taught Mathematics at Allahabad University and his mother taught Education there. His parents had never wanted their kids to go to the US – may be because they were from a small town – Allahabad. Allahabad, a small town from certain aspects, is otherwise a place of great importance. Allahabad also used to be a center of education until 90’s, not any more though. Allahabad is perhaps the most famous for Prayag – where the rivers Ganga, Jamuna & Saraswati come together. It is considered a great holy destination amongst Hindus.
They lived in a rather congested area called Khuldabad in Allahabad. And the people they dwelt with created no pressures on him to do anything he did not want to do. His childhood was like the childhood of any other North Indian kid – strewn with comics like Champak, Motu-Patlu, Chandamama, Nandan etc. However, he enjoyed mathematics even as a child. Living in the region in which they did, it did not offer him much opportunity for sports. Playing cricket in the lanes was where it ended. He read a lot even as a child – Enid Blyton being one of his early favorites. But he had had an early interest in Mathematics and he pretty much read any book about mathematics he could lay his hands on. However, he would never go and ask someone to get him some book or get a book from the library. He was a shy kid. He was also not particularly studious.
Looking at him one would never guess the activities he was fond of. A typical IIT grad has spent at least XI and XII just sitting on a table and chair – studying. JEE did not allow much room for entertainment. However, some of his favorite activities during those days were to bunk college regularly – go to movies (Amitabh Bachchan being his favorite. Incidentally Mr. Bachchan also hails from Allahabad), sit at a Chai shop and chat with friends, or once in a while visit a nearby girls’ college for some eye tonic. He remembers his benign ogling at girls with a mischievous grin on his face.
One would be surprised because with all this he secured 38th rank in the Joint Entrance Exam for IIT. He surprised many with this result because he studied in Government Inter College, not the best school by any stretch of imagination and there were other better schools like St. Joseph and Boy’s High School in town. He had heard from the friends of his friends that there were some very smart guys in St. Joseph’s Convent, which used to make him nervous. But the result laid his fears to rest and somewhere he felt that it was a fluke.
He continued his studies at IITK with the same indifference but like for many more people, it opened up a whole wide world to a boy, who grew up in a small town in UP. He spent a significant time smoking grass, listening to Pink Floyd and usually cramming up shortly before the exams. Pink Floyd would have never imagined, while they sat composing music in London, that their music would be appreciated so much in this technical Institute, in a small little village called Kalyanpur near a small town Kanpur in Uttar Pradesh. Like in the third of the third of the third world. Grass and Pink Floyd gave a lot of relief to people those days. However, unfortunately the trend was discontinued with US pressuring India to ban Grass. Those days Grass was sold at legal shops like some of those ‘Theka Desi Sharab’ selling local liquor.
Pink Floyd still continues to be so popular in IIT Kanpur and in most other IITs. Somehow people don’t listen to Beatles there, very few to Jethro Tull and then not much of Led Zepplin or other great musical trends but Pink Floyd. It is as if these small little institutes are holding a beacon in this part of the world as a fan following. Dr. Agarwal thinks that they have a certain Indian quality, not very definable, but some deeper connect.
Considering his interest in music, grass and fair bit of indifference to studies, it is funny that he did not have much to do with girls in his college days. IIT Kanpur boasted of one of the most open cultures in the country where boys and girls were permitted in each other’s hostels, without much restriction. He had a reputation.
Once in his third semester – second year, first semester – Dr. Agarwal and some of his friends were busy preparing for their mid-term exams while they lived in the E-Mid wing in Hall 2.
Hostels in IITK are called Halls and each floor in a block is called a wing. So say E Block would have a E-Bot (1st floor), E-mid (2nd Floor) & E-Top (3rd Floor). There are no Ground Floors in IIT Kanpur – they did away with their colonial past!
Now that wing faces the tennis courts. While these guys were busy cramming and getting frustrated, their frustration was fuelled by some M. Tech students playing tennis in the courts, with their girl friends cheering them from the sides. Instantly a bet of 20 rupees was set in their wing – the challenge was to go around the tennis courts in nothing but an underpant. Dr. Agarwal, who was so shy that he would never ask someone to get him a book, thought of this as an interesting proposition. He along with a fellow accomplice went around the court in their underpants.
IITians get more than a fare share of stories of their eccentricities but this one is truly unique. Well the tennis fan-fare stopped then and there. Later that evening the whole girls’ hostel, on the provocation of the gentlemen, landed up outside Hall 2 and demanded the culprits. But IITian males are known to demonstrate unsalable unity against females.
Finally, the issue landed in bureaucratic files, from where even demons don’t emerge.
Dr. Agarwal considers his undergraduate time as a waste of time in which he learnt nothing. And he credits his CPI to having an excellent short-term memory. He would cram up the things just before the exams and then forget all of it very soon. He regrets it.
However, he did graduate with a sense of what he liked and disliked, which is a great achievement because most of us land up living our lives without even wondering about what we really like. Leave aside, one, knowing what one likes and two, acting on it.
And act he did.
After joining under Dr. Biswas as a Phd Student he did get serious about studies and explored not just mathematics. He read up a whole lot of stuff including the Classical Indian Philosophy – Yoga Sutra, Brahma Sutra etc. Now he would hang around with a different set of people. He had now become serious and not just about his vocation – mathematics. He graduated with a Phd in the year 1991.
A lot transpired between 1991 and 1998 – he continued as a research scholar at IIT Kanpur till 93, became a Fellow at School of Mathematics, Madras until 95, Humboldt Fellow in Germany till 96, joined back at IIT Kanpur as an assistant professor in 1996.
It was in the year 1998 when he along with Dr. Biswas, who had also been his Doctoral Advisor, came across an interesting technique for Polynomial Identity Testing. Until then, most of the approaches had used random numbers to do the testing. In this paper that they found, the author used irrational numbers to evaluate an expression, which gave significantly better results. The probability of the result improved with the lesser approximations taken for irrational numbers. However, the problem of Polynomial Identity Testing still remained non-deterministic. But this gave an idea to Dr. Agarwal that he could use this approach to solve some other problem in the field of Complexity Theory, his area of specialization.
In the search of a problem to apply this solution to, he chanced upon the Primality Testing. And it became a haunting problem, as it did not lend itself to his efforts. He felt inside that if increasing the approximation improves the result at some point the problem would become deterministic.
He kept on working on this problem, while the rest of the life continued – classes, home, students and the whole works. About two years later, in 2000, with the help of a student he could prove his approach to be true for numbers as large as 10^9.
It was in the year 2001 that Neeraj & Nitin joined him for their B. Tech project -their final year of undergraduate studies. B. Tech project another perfunctory exercise for most but critical for a very select few. You choose. They worked with Dr. Agarwal till the end of their time, May 2002. And they were staying at the campus for the summers, So Dr. Agarwal also decided to stay and they continued working on this problem.
Actually Nitin and Neeraj had both applied for Phds outside of IIT Kanpur. Nitin wanted to travel to the land of milk and honey and Neeraj to TIFR, but since Nitin did not get through anywhere he decided to continue with Dr. Agarwal. And since Nitin decided to continue, Neeraj also stayed on. They continued working on various aspects of the problem and they did find some interesting results but it never came to the point where it would hold true deterministically.
It was one morning in July 2002 that things suddenly came together – a bunch of facts they had discovered were floating around. Each of these observations were very simple in themselves but they suddenly came together to solve this problem. Dr. Agarwal called on his students to verify the results, which they did in a few days. They had finally found a solution to test if a number was a prime whose running time was a polynomial over the number of digits. He was very relieved to have solved this problem, a monkey he had been carrying on his back for about 4 years.
None of them had the slightest clue about how important a result this was and what consequence this would have. The News became public in Nov-Dec 2002. The awards have not stopped pouring ever since, including some of the most prestigious awards – The Clay Research Award, Delbert Ray Fulkerson Prize, G¨odel Prize along with other and other honorary awards like the Distinguished Alumnus Award at IIT Kanpur.
It is remarkable how few things happen and a lot others don’t. Now had he been able to cram words for GRE, or had his parents wanted him to go to the US or to the Civil Services, had he decided to pursue a more lucrative corporate career or had he not come across that paper in 1998. This story would not have been told.
The Clay Research Institute has seven unsolved problems, for which there is a combined prize of 7 million USD, a million a piece. The problem consist of Reimann Hypothesis, Poincare Conjecture, Hodge Conjecture, Swinnerton-Dyer Conjecture, Solution of the Navier Stokes Theorem, Solution of Yang-Mills theory, and determination of whether NP-Problems are actually P-Problems.
Now who is smoking pot and roaming around the tennis court in his underpants?
I am Lost For Words as far as Dr. Agarwal’s story of Learning To Fly is concerned. We don’t need no Brain Drain, we need Brain Damage.
Source: http://gpwrite.wordpress.com/2012/06/01/cracking-the-primes/
Thursday, May 24, 2012
Wednesday, May 23, 2012
Saturday, May 19, 2012
Power Tower Problem-
Given two power towers, find out which one is larger. Power tower is a number of the form : a1 ^ ( a2 ^ (a3 ^ (.... ^an)
You can assume that N <= 100, and each ai <= 100.
I don't have any efficient solution yet.
Source:
A sub-task in ICPC world finals 2012
You can assume that N <= 100, and each ai <= 100.
I don't have any efficient solution yet.
Source:
A sub-task in ICPC world finals 2012
Friday, May 4, 2012
determine whether the given string is of form pZq where q is reverse of q. p and q can contain only X and Y.
like if p=XXYX then z will be XYXX
for ex XXYXXXYXX is valid
the constraints is that "you can read only the next character at each point" .
for ex XXYXXXYXX is valid
the constraints is that "you can read only the next character at each point" .
Subscribe to:
Posts
(
Atom
)
