CS Rage - A trilogy of 7

Author's Note : For those of you who are wondering about trilogy of 7 part, the title is a reference to  Hitchhiker's Guide to Galaxy.

This is a post I have been thinking of writing for quite sometime. I didn't write in insti because I was afraid that some prof might find it (because of Gholap), and get pissed. Now that I'm officially a graduate from IITM (got a degree and all), I think it's safe to post all these comics now. (For those who don't know, CS Rage were a series of comics that some of us in our class made during our third year.) All the comics are based on true stories.

So here we go :

CS Rage 1
Creator : Devesh Yamparala (CR takes the first step)

CS Rage 2 
Creator : Devesh Yamparala
This one is about our friend Qiao from China.

CS Rage 3
Creator : Nitin Motiani (This is where I take this sacred responsibility)
This one is dedicated to all of us who took self study course Computer Vision and then spent a sem contemplating our life choices.

CS Rage 4
Creator : Saheel Ram Godhane (aka Flodi aka SRG aka God aka le shady character)
The shady character joins the party and gives description of Godliness of Boss, Bonnerjee, and Gundu Gunaa (aka Gilma Gunaa). 

CS Rage 5
Creator : Saheel Ram Godhane
This one is awesome because it features me.

CS Rage 6
Creator : Nitin Motiani (Back to the party I am)
About Software Engineering Lab 

Cs Rage 7 (contd. from CS Rage 6)
Creator : Nitin Motiani
Le Gurupi (aka GuruPeace) is the biggest traitor alive.

Bonus Feature (Unpublished)
Creator : Devesh Yamparala
This one is about our great Viki Mama (aka Shady Mama) who has one full series of Mama Comics dedicated to him. This was created sometime between Rage 4 and 5, but was never published.

                                                             The End

Goodbye Dear IITM

I suppose in the end, the whole of life becomes an act of letting go, but what always hurts the most is not taking a moment to say goodbye.

Here I sit for the last time in my lovely messy room hoping that time would stop. I dread the moment approaching. My last moment as a student of IITM, my last moment as a resident of Alak. I wish that I could somehow go back and live the last four years again. I wish for a Groundhog '4 years'. But I know that's not gonna happen. So I wait here for the inevitable. I am ready for it. I am prepared. I know where my towel is (For those unfamiliar with H2G2, http://en.wikipedia.org/wiki/The_Hitchhiker%27s_Guide_to_the_Galaxy).

I remember the day when counseling results came out; the worried looks my parents had about the idea of sending me so far from home. I can't help but let my mind drift off to my first day here. It was 2nd August, 2009. I was scared of being away from family, of having to live with completely new people, of living in a place where people didn't speak Hindi. I was scared of this gigantic place with a series of scary buildings, of super smart people, of starting a new life. At the same time I also remember the feeling I had when I got my ID card, or when I listened to some of the seniors profs speaking. It was a feeling of ecstasy and enthusiasm which you get when a big dream comes true. I remember the butterflies in my stomach. Looking back at those days I realize back then I was a boy trying hard to be a man. Today when I am leaving this place, I am a man who wants to be a boy again.

I look around my room and take a stroll through memory lane. The memories of night-outs during exams, of movie (or TV) marathons, or bullshitting sessions with friends come to my mind. I feel the joy thinking about the happy memories like placement, or getting facebook internship, or playing wolf in the wing. I feel the sorrow when I recall the sad incidents like losing a friend. I think of all that I have learned here, of all that I have done. Then my mind invariably goes to the things I could have done, I should have done. I feel the regret over wasting time one more time. But as usual it goes away when I think of my friends and all the great times we had here together.

My mind drifts to the memories of the people I met here. My old roommates Jusi and Ram (these two are credited with taking away my fear of living with strangers), my neighbors of 3 years Prateek(Golu), Vijay and Saheelram, of close friends like Vaibhav, Gholap, Gundu Gunaa, Ashu, Bonerjee, Boss, GuruPi, Pradeep, Viki Mama, Yemperor, Anuja, Deva, Tiru, and Akash. I relive the late night assignment fights in DCF, playing wolf in Alak, numerous department treats, making plans with Vaibhav to kill Akash, Gholap's killer PJs, all the trippings on dear Viki Mama (and obviously Mama comics), putting fight with Jusi in library during our first year, Jusi and I trying to wake up Ram to let us enter our room at 4am, GuruPi's inner peace, Gunaa making scrambled eggs for rest of us in US, the mysteries about Saheelram, and many more such memories. They all come at me in a wave, and I feel the void which leaving insti is gonna leave in my heart. Never before had I met such a diverse set of people who were all awesome and brilliant in their own way. Getting to know these people is probably the best thing that has happened to me till now. Without them my stay at IIT would not have been half as memorable. I hope that I can be in touch with all of them for years to come, and we can put same amount of fart whenever we see each other again.

