Advance Master Theorem

You can solve majority of questions using this method. It’s quoted in the famous book by “Narasimha Karumanchi”.

Form:
T(n) = aT(n/b) + θ(n^k (log^p n))

Constraints:
a>=1, b>1, k>=0 & p is a real number

Case 1:
if a>b^k then T(n) = θ(n^(log<b> a) )

Case 2:
if a=b^k {

if p>-1 then T(n) = θ(n^(log<b> a) log^(p+1) n)
if p= -1 then T(n) = θ(n^(log<b> a) loglogn)
if p< -1 then T(n) = θ(n^(log<b> a))

}

Case 3:
if a<b^k {

if p>=0 then T(n) = θ(n^k(log^p n))
if p<0 then T(n) = O(n^k)

}

Example:

T(n) = 3T(n/2) + n

Here a=3,b=2,k=1,p=0

Compare between 'a' and 'b^k'

a=3
b^k = 2^1 = 2
a>(b^k)
so case 1 satisfies. T(n) = n^(log<base 2> 3)

You can easily memorize it with practice. Just practice few problems you will easily be able to remember for a long period of time.

Recursion Vs Iteration

Recursion vs. Iteration


In simple words ‘recursion’ or ‘iteration’ means to repeat around until you find a stopping condition. So it’s obvious that if we don’t find any stopping condition then it will ultimately fall into an infinite loop. Both recursion and iteration are equivalent in power and hence inter-changeable or inter-convertible. That means for every recursive program there is an iterative approach & vice-versa.


Example Problem: Write a program to print ‘hello’ 3 times.


Recursive Approach:


void fun( int n){

if(fun==0) return;
else {
      printf(“hello”);
      fun(--n);
     }
}
int main(){
fun(3);
return 0;
}


Iterative Approach:


int main(){
int i=0;
while(i<3){
           printf(“hello”);
           i++;
          }
return 0;
}





You can also simply write ‘printf(“hello”); ’ 3 times inside main function (manual approach). You might think that why to use recursion or iteration then. Now if you are asked to print ‘hello’ 1000 times then…??? You can imagine now which approach would be better.


Important point to note:

1. Recursion, iteration & manual approach are equivalent in terms of power. You can write any program using any one of the approach and also convert them into other approaches without changing the meaning of the program.
2. All the recursive programs require an additional stack data structure for their execution.
3. Iterative programs may require additional storage space as per the convenience of the programmer.

Final Days Of Preparation

The countdown begins in the last 3 months. I was prepared for it. I deleted my facebook, whatsapp, clashofclans and all other such addictions. Trust me initially i felt like "what the hell i just did? i should revert back." But still i put all my will power into action and controlled myself. In few days i got used to it. Now i had more time, in boring time also i was thinking about a question or reading some interesting stuffs. These things matter a lot while your preparation.

I remember i started writing my full length on December 23rd, i just got 49.99 marks. It was test books demo full length test. I was happy indeed. Because i was sure that these mistakes are never gonna happen again. Slowly and steadily i started writing test series each single day without wasting time and analyzing my mistakes. Consistency matters !!! Gate exam will certainly test it, so be prepared. In the end i was calculating i had given around 41 full length tests including 3 CBT's. I had completed part test of rbr test series and testbooks test series but didn't get enough time to give subject wise test series. i had given full length of all institutes probably (madeeasy,ace,testbook,rbrtestseries,gateforum,virtualgate). I have learnt from each of the test series. As a student you should not compare between test series. Every test series has some really good questions and plenty of wrong questions. As a wiser person you just need to extract the cream and thrash the leftovers. I was getting around 60-70 on average, In few test series i got above 80. Test series matter a lot. It improves your time management skills and accuracy. DON'T EXPECT ANY QUESTION WILL BE REPEATING IN GATE. I would also advise not to give any test series just on the last day before exams.

On the last day i just revised few quick notes that i had prepared from my mistakes in test series and few concepts that required to be memorized like Frame formats in Computer networks etc...The in the evening i watched the movie MSD The Biopic. I had my dinner at 8pm and tried to sleep by 9. But due to excess anxiety i couldn't sleep till 2am. i woke up at 6am at morning the next day. It was bit cold so i decided not to take a bath. Because it might lead me into a running nose. Then after finishing other routine works, i left for the examination center with my elder brother. I was in full confidence. No doubt on myself. We reached there 45 mins ahead of time. Lot of my college mates were there but i decided not to talk with them. DON'T INDULGE IN ANY KIND OF TALKS WITH ANYONE JUST 1 HOUR BEFORE THE EXAMS !!!... Then finally i went inside at 8:40am (20mins before the start of exam). Immediately i checked my mouse,monitors, asked the invigilator if there was provision for extra rough sheets, went to the toilet, finally relaxed myself doing breathing exercises in the last few minutes. I had my strategy prepared (1mark technical,2mark technical then aptitude). DON'T CHANGE YOUR STRATEGY IN THE MIDDLE OF THE EXAM HOWEVER DIFFICULT THE SECTION MIGHT BE.

