Everything about Bottleneck Spanning Tree

In this post we will take a detail look on BottleNeck Spanning Tree (BNST).

But first, lets understand the definition of BNST.

Suppose we have a graph G(V, E). Now take out all the spanning trees of G. In all the Spanning trees, the maximum weight edge is called the bottleneck edge [because this edge is some sort of bottleneck for us. The ST cost can be reduced if we reduce this edge]. Of all the spanning trees, pick the tree whose bottleneck weight is such that its the smallest of all other bottleneck weights of other trees, i.e there exist no other spanning tree which has its bottleneck value lesser than the bottleneck value of the tree you picked up.

Lets take an example. Consider the graph below. Also shown are its spanning trees.

The bottleneck edge value is 2 in each case and if I pick any tree, there exist no other tree having its bottleneck value less than 2. Hence all three spanning trees are also BNST [NOTE: the middle spanning tree is a BNST but not a MST, the other two are].

Another example can be as shown.

Consider all its spanning trees. We can notice that spanning trees can have either of AB, BD or BC edge to include the B vertex(or more than one). So 8,9,10 are the heaviest edge that one of the spanning trees can contain and among all the spanning trees, there is no spanning tree whose maximum edge weight is less than 8. So pick any spanning tree with AB edge in it and it will be a BNST. Note that BNST is only concerned with its maximum edge weight.

Problem 1: Is an MST a BNST also? Is a BNST an MST also?

Solution: There are two ways to proving this.

First, by contradiction. Lets say an MST is not a BNST i.e for graph G(V, E), lets say there is an MST, T and a BNST, T'. Assume the maximum edge in T is e and that of T' is e'.

W(e)>W(e') because T' is a BNST and its by definition of BNST that all other spanning trees have their maximum edge weight greater than that of T'. That means if I add edge e to T', it will form a cycle and the cycle will have the maximum edge as e. By the red rule, the edge e cannot belong to any MST hence its contradicting. So the MST is same as BNST.

Second, Instead of proving MST=>BNST, lets prove that ~BNST=>~MST. Assume graph G has a spanning tree T that is not a BNST. Let e be the maximum weight edge in T. Lets say e connects two trees T1 and T2. Since T is not a BNST, there exists another edge e' which also connects T1 and T2 and W(e')

T=T1+T2+e

T'=T1+T2+e', where T' is the BNST.