And now when I look at the future, it scares me the same way IIT scared me four years ago. I am afraid to let go of my lovely insti. A part of me wants to stay here forever. But I know that's not logical. Life must go on. So with heavy heart I am leaving today. Leaving for the real world. Going away from my 'home away from home'. It scares the shit out of me but I hope that with the lessons I learned here I will be able to make it outside too somehow.

So here I am, ready to leave in half an hour and most of my friends have already left. But soon a new batch will come, again full of scared 18 year old boys/girls trying to find their place in the world, looking around this beautiful campus with dreamy eyes. Soon this institute's legacy and history will be under their care. I hope they will have as much fun as we did. Hopefully not make the same mistakes. Maybe make a few new ones. They will fall and rise just like all of us, and hopefully one day leave this place with as much love as I am doing today. To them I say "May the force be with you." (Sorry, geeky habits. Couldn't resist).

My Placement Experience

It's been a long time since I last posted here. A lot has happened during this time. The hectic end to 6th sem, my Summer Internship at Facebook (I had to mention this at least once :P), the whole 7th sem; but as always, I was too lazy to write about anything. I've wanted to write something for long, but why write when I can waste time watching a TV show?

Now since I'm finally done with the 7th sem and have too much time to spare (at least for a few days), I decided to come back here. I can't get all the credit though. I got inspiration from Sujeet and SRG, who both have written about their placement experiences. I saw this as a good opportunity to get back in the game, and also to (hopefully) get more views on my blog ;-)

Background Information
There is a good chance that some of you would've left this page after the first paragraph. So, I have to make sure that the rest of the brave souls who stayed, don't leave too. Hence, some info on what all offers I got during placements.

Some of you might already know that I'm a student in Computer Science and Engineering department of IIT Madras. On day 1 of placements, I got following 4 offers:

1. Goldman Sachs

2. Samsung R&D (US & South Korea)

3. Samsung India Software Operations

4. Samsung India Electronics

Well, that's a lot of Samsung. I ended up choosing Goldman Sachs over all Samsung profiles including the one with the highest paying job in IITM(probably in all IITs, I'm not sure).
So, here is the story of placements.

Before Placements
I applied to a lot of companies(Around 20) mostly core companies like Adobe, Microsoft, Linkedin, Amazon, Yahoo etc. along with big finance companies like Morgan Stanley and Goldman Sachs. A lot of my friends said that for a CS 9 pointer, I was applying to too many companies, but I just believed in what Spock said "It was logical to cultivate multiple options". I will be lying if I say that I wasn't scared of screwing up in all the interviews. There were times when I screwed up placement tests, and feared that I might not get any job in first 4 days. Since I had not written CAT or GRE, I had no back-up. I started thinking that I should have applied to even more companies, even those which I didn't really find interesting.

During all these tests, I realized that I needed to revise topics like OS, Compilers, and Networks. I wasn't super confident in Data Structures and Algos either, but my practice on SPOJ had made me somehow confident in those.

Week before Placements
During Endsems week, I had lots of breaks between the exams. I guess I should've utilized that time by doing some revision. That was actually my original plan. But, I ended up watching 6-7 movies. I re-watched the whole Lord of The Rings series. Even after Endsems, I had to follow the great tradition of Computer Science Department where you have to finish assignments after Endsems(Unless you are MVK, who finishes everything at least a week before deadlines). So, next 3 days went in finishing assignments and writing placement tests. 2 days before placements, Flipkart conducted a test. Out of the 2 coding questions, I couldn't solve even one. That was a big blow to my confidence. I decided to put as much effort as possible on the last night. But, I was so tired that I just slept off early and decided to get up early and read something.

The Day (December 1st)
Interviews were supposed to start at 7am. I had somehow managed to qualify for Google, Samsung(3 profiles), Goldman Sachs, and Directi. I decided to get up at around 4, and revise. But as it always happens with a lazy fellow like me, I couldn't. Before leaving, I just had 20 minutes to revise, during which I chose to read up on hash tables.

I was nervous, yes. I was worried at my insufficient knowledge of some topics. But strangely, I was not scared anymore. My father always asks me to think about "what is the worst that can happen?" in tensed situations like this. So, that's what I did. The worst that could happen was that I wouldn't get a job on day 1. I guess that should be a scary thought, but for me it was a bit of relief. I got into my "Jo hoga dekha jaayega" mode.