Few Important Tips:

1. Always carry a half used blue and red pen. Don't carry a new pen.
2. Looking at the rough sheet, figure out how effectively you are going to use it.
3. Fight till the last second of the exam, don't give up midway.
4.  Don't get carried away by glamors sitting right beside you.
5.  Finish it up in style...Just like MSD does....!!!

"Gate will test your intellectual skills, consistency, patience, ability to tackle pressure situations, time management, adaptation skills, speed and accuracy !!! Be prepared well in advance."

Initial Days Of Preparation

Now i was in the gate roller coaster ride. But still somewhere in the corner of my heart i had a fear of not getting selected in GATE.😩 So i tried placements of companies like teksystems & amazon. Again luckily i got rejected in both of them due to lack of preparation as obvious. So finally i decided that i will skip all placements as it was making me loose my self confidence. AVOID REPEATED FAILURES, TAKE BREAKS.

 It was a really tough decision for me. My parents were also confused like me. I seriously didn't think if the decision was right for me or not. I took the decision and convinced the soul me that i will prove that the decision was right, no worries. After that i never ever thought about placements nor about my decision. I had to bunk so soo sooo many classes as i had to complete my syllabus in time. I was studying for around 7-8 hours daily, consistently. No mercy on my body or mind.

 I completed the entire syllabus, making notes and all in just 3 and half months. From august 1st, i was answering questions in facebook groups. Explaining things properly, which really helped me clear my concepts a way more than it were previously. Everything matters in the end. If you can't explain a concept in simple words to a naive beginner then be sure that you never understood the concept properly. This will affect your confidence and hence performance in real GATE exam. Throughout my preparation one of my dearest friend Abhisek (The Panda) was there by my side. We had negotiated that we will discuss the concepts and won't let our conversations go into any kind of arguments to prove anyone right or wrong. If any question is bit ambiguous, we just skipped it without wasting and quarreling over it all day long.

 "If you ever wish to achieve something you never had, you have to do something that you have never done"

The Beginning

I was really passionate about all the subjects of computer science. But i didn't wish or ever thought of clearing GATE and doing my MTech in one of the prestigious IIT's.

In the month of January, i was working hard for GSOC (Google Summer Of Code). I had no prior experience in open source development at all. Thanks to my lovely friends (Lalu, Rishav, Ashutosh, Sandeep, Sai) for helping me out. So after 2 months of serious effort i was able to contribute to one of the organizations participating in GSOC. I was the top contributor among all the contestants out there. I had 3 fully merged contributions and 4 error reports. I was certain that i would be getting selected. But alas!!! On may 17th (just 2 days before my auspicious bday) results were out and luckily i wasn't selected. At the end of this post you will figure out why i said 'luckily'. After that i was seriously depressed. Because you know, how much that hurts if you have worked hard for it and someone else steals the show.

It took me 72 hours to convince myself that i  shouldn't give up and try something else. Thanks to my dearest friend Siddhart (brahmuna) who explained me the entire syllabus of gate in his 5 crore worth bungalow. He convinced me that i should go for gate instead of crying over split milk. I wasn't sure at first but i had to perform in some way or the other. The worst thing was that i had less time remaining for gate cs 2018, competitions were really high. The best thing was i had scored above 9cgpa in all the subjects that was mentioned in gate cs syllabus. So i had some optimistic speculations that whatever might be the situation, i will be in top 100 !!!

I purchased few books from flipkart and started my preparation from may 20th. But later i realized that reading from books was way too time consuming and i won't be able to finish up the syllabus in time. So i decided to join Ravindra Sir's lecture. It's bit costly but somehow i managed to convince my parents that i won't disappoint them this time for sure like JEE MAINS & ADVANCE. It all started from there on. I still remember the date, June 1st 2017, when my serious dedicated preparation had started.

"Never Give Up !!! Sometimes you think that god is cruel, but you are unaware that he has planned something way better than you have ever thought of . Life is all about experiences. The person who hasn't faced the darkest of nights, can never enjoy the tiny spark of light "