Sum of tree edge weights, S(T)>S(T'), so T cannot be the MST. Now T is not a BNST, implies it cannot be the MST as well. Hence proved.

The second part of the question can be proved using the counter example explained above.

Problem-2: Give an algorithm to create a BNST of a given graph G(V, E).

Solution: The solution is very simple. For this, starting with the largest edge, remove edges from G one by one. If removal of any edge disconnects G, then keep that edge and continue the process with the next edge in sequence. Continue this until all vertices are covered. Now we have a spanning tree which is a BNST. Note that it is an exact opposite of Kruskal's algorithm to find the MST of G. Moreover any MST finding algorithm is also fine because MST is a BNST as well.

Another method is, find the median edge weight and remove all edges with weight more than the median. If the remaining graph is connected recursively repeat the process. If the graph is not connected then there are connected components in the G. Shrink these components into single vertices with edges coming out is similar to original graph and reconstruct till G is connected again. Repeat the whole process till result is achieved. It is O(|E|+|V|log|V|).

Problem 3: Give a Linear time algorithm to determine if a graph G(V,E) contains a BNST with its maximum edge <= b, where b is a given constant.

Solution: We remove all the edges with weights > b from G. Then we check is G is still connected. If yes, then such a BNST is possible, else not. We can use DFS to check connectedness of G which is linear.

References:

http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf

http://www.fongboy.com/classes/cs180/hw8-2.pdf

http://www.cse.nd.edu/courses/cse413/www/hw7_sol.pdf

http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Homeworks/hw2-sol.pdf

Algorithm: Determine the element that occurs more than n/2 times in an array of size n

Problem: An array of size n contains integers between 1 to n. You have to determine if there exists an integer which occurs more than n/2 times in the array. Also, find the element. This is also called the majority problem. One more thing, the solution has to be done in linear time and using constant extra space.

Solution: I tried real hard to think it over myself but gave up eventually. Going through the solutions posted in the web, I selected the following ones, which seemed to me more acceptable.

Despite many claims of doing it in under linear time (like logn), it is not possible to do it. I can always find a way to arrange the numbers such that one has to traverse the whole array atleast. Also, sorting is not allowed as it will make it nlogn complexity, greater than linear. O(n) sorting is possible, like radix sort but I think they donot do it in constant extra space. So here are my collected approaches.

Approach-1: A simple solution is to find the median of the integers in the array. Median can be found in O(n) time, called the Selection in Worst case in linear time. Since if an integer exists in majority, it must be the median itself. But median doesn't always guarantee that its the one. Once median is found, we need to run another traversal of array to count the number of times the median element occurs. If its more than n/2, thats the answer else return none.

Before going to next approaches, lets understand the concept of the solution. Since there is only one integer(if any) that can occur more than n/2 times in the array, the trick is every time you encounter 2 different integers adjacent to each other, make arrangements to remove them from the array, or simply pair them together and forget about them. And if adjacent numbers are equal, you continue with next integer in the row but remembering that the integer you encountered just now could be a potential majority element. If we go through this one, we are actually collecting the majority element together, and the in-between different elements are (kind of) removed by pairing them with one of the potential majority element. In other words, we are sacrificing one of the majority element to remove one of the other (different ) element. Eventually, the non-majority elements will vanish but atleast one of majority element will still exist because it is present more than half the times.

Approach-2: Take the first element, consider it as ele, the majority element, and put a mark for it. Traverse through other elements and do the following:

a. If next element in array is equal to ele, increment mark by 1.

b. If next element is not equal to ele, decrement mark by 1.

c. If mark is zero, make mark as 1 and consider the current element as ele.

When traversal is done, take the ele and perform another traversal through the array and count the number of occurrence of ele. If its more than n/2, return it as answer, else return NONE.

pseudocode:

-------------------------------------

m = 0

for (x = i..j)

if (m = 0)

m = 1

ele = A [x]

else if (A [x] = ele)

m = m + 1

else

m = m –1

endif

endfor

Another array traversal and count number of times ele occurs

if count>n/2

return ele;

else

return NULL;

------------------------------------------

Approach 3: This solution is very much similar to the one above, i.e the same concept of taking out pair of different elements out of the array and this one uses a stack to remember the previous encounters.

Create an empty stack. traverse the array and for each new element e,

a. If the stack is empty, push e into the stack.

b. If stack is non-empty, compare e with top of stack e', if both are equal, push e into the stack, else remove e' from top of stack (pop).

c. Once traversal is finished, if stack is non empty, remove the top of stack e' and do another array traversal and count the number of times e' occurs. If its more than n/2, return it as answer else return NONE.

As one can see that the stack performs the work similar to mark in the previous approach.

References:

http://taylor.thursday.com/classes/cs307/2/Majority%20Element.pdf

http://www.cs.nyu.edu/~khot/G22.3520-2009/sol1.pdf

http://stackoverflow.com/questions/744981/yaaq-array-of-size-n-with-one-element-n-2-times

--

Prelude to the Blog makeover

I felt like writing something. Its been a long time and moreover this blog is nothing but my nonsense thoughts. I mean, yes, it is exactly so. Take for instance some blogs where people discuss technical matters, this error occurred and I did this and that and poof!! the errors' gone. Some people write blogs on technical gadgets, giving their views, some people put up their photography skills on display, some people put up tutorial pages in their blogs and those are the ones that really help others. Yes, its true. I have myself got many of my computer bugs fixed through posts in one blog or the other. I have bookmarked many such websites where there are useful links, posts, images, directions, helps etc. And compare those blogs to this one. Sheer waste of google's space. Its just to feed my fantasies. Its just a consolation. Just a time-pass when I think I am a good writer and I had to vent out something somewhere to prove that I am a good writer. Trust me, I read my own articles many times and I like it but I am afraid if other would think so. Moreover I don't expect to show off my writing skills even if I have any. There are some people who publish their blogs to friends in the hope to garner some appreciations for their writing skills, show off. I ain't like that at all. I can live my life writing anonymous posts no matter how good they are.

From now on I have decided to make this blog useful to atleast someone. I think I have some computer knowhow, programming knowledge, software understanding etc. Time and again I bump into something interesting, like some interesting piece of code, some unknown shortcuts, tricks, some error handling solutions etc. So one can look forward to this blog for that. I think once I start my industrial experience, I'll be in a better position to put quality stuffs here.

Plus I like travelling alot. And I like planning before I decide on visiting any place. In that way, I can put up my travel itinerary here and the reason why I took this route, some suggestions for others, feedbacks to future travelers.

Apart from that, I take interest in photography also. So I'll try to put up snaps of the beautiful places I have been to. One step towards the same is the "Collections" series of post at this blog.

I am an avid reader of books also. I'll try publish my book reviews (completely unbiased, totally my own views).

Did I mention I am a movie worm? Yeah, I am a Hollywood movie freak and not only movies but take interest in watching documentaries also. I used to watch lots of Bollywood movies also but as I grew more and more acquainted to Hollywood, I kinda lost interest in Hindi movies. You don't have to worry about that. The Bollywood movies are all nothing but cheap remake of Hollywood ones and they are pathetic, trust me. Except for a few ones, Hindi movies these days are nothing but waste. And the few good ones that I am talking about, won't miss their spot on this site.

And of-course obvious is the the usual nonsense thoughts and everyday happenings that I have been putting in here till now.

--Goldy

part time = party time

Its been 9 months since coming to US and I haven't had a part time. Not any more!

There used to be a time when people were coming to US, completing their studies and everything and not spend a single dime from their pocket. All expenses, assistantships, funding and all provided by the University. Although the same doesn't happen anymore but there are some people who have this luxury. Others are spending, sometimes complete expenses, from their own. I was kinda in between. University paid 40% of my tuition, but I had to pay for the rest 60% of my own. I had to take an education loan for the same. So it was very very important for me to get a part time job here atleast to take care of my living expenses.

I tried hard during the initial days of my University, going through departments, stores etc and putting up an application wherever I could. As the days passed by, I kinda slowed down on my hunt. Partly because I wasn't getting any reply what so ever, and partly because my enthusiasm was dying. Moreover it frustrated me when some of my friends got into one or the other.

Come spring, and I realized a lot of my senior friends will be graduating this term and many of them had part times so why not ask them for some push. There is one guy from Bhubaneswar here, Sandeep, very nice chap and down to Earth. He was employed at the bookstore. He had helped me alot when I was new here, taking me to the Banks, completing formalities etc etc. I always used to consult him regarding University matters since he has been here for a year now and knows more or less everything about the University activities. I asked him if he could refer me to the Bookstore guys for hiring. He readily agreed and said to contact him again in the first week of April, when he will put up my name to the authorities.

Come April, I emailed him and asked to let me know when to come down to the store so that he can introduce me to his superior. He said it is not necessary for me to come down now. He said he will tell his manager about me and I can go and meet Mr. Tucker in 2-3 days and ask for service letter.

I paid a visit to Mr Tucker after 3 days. I told him that I am friend of Sandeep and that he told me to come down here and check if there are any positions open. The guy told me there are no positions open now and that I should see him in 1-2 weeks. I let him know that I don't have an SSN, and that it would be another 2 weeks before I can actually start working. He told me he can't issue me service letter unless he hires me for any position.

Anyways, I met him again after a week. This time he told me he can hire me right away only if I have an SSN. This was a shock for me. I was so very disappointed. I told him atleast give me a service letter now so that I'll apply for SSN and in 2 weeks I am good to go for the job. But he told me its a strict policy in the bookstore to mention SSN info before hiring anyone so he can't even offer me a position unless I have an SSN.

Now I am in a loop. Its like a dog chasing his own tail. I can have SSN only when I have a service letter, i.e he hires me for any position and he can hire me for a position only when I have an SSN. Now my head is spinning. I went to the International Center and they told me I can still work if I don't have SSN but I'll be paid only after my SSN arrives. I told the same to Tucker that atleast now let me fill in the position, I'll start working and apply for the SSN in the meantime and he doesn't have to worry about paying me for this time. To this he said they have policy they can't hire people unless they have SSN, so its the same story altogether.

I was so dejected. I had lost all hopes of this job. It was my time-pass for the long summer break, apart from the loads of studies. Seeing me so sad, Tucker told me to come around July and he will see what he can do but we both knew its a consolation. Even though I get a job in July, my summer is wasted, the time when I could have put in 40hrs of work per week (unlike 20 hrs during semester) and earned double money so that I need not take loan money anymore.

Tucker: Come in July and we will see what we can workout. You will be working alongside Sandy. Do you know Sandy?

I thought Sandy is some software the store uses to manage operations.

Me: Well, it will take me no time to know that. But I was banking heavily on this job now. I was thinking I'll be replacing Sandeep since he will be leaving this job soon.

Tucker: You know Sandy?

Now I realized he is referring to Sandeep by Sandy.

Me: Yes. I know him pretty well. He is the one who referred me for this job.

Tucker: Yeah. He once told me he referred one person for this position. Are you the one?

Me: Yes. I am the one he referred.

Tucker: Well then let me have a talk with Sandy tomorrow. Does he have your number?

Me: Yes. He has.

Tucker: Thats better. Let me talk to him on this tomorrow and you can expect a call from him sometime tomorrow.

Me: Sure. Thanks!

Then I left. It made me think. I was now sure that he didn't realize before that I am the one that Sandy referred. He must have been thinking something else when I told him I am a friend of Sandeep, may be he didn't pay attention to this statement or may be he did but it didn't strike him of any importance. Why does he care if I am a friend of 'xyz' or 'abc'? But the conclusion to be drawn here is that there was a communication misunderstanding that led to a week's delay. The next day, Sandeep called and told me to meet Tucker on Monday and he will give me the letter. I was so jubilant. Better be late than never.

On Monday I got the letter, took the application form from the International Center and applied for an SSN on the same day. Its a matter of days before I start earning some dough. One step towards my ultimate goal.

Before I wrap up this, I must thank Sandeep a thousand times for this opportunity. It would not have been possible without his help. Thanks man!

cheers....

The friends I have been with

One type of people we treasure the most are our friends. Atleast for me, my friends have always been special for me. So I thought to take a moment's time from my life and cherish the memories of some of the fascinating people I have crossed roads with.

When I was in school, apart from some of the hot chick's faces, I distinctly remember my happy times with two of my best friends there. One's name was Sudhamshu Ghode and another Abhijit Nayak. Ghode had more of a tamed animal's personality and I enjoyed bossing around with him. I used to ride on his back(his name signifying the same is ironic) most of the time and he would whole heartedly agree without ever protesting. It was more of demanding and serving friendship between us and I was always won over by his servitude. I never used to bring my lunch box to school and so I would always devour on Ghode's. Moreover, everybody in the class used to like him for his free manners. Ghode left the school in 7th or 8th grade and our friendship too. But unlike Ghode's, my friendship with Abhijit lasted till 12th grade. We were bound to become best buds since we had been in the school from 1st grade, if I remember correctly. I am still in touch with him although very rarely we exchange greetings. But nonetheless he still holds respect in my heart. Nadu, as we used to call him fondly, had a typical attribute in his body language. His body always had this motion, or vibration thing attached to it. Yes, his body was always moving, very slightly ofcourse but distinct enough. And he used to drool alot too. I mean, he never had this control over his saliva, that in the middle of some arguments over some problems in mathematics, while explaining, some saliva would suddenly come out of his mouth. Nadu, the name was derived from this act of his only. Although when we were young, we took pride in mentioning each other and to the world that we are best friends of each other. I don't know if during the later part of the school he had the same feeling or not, since we kinda matured and behaved like adults, had friendly arguments often, went to different coaching centers etc, but he still remains my best friend of my school. We both might have changed from what we used to be in 6th grade than what we became in 12th grade, but I still considered him my close friend owing to the long history we had shared.

There were some other school friends too whom I remember. There was Abhisek Mohanty, our Biolgy teacher's son. He was the best man in an argument and I always knew that noone can beat this dude in a friendly (or unfriendly) verbal fight. Then there was this haughty, hollow-inside group comprising of Preetam, Shivananda whom I always disliked cos they will never loose a chance to degrade you infront of bunch of girls or other smart ass friends of theirs to make an impression of themselves upon them, no matter how old your friendship might have been. They were friends with their kind of people only, as I believed. Then there was Rahul, the guy I hated the most throughout my school life. Although his younger brother was a gem, in his nature, but Rahul was a deeply selfish guy. We were friends too, since we had our houses nearby and he was also a teacher's son, like me and I used to hang out in his house alot when we were kids but as we grew old, he became more and more selfish as to the point that I couldn't stand his attitude anymore.

Among all my schooldays friends, there was only one, and only one person whom I admired, respected and adored truly as a friend, was Barun. He was such a jolly and innocent looking and selfless person and I always was bowled over by the purity of his heart and behavior. A true gem. Towards the end although he too became somewhat biased by being in the company of Preetam and Shiva and Rahul, and sometimes I didn't like him but when he wasn't with those guys, he was again the same, the pure form of himself. Thats why I liked him.

There were bunch of other friends too like Pankaj, with whom although my interactions were for small time but his jokes would always crack me up, I considered him a truly funny guy, pulling out jokes from nowhere and spoken as to bound to crack you up. Then there was Bittu, the living symbol of the result of a struggling family. His father had died long ago, his mother worked in the CRPF hospital as a nurse and wasn't earning much because in his house there would one find nothing except bare minimum stuff necessary for a living yet Bittu and his brother were fine, elegent gentleman type in their acts. They studied well too. Another person deserving a mention here is Jyoti Ranjan Mohapatra. He was in the C section (I was in A) and it was only during 11th and 12th grade that we came together to sit in one class, namely, the Science section. I spent my 2 years (11th and 12th) and major part, with him. We were in the same tuitions, same class. His unmatched quality to make fun of teachers, to be able to copy their expressions, voice, movements and everything and his ability to contrive his wildest imaginations and putting the teachers in there and make jokes around them influenced me so much, I must admit, today the person that I have become, the way I act, the way I try to make a joke and many more things are very much like Jyoti's. Except a few, I don't have contacts with these guys but I still remember their faces and occasional incidents, the moments I shared with them. Priceless!!!!

I was never comfortable talking with girls of my class. I remember faces of some of 'em, because they were cute and beautiful, but I don't have any moments, any conversation with them that I can recall. There was one girl, Smruti, whom I can consider as my best friend among girls because probably I spent more time talking with her during my school days than any other girl. She was also the school staff's daughter and lived in our own colony, which should explain the deeper acquaintance between us. Moreover, I think her mom also used to hate Rahul and so she would rather ask me to come over to her house and help her daughter with some questions in the history chapters than ask Rahul. Its a different thing that I would ask Rahul about the answer to those questions (for he was the topper in our class) and then go to Smruti's house and replicate the same answers on her notebooks. Smruti is in US, married and with a baby too. I am in touch with her, and I enjoy talking with her, remembering our good old CRPF days.

After 12th, I took a year's break, to prepare for my entrance exams. During that time I used to go to 2-3 places for my tuitions on Physics, Chemistry and Mathematics and I made some good friends there too but have lost contacts with all of them. During those days, I met with DibyaJyoti and we became instant friends, little did I know that this friendship will extend for another 6 years and during which time I'll come to know more of him and be influenced by his ideas.

The came the best 4 years of my life. My B-tech at NIT Rourkela. Staying away from home, for the first time, staying in a hostel with 300 other students and this for another 4 years and sure enough I met with some of the best people of this world and am glad of it. Among the closest friends I had when I left Rourkela was Ashwini Maharana. My best friend of NIT. A person of not so much of pure heart but still quite pure, not much of a funny guy but yet funny sometimes, not much of helpful yet very helpful almost all of the time, and moreover the one quality for which I'll always know him, Unlucky. No matter how careful he tries to be in every dealings of his, yet he would fall into some trap, be duped, made a scapegoat, always dominated by others. He was kind of the favorite, lovable by all others in the hostel and I take pride in the fact that he considered me his best friend, and we stayed in adjacent rooms during the final year, the year when students enjoy the college life the most. Although these days we talk less often but I still keeps an update on him. Next on the list would be Abhisek Bose definitely. The true prize of my 4 yrs at NIT. My only regret was, I got to meet and know him better only during the 3rd year but we became such good friends, I am sure we will remain the same till I breathe my last. He is the type of person that I am myself in many respect. Only that he has one more good quality, he has been very regular being in contact with me. I admit I sometimes don't feel like going out and reaching to my close friends, but Bose has never failed me in that front and I always feel like on top of world, cross my limits of ecstasy when I see Bose's call , or his "Hi" over gtalk. As I said, he is like my own reflection. Whenever I had asked him for any assistance, he was there with me even to the extent that he agreed to come with me to Puri on a stormy evening because I had this desire to spend a whole night on the beach. Not to mention that he made the arrangements for us to stay in a dharamshala which was on the beach itself. He truly is a true friend, above all. I would not have found the courage to visit Puri of my own, more so because it was raining cats and dogs those days and major parts of the state were under flood waters and as a matter of fact the following morning, ours was the last train from Puri to Bhubaneswar after which the railways services were disrupted between Puri and Bhubaneswar since waters had flooded the region. I'll always admire him for what he has been to me.

Apart from the two there were couple of others whom I consider close too, like Abhisek Saran, a pure, innocent and genius boy, Sibashish Acharya, a charismatic, life sacrificing friend, and many more.

Then came my two year stint as a software engineer working for Samsung, at Noida. And the single most influential people during this time on me was none other than Dibyajyoti. I must mention that he was with me at NIT too, all through the 4 years, he in mechanical branch, me in computer science but still living in the same hostel, with regular visits to each other's room and frequent hang outs but I never got to know him better. I must also mention that Barun and Preetam were with me too, in the NIT all through the 4 years, them in Mining (Barun changed to mechanical after 1st yr) but this was the time when I grew apart from Barun. He was spending his time mostly with Preetam and and his likes and was behaving like one of them when in their group but surprisingly he was the same old Barun again when alone. So I would talk to him only when I would see him alone or with other friends and avoided him otherwise (I avoided Preetam all the time). With Dibya, it was different. We were kinda close, good friends but I would say, never from within. When in Noida, he was to join CSC so he asked if we three (including Amartya, Samsung) could stay together and I agreed. I never expected to stay with him cos I never really knew him that well but I agreed because I thought its better to stay with someone whom I know something about than with some other guys whom I don't know anything about. While living with him, I would not hide the fact that we had numerous verbal arguments on myriad topics, his views rarely agreeing with mine or vice versa and yet we were hands and gloves on a lot of other matters. Although I used to be irritated alot by some of his acts, esp his casualness towards common household matters yet we both enjoy each other's company, we both would visit places together. Without doubt, he was the best thing, the best friend of mine in Noida's 2 years. We had the same feelings towards Amartya i.e sarcasm and we both kinda enjoyed it. Above all, gradually he made me realize there is no harm in buying a little luxury for yourself, now that we have started earning ourself handsome salaries. He made me realize money is not for stashing away someplace and living a beggar's life but living your life first and then stashing the leftover money. He made me realize that if I don't start living my life now, I might never get the same chance again, and I might as well save me some regret in future. He brought broadness into my thoughts and actions. I was no more irritated over messed up table or bed or be worried about my mobile or MP3 player not working. And this transformation has surely made me very very comfortable with people and things around me.

Then came my stint as a student again, this time in a whole different country, USA. While looking for roommates, owing to my broadness and highly evolved adjusting nature, I never cared with whom I would be living as roommates because I knew, whoever it may be, I'll be able to adjust. Luckily, I found Subrat and Ajit as the best roommates and in turn, friends that I could have found. Although the same doesn't go well with Bibhu because he has mannerisms typical of a geek, a class topper, a blend of selfishness and irritating behavior and uncomfortable with adjusting. In short, not at all open minded. No broad thinking, no broad perspective. He doesn't like sharing his bowls/plates etc for using in microwave by others, he keeps his charger nicely tucked away in his luggage and taking out only once in 4-5 days for charging purpose, doesn't like someone wearing his sandal even to walk inside the house etc etc. Well, I am too much evolved to worry myself over who is using my sandals or who is doing what with my plates/bowls and Subrat and Ajit are exactly like me too and thats why I bond so well with them. Such sense of freedom to use others stuff without feeling any 2nd thoughts invokes a feeling of brotherhood between people and thats why I donot think anything otherwise, no guilty, no shame, nothing, to use Ajit/Subrat's plate or his hard disk or his laptop without his permission, I use it as if its my thing and they use my stuff without any question and seeing them use my stuff I feel very very happy in the fact that they thought me as close enough to use my stuff without asking me anything, as if its all theirs. It makes me feel like we are all brothers. I agreed with Ajit when he said people's perception, thinking, actions are broadened, matured when he has been under a period of financial independence like the time we had(Ajit, Subrat and I have atleast 2 yrs of work experience) and sadly this is absent in Bibhu. May be its true but sometimes I think Bibhu would still remain Bibhu even if he would have 5 yrs of experience earning money. No doubt, Ajit and Subrat are the best things that have happened to me in USA. And Bibhu has been my worst.

This is where I would stop. This is where I am right now but I am sure I'll have more things to fill this place when I move on to new adventures. But one thing is for sure. I am proud of all the friends I have made. They are all exceptional people and I consider myself very fortunate to have company like these.

I miss my past

Its been 4 months since I have been to US and not a single day has passed without me missing my days back in India. With each passing day the thoughts are more and more pronounced. Every now and then something reminds me of my past life and the whole past flashes in front of my eyes like a movie clip with a strong background music going on and pieces from here and there making up the movie. Sometimes I see myself shouting at the top of my voice at one of my college's party night, I am jumping and dancing, the next moment I see myself in the midst of my friends and we are having a great time. I see myself going to office, I see myself making jokes with my teammates, I am having a party with my friends, I am going to see a movie with my friends, I am travelling, I am at the top of the mountain and remembering all my tours, I am with my cousin brother at Chittaur, I am at Manali with my office buddies, I am clicking pictures, I am sleeping back at home, the Blueline line bus ride from New-Delhi to Noida. Oh now I curse myself why I didn't use my time at Noida to see the Delhi at its best.

There is a lot of things to be done in life and every now and then I remember my times back home and not stop thinking if I could have used my time in a better way.

The US life is making me miserable from within. There is limited fun here and I thank my life I have some exciting friends here with me without whom it would have been hard to survive the days. The lack of money is forcing me to stay indoors and better not to start about studies. During semester, its only studies. I now see the pressure of securing a nice GPA. Never felt the need for it before but here it counts, and its everything. So now I have to study like never before and its hard to concentrate also. I am not used to studying seriously and at a stretch. I am worried about my grades. I have already kinda screwed up one paper. Two papers remaining and exams are 5 days away. Its hard for me to sit down and like study 2-3 chapters at a length and be done with it. I always think of doing something like it but I fail everytime. Every 15-20 mins I need a break. He he he. Yeah, thats how I study.

It even saddens me more that my life is going to be colorless and uncool for the next 2-3 years.

When I was in India, I was sure that I wouldn't miss my past. I was sure I am that macho not to remember the fun days and be sad about it. I thought I am over it. When I was in Noida, I would often miss my home but I was more controlling than others. In US, its a whole new story. I am so much far away from my house, my friends, my family that I miss them dearly.

The samsung days were fun. I was getting more money than I think I deserved. Although I became complacent but still, the money was good. It took care of my basic needs and travellings, parties, movies, beers etc. I loved that life. The financial independence brought a lot of fun to me. It changed me a lot also. I became more and more free, open. Not restricting myself to anything. My motto was There is no use of this money if it doesn't bring me happiness. So I spend it whenever, wherever I wanted not caring about savings or future. That brings me to my second motto, One can never be sure about how things will turn up in future, 5 yrs down the line one can only say that I may or may not be able to do this but now, I can definitely do this and have fun. Absolute surety at present is better than doubt in future. And moreover, after 5 yrs, I don want to think like I should have done this when I had the opportunity.

I remember the infinite visits to the malls, to the markets. The fun get together at the lunch table when the whole of AV team would come along and bring in new gossips. It was fun to know strange things about other people, half true half imaginary. The annual office party was one other thing to cherish. So much fun man!!! Loads of dancing, shouting. Its nothing but letting yourself loose. The other thing I miss is attending colleague's marriage party. Its kinda different get-together. Meeting your office friends, outside office, like in real life, like they are your real life friends. It was always fun and more fun if the marriage is some 4hr drive from the city. Awesome. We play all sorts of games on our way in the car. Like listening to the radio and guessing the song from the opening music, like waving to people outside and capturing their puzzled face in your mind and laugh thinking about it afterwards.

One of my teammate is going to marry in may next year and I am suddenly so depressed. He was my best bud in the office and damn I'll miss his marriage party. It kills me. I long for that kind of get-together party. Good friends make a special impact in your life, isn't it?

I have got some good friends here also. My roomies are simply superb. There is this girl who is also very close to me.In-fact she is close to everyone. She is funny and I kinda like her alot. I like talking with her, I like being with her but now this is killing me softly. She has got a boy friend already and these days not a single day goes by without me cursing myself why I met her. everytime I talk to her, I want to feel as if there is something between us beyond normal friendship, but I know she cannot be mine. It kills me everytime I remind myself that she has got a boy friend. I always wanted to he hers but..............

These days I try to avoid her and restrict myself. The more I talk with her, the more painful its for me to separate. Although I joke about her relationship, make fun of it but from inside, I feel someone took away one of my hand. From inside, I become like dead serious. The feelings are one sided and would remain like that. And it is more depressing that she would never know I had such strong feelings for her. I won't tell her anything. She is happy with her beau. I don't wanna ruin her life by introducing more complexities. I am also dead sure she would reject me if I propose. Anyone at her place would do the same. There is only one happy ending to this. If she feels something for me too and if its more than normal, may be she would come to me but that is highly likely so the sad ending is that I have drink this poison for the next 2 yrs that we will be around.

Man! Know I feel how one feels when in Love. She magnifies my good feeling when we would be talking, I can hardly imagine how elated I would be if she were my girl friend. Enough of imagination................

one of those better days

Well, yeah. What a lame title to begin with but honestly, I couldn't find anything better. Its been in my head since evening, since the time I started my ride back to home from the university.

There were lots of things happening to me today. For starters, I got a Historian post of the students association body of the computer science dept. Thankyou very much. Appreciate it!

And that sums it up. Yeah, the other major advantage was I got some breakthrough in my parallelizing project. There is this awesome project in which we have to pick an algorithm and device methods to run it using thousands of processors. I am doing it in CUDA which I can only say till now is awesome to look and study about it in the surface, but when you actually get down to writting kernels, and start dealing with keywords like shared memory, for loop, threadId.x etc etc, life begins to suck. Yeah. Trust. Starting days with compiling and running stuffs will be frustrating but later on it will go great when you actually some in terms to know how this thing actually works. Yeah, its awesome. You know what, people still have genius instincts in them. I thought that era is over.

How do you react when you are given certain responsibilities? Something out of your bound, you never expected it and boom!!!! you are in for a surprise because the mailman just delivered to you a post of manager (read historian) at some crazy going association. Suddenly I am elevated to a height from where I can see everyone else, and vice versa.

Speaking of which I remember my algorithms teacher here. He is such a great guy and teaches like it will blow your mind off but guess what, I do him in the class. Yeah, he looks so funny to me and not only me but everyone else. In fact majority of my friends do him. We pick on him, we copy him, we comment, we gesture, we do anything humanely possible to get a crack out him. He is kinda a romeo type guy. I mean he is married and must be having a beautiful wife with kids but I don know why he seems to be excited to see the video recorder hot university girl. He sometimes even visit her in the recorder room to say that he is ready to start the video and some other times if there is a guy, he would just thumbs up from the dais.

But tell ya what? I like the education here. Although an M-Tech from one of the IITs wouldn't have been that bad either, but its good here too. Yeah the price is a concern but with banks like SBI and loan rate like 10.5, I would say, Suck on that!!!!!!!!!

Speaking of loan, I cant get a good night sleep at night. Its my first albatross around my neck. Yes, trust me, I consider it as a chain, holding me from going out and enjoying my life and time. I can't eat outside, I can't go bungee jumping, i can't go scuba diving, I can't go sky-diving. Oh my God!!!!!!!!!!!

My life was awesome when I was in job. I was into money. I was travelling places. I was doing crazy stuffs and enjoying it. I liked my colleagues. But then this thought was bothering me all through my time after B-Tech. Why should I be satisfied with bachelors only? Why cant I go higher, like masters or doctors? Every other guy is a bachelors now. What makes me different than other? I am different. I want to be different. I don wanna stand in my marriage mandap and have people talk that ooohh he has done his bachelors and others go like, wht??? even my waste niece is an MBA, couldn't this guy try any harder to study more about earthly stuffs.

Its not about going around shutting up other people. Its about shutting up the person looking you through the mirror. How can you avoid that. Its like ignoring the person which plays a record player in your mind and there seems to be only one thing coming out of that player, "Inspite of knowing you can do it, you never had the guts to do it".

Atleast after taking the jump from clean tap water to the sewer, I silence those people. Yeah, job life was awesome. The financial independence, the new friends made whom I miss so dearly and now from that to this, a huge loan on your back, student again and unemployed and expenses don't seem to stop.

The return is sometimes satisfying, thts when you compile the program and get the desired result and sometimes frustrations, thats when you just missed the bus and now you are 5 mins late to the one class where in the teacher uses the first 5 mins to introduce us to the topic that he would be teaching today and the introduction helps you understand the head and tail of rest of the lecture. You miss the intro, you practically miss the whole lecture. Damn those bus drivers. Damn me!!!!!!