Morning Session
The big day started with Google interviews. I had 2 back to back interviews. I felt I screwed up one, and did okayish in the other. Bad start. Then came Goldman Sachs, and Samsung US. After 2 interviews with Samsung and 5 interviews with GS, I was 80% sure that I was going to get selected for both. I started wishing that these two companies declare their results soon, so that I can go and sleep. Little did I know that they were not allowed to announce their results before 10pm. Since I had already had 9 interviews, I had no enthu to sit for another. But I had to sit through all the interviews in the afternoon session also. :(

Special thanks to all the placement coordinators at that time. They were really helpful and encouraging. Google's second interview took up my GS interview slot. The Samsung interview was scheduled in the next slot, but GS people were also calling me to come for that interview. At that time, the placement coordinators really helped me manage the situation. They ensured that I could sit for both the interviews without any trouble.  

Afternoon Session
Afternoon session started with Microsoft test from which they were going to select people for interviews. During that test only, I got calls for Directi and Samsung interviews. This was gonna be a painful session. After 3 more interviews for 2 profiles of Samsung India, I found out that I didn't get through for MS interview. I didn't know whether to feel disappointed or relieved. By 6:30, I was done with all the interviews except Directi. I was hoping to get done with it quickly. I was daydreaming about food and sleep. But, 2 Directi interviews lasted for 3 hours, and I was stuck in the interviews hungry and sleepy. Finally at 10pm, it was over. I had survived through 14 interviews in one day.

Result Time
After all this fight, I wanted to know the results as soon as possible. So, instead of waiting for results to come on placement website, my friend Sagar and I went to placement office to find out results as soon as possible. And yay, I got offers from Goldman Sachs, and all 3 Samsung profiles.

It was pretty awesome to see that so many of my friends had got great job offers. Almost everyone in class was placed on day 1. 6 guys were placed from my hostel wing that day.

Moral(s) of the story 
1. Have confidence in what you know. There were a lot of things I didn't know. I hadn't really prepared properly. I am not encouraging anyone to go unprepared or partially prepared like me. What I want to say is that having confidence in whatever you know, does help a lot.

2. Don't let bad performance in one interview affect the other.

3. Having so many interviews in such a short period, means there will be conflicts in timings. Naturally, you will be late for some of the interviews. But, make sure that you are not too late for any of the interviews. If you are late by say 2 hours, your chances will be pretty bad. It's like designing a good Scheduling Policy.

4. If you don't know something, ask for a hint or something. Don't try to fake your way through it. Particularly, if the question is about some core CS concept or about finding a good algorithm. I personally don't like the HR type interviews where you have to sell yourselves. It's not that I'm bad at those(actually it turned out that I'm pretty good at those), but it's easier to put fart there. They obviously won't buy everything, but you can still do a decent job of faking knowledge there. At the other hand, if the interviews check your knowledge of Algorithms and other core concepts, it is very difficult to fake it.

5. Most importantly, having good friends help a lot. There were times during this sem when I was low in confidence, when I was scared. At those times, good friends like Prateek, Vaibhav, MVK, Saheel, Ashu etc (can't type all the names, so 'etc') were a great help. Although they basically accused me of being over-dramatic (Saale sab kamine hain :P), it was really great to see so many people believing that I could do well.

6. Placements are not end of life. Enough Said.

P.S. : This post is a blatant attempt to get more hits on this blog. :-P

CS Rage 3

Dedicated to Computer Vision Victims of our class.
Context : Exams for self-study course Computer Vision.

For the uninitiated : 

CS Rage 1

CS Rage 2

Idea Courtesy : Vijay (MVK)

P.S. :- Those of you who don't know who SRG is, the hint is 'He is to our class what SRT is to Cricket'.

The Human Hero

"If I have to put anyone to bat for my life, it’ll be Kallis or Dravid". - Brian Lara

      It was summer of 2006. A 15 year old boy was in hospital. He couldn't watch the last test of India-West Indies test series there. First 3 matches had been draw. And last match was on uneven pitch of Jamaica. If India could win this match, it would be their first series victory on West Indian soil after 1971.

      The fact that Chris Gayle made a pair on his home ground is good enough to give us a picture of the pitch. It was late in a night that boy was listening to commentary, when that historical moment came. India won a test series in West Indies after 35 years, second time only in the history. For a few minutes he forgot everything about health. For some time every Indian forgot about all their problems. That victory gave that boy the strength to fight his illness.

      Rahul Dravid's career is full of such inspiring moments. Whether it is his hundred at Headingley, or his partnerships with VVS Laxman in Kolkata and Adelaide, or his fifties in Jamaica. Rahul Dravid is not God. He was never a God. He didn't have the perfection of Tendulkar or Stroke Play of Lara. He has always been a Human. And a great one.

      Where is the fun in being God? They have it easy (generally, I think). The best thing about being a human is the struggle and challenge that is the part of our very existance. And that is where Rahul Dravid teaches us the most important lesson. It's more than cricket. It's about anything we do in our life. We all have our limitations, but with a fighting attitude, we can overcome them. Thanx to Rahul Dravid for this important lesson.

      For most of his career he was overshadowed by others. His 95 on his debut at Lords was overshadowed by Ganguly's hundred. His 180 at Eden Gardens overshadowed by Laxman's 281. For most of his career his contribution to the team was overshadowed by more pleasing and attractive game of others. But he was a complete gentleman. Such small stuff never affected his personality, or his game.


"Rahul Dravid is a player who would walk on broken glass if his team asks him to" - Navjot Singh Sidhu


      An ideal selfless team player he was. He opened in test cricket when team needed him to. He took role of wicket-keeper when team needed him to do that. He was considered unfit for ODIs, the man has more than 10,000 runs in the shorter format of the game. He holds record for second fastest fifty in one-dayers for India. The man just loved challenges. There was nothing that he couldn't do.

     Of all his innings, his 233 at Adelaide is my favorite. That was Rahul Dravid at his best. What a great effort it was. With that innings he saved the match, and with his 72* in the second innings, he went on to win the match for India. The best part of that innings was the way he got his 100, by pulling Gillespie for six. And people thought only Virendra Sehwag could do that.


"All this going around is not aggression. If you want to see aggression on cricket field, look into Rahul Dravid’s eyes" - Mathew Hayden

       Apart from his performance on the field, Rahul Dravid was a perfect gentleman and great ambassador of the game. He can be counted as one of the last true gentlemen of the gentlemen's game. One of the finest batsmen of his generation. He was in the league of Tendulkar, Lara and Ponting. The best number 3 batsman in the history of Indian cricket. And as Harsha Bhogle once wrote that whenever an all time India team will be chosen, along with opening position and number 4 position, number 3 will also be already taken.

       Today when he has said good bye to the game, the game has got poorer. It won't be same without him. Indian cricket won't be same without him. The Mr. Dependable for last 16 years has left the stage empty. And on this day, that boy gives his tribute to Rahul Dravid, a true genius. Thanx for the memories. It was an honor watching you play. We'll miss you.

He is a perfect role model for youngsters. He has set a great example for all of us to follow. We are all trying to follow that path," - Sachin Tendulkar
     

Inheritance in JavaScript

         JavaScript is a funny language. For a few weeks I have been reading the book "JavaScript : The Good Parts" by Douglas Crockford. This is the first time I've tried to look at javascript as more than a language just for browser. Syntactically javascript is pretty much like C, but it has much more in common with Lisp than with C. For someone familiar with languages like C and Java, it can be pretty weird at first reading.        
         One of those weird/funny things is that JavaScript has Class-free objects. There is no class hierarchy, objects inherit from objects. JavaScript provides prototypical inheritance. Every function object in javascript has prototype property whose value is an object containing a constructor property whose value is the function object.
          this.prototype = {constructor : this};
          The language attempts to provide pseudoclassical inheritance so that programmers used to the classical style don't feel bad. But in that attempt, the language has become even more complex and messy. Here is an example from the book :


        //define constructor for the pseudoclass
         var Mammal = function (name) {
                   this.name = name;
         };
         //augment its prototype
         Mammal.prototype.get_name = function ( ) {
                   return this.name;
         };
         Mammal.prototype.says = function ( ) {
                 return this.saying || '';
         };
         //we can make an instance:
         var myMammal = new Mammal('Herb the Mammal');
         var name = myMammal.get_name( ); // 'Herb the Mammal'





         //make another pseudoclass that inherits from Mammal

         var Cat = function (name) {

                this.name = name;

                this.saying = 'meow';

         };

         // Replace Cat.prototype with a new instance of Mammal

         Cat.prototype = new Mammal( );




        // Augment the new prototype with get_name method.

        Cat.prototype.get_name = function ( ) {

                return this.says( ) + ' ' + this.name +

                      ' ' + this.says( );

        };







        var myCat = new Cat('Henrietta');

        var says = myCat.says( ); // 'meow'

        var purr = myCat.purr(5); // 'r-r-r-r-r'

        var name = myCat.get_name( );

        //'meow Henrietta meow'

                So as we can see this code looks quite arbit and weird. So, instead of using this pseudoclassical complicated approach, we can try to use Prototypical inheritance as it should be used. The author has provided some good ways to get rid of this mess. One way is to define a method like following :

                Object.beget = function(o) {
                        var F = function () {};
                        F.prototype = o;
                        return new F();
                };

               Now we can just write :
              new_object = Object.beget(old_object);


       And then we can make changes to the new object without affecting the old one. This is called differential inheritance.


        In all these techniques, there is something quite important that  we haven't yet paid attention to. That is the idea of encapsulation. Here we use closures fundaes. Let's revisit the cat and mammal example : 
          




       var mammal = function (spec) {
            var that = {};
            that.get_name = function ( ) {
                return spec.name;
            };


            that.says = function ( ) {

                return spec.saying || '';

            };

            return that;

       };

       var myMammal = mammal({name: 'Herb'});




       var cat = function (spec) {

           spec.saying = spec.saying || 'meow';

           var that = mammal(spec);

           that.purr = function (n) {

               var i, s = '';

               for (i = 0; i < n; i += 1) {

                   if (s) {

                       s += '-';

                   }

                   s += 'r';

               }

               return s;

           };

           that.get_name = function ( ) {

               return that.says( ) + ' ' + spec.name +

                    ' ' + that.says( );

            }

            return that;

       };

       var myCat = cat({name: 'Henrietta'});




             I've given brief description here. If someone wants more details, they can visit
             http://www.crockford.com/javascript/inheritance.html
             http://javascript.crockford.com/prototypal.html

Fermat's Little Theorem

           It's been around 9 months since my first and last post. (Just checked the date, exactly 9 months). I had said that I'd try to be regular, but if someone really trusted me on that, it's their fault.

           So, as I said that I'd write about interesting stuff I come across, this post is about an interesting theorem I recently came across, called Fermat's Little Theorem. 

           The statement of the theorem is pretty simple like most of the theorems by Fermat.

                      For a prime number p and a whole number n, n^p - n is divisible by p.   

          And like most of his theorems, Fermat didn't leave any proof.
          The theorem was first proved by Leibniz around 1683, but he never published it. The first published proof came from Euler. Both Leibniz and Euler gave essentially same proof. I decided to give it a try on my own before looking at their proof.

          First thing that I did was to factorize the expression.
                               n^p - n = n (n ^ (p - 1) - 1)
          So, the case when n is divisible by p becomes trivial. Now, the goal was to prove that
                          n ^ (p - 1) - 1 is divisible by p, if n is not divisible by p.
           The idea that came to my mind was induction.
          But before that, I thought of trying to do some arbitrary geometric series stuff, but made a stupid mistake in that and ended up wasting time because I found some impossible results. I tried to prove it using induction and binomial theorem, but no success. Even Prateek Agrawal tried something similar, but that didn't work.
         After wondering for some time, I finally decided to try induction on original problem and the following proof came out.

To Prove :  For a prime number p and a whole number n, n^p - n is divisible by p.
Base step : The proof for n = 0, and n = 1 is trivial.
Induction Step : Assume statement is true for n and try to prove for n+1.
                         So we assume that  n^p - n is divisible by p
                              i.e. n^p -  n = k*p, k is a whole number.
                         Now goal is to prove that (n+1) ^ p - (n + 1) is divisible by p.
Proof :  Expand (n + 1) ^ p using binomial theorem
             We'll get
                        (n^p - n)  + p*n^(p - 1) + p*(p - 1)*n^(p - 2)/2 + ..... + p*n
             n^p - n in this step is divisible by p(as assumed), for the remaining part we can write it as
                          p*(n^(p - 1) + (p - 1)*n^(p - 2)/2 + .... + n)
            Now if we can write it as k*p. All we need to show is that k is an integer. Here we can use the fact that p is prime, and claim that k is integer. And woah, our proof is done. That wasn't too difficult.
            If you want a more awesome proof, you can check the proof by Leibniz here.

            There are a lot of other interesting things related to this theorem like Fermat Primality Test which is based on converse of this theorem (which is not true), so it's a probable primaliaty test. The biggest problem for this test comes from Carmichael Numbers. These are composite numbers and for all n co-prime to them, n^p - n is divisible by p, where p is the Carmiachael Number.
            Also encryption program PGP used Fermat Primality test because the probability of generating a Carmiachael number is pretty small.
            I guess that's it for today. Will try to post something else soon. If someone finds some flaw in the proof, please let me know.
P.S. :- Thanx to Prateek Agrawal for his help with the proof.