Killing the Loop in a Link

In the last post we discussed a way to find the loop in a link. Once we know that there is a loop in our linked list, first thing we should do if we want our linked list to be realistic and usable, is to remove the loop.

How do we kill the beast? I guess if we know where the loop starts, we will be able to burn its tell (set the next pointer of the magic node to null).

Lets get started.

What we already know? 

From our little stint in the last post in this category, we know for sure that there is a loop in the below linked list.

Linked List with a Loop

We also have our hare and tortoise pointers pointing to an element inside the loop. Like so.

As the hare and tortoise story goes, the hare stops in between the race thinking that the tortoise can never catch or overtake him. Eventually the tortoise through its sheer perseverance catches hare, overtakes him and wins the race. Nice inspirational story.

In our case, the ends don't meet as we don't have an end to our linked list. And by the way, our hare has read that story and thus he never stops. Which means he will continue to loop crossing the tortoise again and again until we let him stop. Which also means that at this point when both hare and tortoise are pointing to the same node, if we let our hare run and at each node increment loopsize by 1, by the time hare catches tortoise back, we will have the size of our loop.

What we already know? Update 1.

• That there is a loop in our linked list.
• And the size of the loop (in this case 4). 

Now lets start at the beginning again. Set hare and tortoise both to point to the start of the linked list and then give our hare a heads up of exactly the loopsize. (Yeah, this time no matter what, we will let our hare win the race. Why should tortoise have all the fun?). This makes hare and tortoise loopsize apart - make a mental note of it, this will come handy.

What we already know? Update 2.

• That there is a loop in our linked list
• The size of the loop
• And two pointers one pointing at the start of the linked list and another loopsize away from it.

Now advance both hare and tortoise exactly by one node until both point to the same node at which point, tortoise will be at the start of the loop and hare will be at the end of the loop. And yeah, its a loop so both start and end are same :). Also while you are advancing the hare pointer, keep track of the previous value, something like this:

previous = hare;

hare = hare.next;

What we already know? Update 3.

• That there is a loop in our linked list
• The size of the loop
• The start of the loop.
• The Element at the end of the loop that points back to start.

Now killing this loop is simple. As I said earlier, just burn the tail. Okay, in technical terms, doing something like previous.next = null (removing the red pointer in the above figure); should do the trick. Here's our final linked list without a loop in it.

I hope you enjoyed this post. And I was able to express the algorithm in a way that will stick to your grey matter.

As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat

P.S.

After successfully understanding the above algorithm to find and eliminate a loop in a linked list, you have an important and very handy tool under your belt sometimes referred to as a Two Pointer Algorithm. This algorithm can be easily used in a lot of other problems. One such example is:

• Find Nth node from the end of the linked list.

I would like to leave you with the problem to find a solution. You can google for a ready made algorithm to solve this problem, but if you think on the grounds of what we just discussed in the last two posts, it might stick around your head a bit longer.

Also, this post pretty much concludes our discussions related to the singly linked list data structure. Although we will come back to the topic as and when it feels like a right thing to do :).

Dejavu : Finding a loop in a link

The linked list data structure we discussed in my last post in this category is really nice for sequential data. Insertion and deletion is also nice and simple. There is one problem though. If you want to go to the nth node in the linked list, you have to start from the first node and move one node at a time to your node. What if your node is the last node? You will have to start from the first node and traverse the entire list to get to your node.

Suppose you have the following linked list at hand and you want to go to the node Museum which is the last node. You will have to traverse through the entire list before you can get to it.

A simple Linked List

Okay, I know you love The link so much that you are ready to compromise and are OK with this tedious traversal. But the problem doesn't end there.

Me: Consider the following list. Try traversing through it.

Linked List with a Loop

The Link Fan: What's the big deal here? Here I go: Chocolate, Apple, Table, Shoe, Museum, Apple, Table, Shoe, Museum, Apple. Hold on, I feel like I have been here before, I can feel the word Apple coming again. Is it Dejavu?

Me: My friend, you are not in a Matrix and this isn't Dejavu. What you are feeling is a cycle (or a loop) in a linked list. And you were able to notice it because you are Neo, the one or at least a human, if that gives you any pride. But The Matrix (a computer program of-course) will not be able to detect this cycle and will continue to traverse through this list until it runs out of its resources (Only if Neo new this trick, he could have broke the Matrix in no time and there would not have been a need for all that machine war).

Is that what you want? Of-course not. Not in the real world not of The Wachowski brothers.

Then we must find a way to detect this cycle thingy and if possible, a way to get rid of it.

So lets first try to detect the loop.

• Let's start simple, if the link is empty, it cannot have a loop. So we are good there.
• If there is only one node which points back to start, you know that there is a loop.
• Now if there are more nodes, we need something to detect a loop.

We will use an algorithm called a "Two pointers algorithm". This is also called a "Hare and tortoise Algorithm" because one of the pointers is slow while the other one is fast.

So lets get started, if there are two or more nodes, start the tortoise pointer at the first node and the hare pointer at the second node. Now we will continuously advance the tortoise pointer by 1 node and the hare pointer by two nodes (You see? Hare is faster than the tortoise).

If there is a loop in our linked list, at one time both the hare and the tortoise will point to the same node (In the real Hare and Tortoise story, the hare stops and rests because he underestimates the tortoise. Our hare here is honest as god, it will loop indefinitely if you don't ask it to stop. So, unless there is a loop, our hare and tortoise will never cross each other.). If that happens, you can be sure that there is a loop in your linked list and terminate the traversal.

If there is no loop in the linked list, the hare will eventually point to the end of the link(hare = null) or in case where there are even number of nodes in the linked list, you would not be able to complete the step hare = hare.next.next because hare.next is null (in other words, you would not be able to advance hare by 2 nodes because there is only one node before you hit the end of linked list).

To try the above scenario, remove museum node from the above linked list without a loop.  The hare can only be advance once(when it points to shoe) before hare.next is null.

Lets see if that works:

In our linked list with Dejavu, the hare and tortoise will have following stages during their traversal.

Tortoise and Hare on loop

If we remove the loop and run our algorithm (Linked list with odd number of nodes), it works something like this:

Tortoise and Hare on a straight highway

So this is how you find a loop in the linked list so that you can avoid running out of resources while traversing through a list that never ends.

I hope you enjoyed this post. And I was able to express the algorithm in a way that will stick to your grey matter. Also, do let me know if you think there is a better solution to this problem.

As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.

In the next post, we will discuss how to get rid of this loop. 

Until then,

Happy Learning!

Banyan Bat

Trick to an easy knot to an inflated balloon

As I told in my last post, I was attending a birthday party for one of my friend's daughter. It was a friend's daughter's birthday, so this uncle had to do something to help the overworked father complete the necessary arrangements. So, I chose the simplest of the tasks, well I thought so. Inflating balloons!! You would say, its not that easy, you have to exhaust your lungs. Haha... I am smart. I had already noticed that he had the pump to do that job, so I thought it would be fun. But I missed one important part. The inflated balloon needs to be tied so that it does not loose its air. How could I miss that? And (not so) surprisingly I was worst in doing that until that day.

So I shared my misery with my friend engaged in the same endeavour of helping the overworked father. Luckily he knew just how to do that. He courteously shared the steps with me and helped me learn it too. Thanks to him, it was a joy to inflate those balloons and tie knots on them.

Here are the steps for people like me (unless you all know it very well). Steps courtesy: The Friend: Rahul.

Step 1: Inflate the balloon using a pump or your own lung capacity. Make sure you don't blow it to explosion (Trust me, it happens. We exploded a bunch of them :) and we kinda loved it.).

Step 2: Hold the balloon in your left hand like so. Notice the index finger and thumb pointing up.

Step 3: Pull the open end of the balloon as far as you can safely holding it with index finger and thumb of your right hand.

Step 4: Now, pushing the balloon down with the three fingers of your right hand, push the stretched end of the balloon from above the balloon besides/along with the index finger of your left hand as shown in the pictures below. (Forgive me if I could not put it in words correctly. Believe me, I tried real hard.)

Step 5: Now, pull the open end of balloon slowly taking the index finger of your left hand out. The smooth and shiny nails really come in handy here.

And here's your inflated balloon with its knot tied securely.

Do let me know what do you think about these steps and let me know if these instructions could have been better.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat

My journey through sketching .....from nothing to ...wait for it .......beginner.

childhood memory

I am writing this post because if someday, I become good at sketching, I will remember that I had a humble beginning and I was nowhere close to perfect and will not be perfect anytime soon. Another reason I am writing this post is that if someone who reads this post (if at all anybody does), wants to start something new and is afraid of it because they are not sure how good they are at it and how far they can go, they can get some motivation. Another reason I dared to actually post this is that I have just been to a birthday party for the 2 year old daughter to one of my friends. And can you imagine, what I could give her apart from blessings? I gave her a portrait of herself.

Drawing a portrait of someone you know is an entirely different experience than drawing a portrait from an unknown image and its hard to put in words. The sketch starts with relatively vague and strange looking shapes, but as things start getting shape piece by piece, the character of the person you know starts building up. When you show this image to someone and they instantaneously recognize the person from the sketch, it feels like winning a gold medal.

And after all, this blog is all about my endeavours of learning new things.

Ohkay!!! Enough of prologue(s). Lets get started. The story goes back about 18 to 20 years when I was still a child. Back then I had scribbled a few cartoons and a few scenes. My favorite was one particular scene involving two pointed mountains, a smiling sun, three four birdies, a coconut tree and a river flow which probably every child does in his/her childhood. But apart from that I drew nothing that would grab anybody's reasonable attention. A few pats on the back form the nearest and dearest who would appreciate even if I scratched my belly with a pen is all I got. This would be while I was not even in my teens.

As it was not worth anybody's attention anyway, it simply went dormant in the background until I was well 29. In these 17 years or so, I never sketched a thing as if I had no idea about it. I do not remember any other art that allowed me to come near itself. I am deliberately not mentioning my buying a black acoustic guitar and a guitar tuner because that affaire did not even last a couple of weeks. Though I still miss that black beauty. (Yes, the answer to the question: "Does it come in black?" is YES). I gave away that guitar to one of my friends who actually knew how to play one. Thats the only good thing I did to my guitar. Yeah I know, and I appreciate your keen observation. But I could not resist to mention my guitar.

Then one fine day while I was getting bored in my apartment in Mumbai, out of extreme boredom, I scribbled something on an empty envelope laying around in the dust. Here's the picture for your reference:

My First Sketch

It sucked. I knew and that was perfectly fine because I was not into sketching anyway. But then I thought why not give it a try. In today's world of internet and YouTube, its really not hard to find any kind of help you need. If you want to learn something new, you are just a few clicks away from some of the best teachers/gurus on any subject what so ever. So I just did a Google search and I got something to start with. I started with something like: "how to draw a face". Another thing great about Google is that once you search one thing, it kind of puts you into an information loop which literally has the ability to advance you from novice to beginner to expert. This ability of internet is only limited by the limitations you put on yourself.

So, using these intuitively ordered recommendations from Google and some of my own interest and enthusiasm, I was quickly able to draw a few specific versions of faces.

Not my first Sketch

This was interesting and intriguing. Still because I was not crazily in love with drawing and sketching, I had to push myself to start drawing. But once I started, time would fly. I thought why not try some cartoons and that was good too. They may not be perfect but each drawing gave me a sense of achievement.

As Steve Jobs says, every artist signs his work. So I started dating and signing my work :). I know there are millions of artists out there who can draw much better than me and my scribbles are nothing more than a bud. I don't know if these will ever become trees, but I know one thing for sure, if I nurture and water them regularly, they are bound to grow. That's all that matters to me.

I also wanted to put my drawing to some productive use so that I get motivated to draw more often. Nothing came to my mind as such, until I thought about starting this blog and my friend Sabyasachi suggested me that I can use this to enhance my blog and since then drawing became an integral part of my routine.

Now I have a few focus areas I would like to work on for drawing and sketching:

• Keep drawing at least one picture per blog post.
• Learn to draw portraits by looking at the person's face instead of a picture.
• Try to avoid the use of eraser as much as I can.

With the hope that my journey of learning could be of help to someone, I will keep posting my strategies/progress and any other new things I learn as part of this process. I would really love to hear from you about your experience of learning a new thing. And if you could guide me in progressing through my endeavours of learning sketching, nothing could be greater than that.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat

Meet The Link...

Link from The Legend of Zelda

We have worked enough with our friend caterpillar to fall in love with her. We have worked with her close enough to find out her good qualities and bad ones if any.

They say you will have a good social circle if you focus on the good in people and ignore the bad. Gratitude is the key to success and riches. But at the same time you need to find problems so that you will seek solutions and not seat around satisfied with what little you have. To help us with both these views, thank Gods we have with us today: Mr. Optimist as well as Mr. Pessimist. The thing is, these two lads can't talk to each other without biting teeth. This is how the discussion ended up while they were talking about our friend caterpillar last night over a few pitchers of beer which is the only thing they seem to enjoy together and agree on.

Mr. Optimist: My dear friend caterpillar eats happyly (Insertion in an array is easy).

       Mr. Pessimist: Well only until you allow her to eat all the junk she gets her hands on (Insertion in a sorted array is not as easy). And by the way, there is an I in happiness.

Mr. Optimist: Well she knows where the stuff is going (Random access to any element of an array is easy-index based access). And by the way, you pessimist! What do you know about happiness? You are my tragedy queen.

       Mr. Pessimist: I guess by know you know how hard it is to find where all the wrong stuff ended in her stomach the last time she munched on those chocolates (searching in an array is tough, so is deletion. Further, deletion involves moving elements to fill the place of a deleted element). And yeah, don't forget what a trouble it is to move things around in her belly.

Mr. Optimist: Yeah yeah, you don't have to care for her eating habits; I can take care of her. And by the way, she can eat only so much. She knows when she is full (Array size is fixed).

       Mr. Pessimist: Yeah, that's another headache, sometimes we need to eat more just to finish what was served simply out of courtesy. But she is adamant and stubborn and arrogant. She won't take an extra bite.

Mr. Optimist: Go away you moron.

       Mr. Pessimist: Shut up you .......

While Mr. Optimist and Mr. Pessimist fight over the good and bad of our cute caterpillar, let's introduce ourselves to a bit more sophisticated data structure and let's find out if it is worth extending our friendship to. Is it any better than our little caterpillar? I am even considering hanging out together with the Caterpillar and this new friend if it is worth it.

Please welcome majestic Mr. Link A.K.A Linked List.

Definition of a Linked List:

A linked list is a linear collection of data elements called nodes pointing to the next node. Each node has a reference to the next node. It is a data structure consisting of a group of items which together represent a sequence.

A Detour:

To imagine, understand and remember Linked list forever, we will use something unique but wonderful. With the help of this unique tool, we can remember not only the implementation of linked list, but also any list of items, tasks, states of a country or anything that comprises of items linked to each other.

You may not know (Hopefully you did not notice it in my blogs), but I always had difficulty in forming and remembering spellings for English words (I still do). I knew it and I wanted to change it. So I was searching for some wisdom, technique, procedure or steps that will help me conquer this difficulty. I browsed internet, went through blogs, read books but nothing quite convincing came across. Then one fine day, I got reference of this book called "The memory book" by Harry Lorayne and Jerry Lucas. This book changed the way I remembered everything.

This book has several memory techniques to help remember all kinds of things. One particular technique called "The link system" caught my eye as it helped me understand and remember the data structure Linked List.

The link system:

Suppose we have following list of items to remember:

• chocolate
• Apple
• Table
• Shoe
• Museum

Let's assume we remember chocolate easily because you like it. lolz, nope, but because it's the first item in the list. There is a way to make sure that we use a system to remember this first item as well but let's not go in those details as we are good with this assumption. Now, to remember rest of the items, we are going to link each item to the previous one in such a way that if we remember chocolate, we will remember apple and the apple will lead us to the next item in the list - table. The table will then remind us of shoe which will finally remind us of Museum.

The trick here is to make the first item a trigger to the memory of next item in the list.

As per our assumption, we already know the first item chocolate. Now, as per the system, our task is to link chocolate to apple. To achieve this, we need to associate chocolate to apple in some ridiculous way (Note: There is science, evolution and neurology behind the fact that a ridiculous imagination works. I would humbly avoid getting into those details at this moment.). Imagining that a huge chocolate is eating an apple instead of me does the trick for me. So the current state of my memory can be summarized as shown below.

Now, to link apple to the table I imagine that a huge table is sitting on a huge apple.

By continuing the same process for shoe and museum, we get the following in memory.

That's it. We have remembered the required list of items. Now you can recall it anytime you want. If you no longer want to remember it, no worries, it will gradually fade away as well. This system is really wonderful and it potentially lets you remember any list with ease no matter how long it is and how long you want to remember it.

If I need to add an item to the existing list, I just need to reimagine the new link

If we need to delete an item from this list, it's also a matter of some re-imagination and re-association. 

Wasn't it easy and fun? This was nothing but a real life breathing and living example of a linked list data structure. Now, do go through the definition of linked list and the final image of your small memory map above. Aren't they similar? Now it's just a matter of putting it all together in your favorite programming language.

Implementation:

To implement linked list as a data structure let's redraw our list of items with some new labels.

Let's make it further data structurish:

Looking at the above diagram, to implement this linked list in java, we need following steps: 

1. A class called LinkedList.
2. A reference (start) to the first element in the linked list. When this list is empty, start will be null.
3. A class called Link which has two attributes:
1. data - it is the actual data being stored.
2. next - it is of type link again.

Insertion and deletion are a matter of some re-association as discussed for the list of items to be remembered. 

I think the data structure linked list is now under your belt. Do let me know your views on the same.

As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat

Comparing simple sorting algorithms

Its summer in Canada, which means opportunity to enjoy a lot of outdoor and travel. So I have been busy travelling to some places. But I can't forget that I put bread on my table being a software engineer. It comprises a considerable chunk of my life. Hence you are bound to see a lot of posts here. Last time I posted in this category, we saved Bubbly some money and helped her gamble successfully in Las Vegas.

As part of the ordeals of saving bubbly, we also learnt three simple yet powerful ways to sort a bunch of elements. Bubble sort, Selection sort and Insertion sort. It is only human nature to compare stuff when you have multiple options.

But before we start comparing different algorithms, we need to set some rules. Until now we tried to keep the complexity out of our equations and we will continue to do so as far as we can, but its a fair wish to compare our options.

All work and no play makes Jack a dull boy. But all play and no work also seems to do the same. :) So for a change, this time its going to be a dam serious affaire. Bite me if I smile here after or let you smile. The fact is, I tried so hard to find a funny way to explain this complexity stuff but I could not. I will still continue to find a funny way to understand this stuff but until then, let's be serious as hell.

Welcome to the space time Continuum ...

When we write a program or an algorithm, our primary goals are:

• It does what its supposed to do.
• It is able to identify the error situations and is able to handle them properly.

But that's just scratching the surface. In our normal Hello world program and almost 90% of real life programs, that just might be fine, but when it comes to real life complex and large scale applications, few things become more critical. Some times even if the program does what it is supposed to do, that's just not enough and it must be seen: 

• How much space will this program consume at runtime.
• How much time will it take to complete the execution.

Space Complexity:

When a program executes, we are concerned about:

• How much space will it take on the stack (method calls and local variables)
• How much space will it take on the heap (Objects and their references)

The stack space is fairly simple and we would not focus on it as much. We will calculate the heap space as that's what matters the most and is dependent on how we write our code and what are the inputs to the code.

The space complexity can simply be defined by the following equation:

Space complexity =  Sum of space needed for total number of objects created + space needed for references

Time Complexity:

Time complexity of an algorithm is also determined after finding out the important inputs and deciding factors.

The time complexity can simply be defined by the following algorithm:

Start with count = 0.

for each step executed in a program, increase count like:

for each step

count = count +1;

But an important thing to consider while calculating these complexities is that based on the input factor, the algorithm may at times perform at its BEST while at other times, it may perform at its WORST

They say: Hope for the best and prepare for the worst. For a programmer the saying is: code for the best, prepare for the worst. Funny huh?

Be it time or space, as programmers I think, for us its more important to calculate how much maximum time or memory our program would take so that we can plan our resources accordingly. So we will mostly focus on the Worst case scenario here. Also,  At this point, we will only focus on the time part of it as for the programs we will write for a while, our personal computer's memory would be much more than enough and we won't run out of it.

Asymptotic Notations:

Asymptotic means approaching a value or curve arbitrarily closely (some sort of limit). As mentioned earlier, we are only preparing for the worst. So we will only discuss the asymptotic notation that describes the worst case time complexity of an algorithm.

Big-O

As already discussed, and which will be more clear when we compare our efforts to save Bubbly, how much time and algorithm will take largely depends on the input we provide to the algorithm. For simplicity, we would go further and say it largely depends on the size of the input to the algorithm.

So if I say that the time needed for the execution of an algorithm is a function of the size of input to the algorithm, I hope it would not be too much of math here.

so I can say:

Time complexity = f(n)

Now, Big-O notation represents the worst case time an algorithm can take. Its an asymptotic notation, which means it will represent the complexity like approaching to some value. As its worst case scenario, Big-O will represent the maximum time an algorithm can take.

so I can say:

Worst case Time complexity = O (g(n))

So I can say, at all times:

f(n) <= C * g(n)

where C is the constant time representing steps that are not directly dependent on the input.

With this background, lets analyze how we did in our three attempts to save bubbly.

Bubble sort

As you can see in the post Operation rescue Bubbly... in the first pass through Bubbly's stomach, we did 4 comparisons, in the second pass we did 3 comparisons and so on down to 1 comparison on the last pass. For 5 chocolates, this was: 

4+3+2+1 = 10

lets generalize it. So if Bubbly had eaten n chocolates, it would be:

(n-1)+(n-2)+(n-3)...+1 = n*(n-1)/2

The -1 here does not make much sense, specially if n becomes quite large. So we can say that the algorithm does n^2/2 comparisons.

There were less swaps than comparisons as two chocolates were swapped only when needed. But for our worst case scenario, lets assume there was a swap for each comparison. so we have n^2/2 swaps.

As can be seen in the above definition of Big-O notation, constants are ignored, so we can say:

Time complexity of bubble sort = O(n^2)

Selection sort

When Bubbly did the mistake again in a silly mistake..., we tried to find a way to save bubbly with some less pain to her. What we did was try to use selection sort on her stomach. Though the number of comparisons we did were the same, we saved some effort on the painful swapping part. The saving on swapping is actually a great deal if the number of elements is large. 

As you must have seen, in each pass through Bubbly's stomach, we did only one swap if at all. In a worst case scenario, there would be exactly one swap for each pass, so in general for 5 chocolates, there would be 10 comparisons but less than 5 swaps, if there were 10 chocolates, there would be 45 comparisons but less than 10 swaps.

As there are O(n^2) comparisons needed to complete the sort, the overall complexity of the algorithm still stays O(n^2), but selection sort is undoubtedly faster than bubble sort as it requires very few swaps.

Insertion sort

This one is the best so far. The overall complexity of insertion sort is also O(n^2) thanks to the comparisons on each pass, but its almost twice as fast as bubble sort and a little faster than selection sort. Lets find out how:

The very first reason it is faster than the other two is that it does not do a swap at all. It does a copy which is faster than a swap. Secondly, the comparisons done are on a sorted array. So in the first pass, it does a comparison on 1 item, in the second pass it does a comparison on 2 items and so on up to n-1 items. So in a worst case  there are n(n-1)/2 comparisons.

As can be seen from Bubbly's ordeal in Las Vegas: Bubbly goes to Las Vegas..., we needed only 3 copies when we moved 2,4 and A to their deserved positions respectively. But in most real life situations on an average, about a half of the items need to be compared and copied, before an insertion point for the next sorted candidate is found, making the algorithm faster than the other two in real life situations as well.

So after all, gambling is a good thing. It taught you how to sort numbers the fastest. But hold your horses there, these sorting algorithms are just scratching the surface. There are lot faster algorithms out there waiting for our exploration. 

I hope this article was as boring to you as I expected it to be. 

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat

For the first time's sake....



I don't think this one needs a caption.

I could not write over the last few days because I was travelling to the two beautiful cities in Canada, Montreal and Quebec. I particularly love Quebec city dwelling by the shores of the majestic St Lawrence river. The exquisite European architecture around every corner of the city is hard to be missed when you walk on the typical French narrow streets. If you are fond of history and culture, this is the city you have to visit. And if you are a relaxing stroll kind like me, nothing is more relaxing than the walks across the old Quebec city in the warm and quiet summer early morning.

A beautiful restaurant we spotted while in Quebec city.

Evenings in Quebec are not as quiet as mornings, because of all the tourists and travellers from around the world. Even with all the tourist rush, the evenings are beautiful and enriching. I like to visit a patio once in a while. Patios feel great if they are on a beautiful location, because you get to have your dinner in the nice warm and fresh weather appreciating the life and nature around. Quebec city has plenty of them and any location here just seems nice.So, Quebec naturally becomes a great destination for a patio lover as well.

The heated patio of Savini where Mr and Mrs Banyan bat enjoyed an Italian dinner.

Well, while we are on the subject, let me share the story of little Joe who is now starting to enjoy his travels and who is secretly wishing to visit as many beautiful places as he can. He doesn't even know how he would visit a lot of places in his list. But there's no harm in dreaming, right? Before his 21st birthday, Joe had hardly crossed his native state (a beautiful state in India). The only out of state travel he had done was a trip to Jabalpur Bhedaghat (a magnificent water fall on the river Narmada). It is a little Niagara Falls. That was the most amazing trip he ever had, well until 2006. It was the first time he saw a beautiful and gigantic waterfall in his life time. On 3rd February 2006, he embarked on the 36 hours journey to the God's own country, Kerala. The longest train journey he had been on so far. The views from the train while it crossed states one after the other were breathtaking. The view when the train entered Kerala and cruised along the coast of Arabian sea was simply great. Joe was going to Kerala for the initial training before starting his first Job.

The training period was filled with a lot of new experiences like green/blue waters in deep Indian ocean, Interactions with people who didn't share his mother tongue and staying happily with complete strangers who will become his best buddies in the time to come. This is where Joe got the glimpse of a multicultural community.

The training was completed and Joe joined the company, worked in Mumbai for another 4 years and the time came when he boarded an international flight for the first time. He was travelling to Toronto, Canada. He would get only one chance to fully embrace these moments because as you know, First times happen only once. Any international flight after that would never be first time. All the time in the flight, he was preparing his first few sentences: The conversation with the Cab driver. He was trying to imagine the accent of the driver and how Joe will tell him where he had to go. It was thrilling and a bit scary. Well he enjoyed every single moment in that flight with a little bit of fear of unknown and finally landed in Toronto.

Well, life is funny. After everything from immigration and baggage claim was done, Joe went for the cab. You won't imagine, He did neither :). The Cab driver spoke in Joe's native language and he seemed to be from Joe's place in India. :) Well that was the first time Joe's "First time experience" was screwed so badly. :) Come on... he wanted to speak to an English guy. Well, but that actually gave him a lot of comfort as well and for the first time in his life, Joe truly experienced what it means when people say, the world is really a small place.

Beautiful Sunset somewhere in Nova Scotia, Canada

Since then a lot of first times happened. A few of them are worth a mention. I don't think joe would have ever imagined jumping off a flying plane from 5000 Ft above the ground if he had stayed back  home. Learning to swim was Joe's dream since he became sane, but that became a reality only when he was in Toronto among a lot of others who shared his dream of swimming. Upgrading the waterfall experience from Bhedaghat to one of the most voluminous waterfalls in the world, Niagara falls could not have been possible if it were not for Toronto.

This list could go on. But why am I telling you all this? Because all these first time experiences give a great feeling. They keep giving us joy even as days pass into weeks, weeks pass into months, months pass into years. This has become the "why" behind my travel dreams.

There are a lot of ways you can get various first time experiences, but I believe the easy and fun way is to travel. Whenever you travel to a new place, you invite a lot of first time experiences into your life. They may not always be great, but the risk is worth taking.

I must confess, I don't claim to always have a specific purpose for travelling and I am not always a true traveller. To be honest, a lot of times I am really a tourist, wanting to strike out as may places in a city as I could. Sometimes the sheer goal is to add that funky destination to my list of "Places I have already been to" so that I can flaunt my travel experiences when the topic crosses our chats.

Whatever the why may be, travelling always refreshes your mind and it gives you a sense of appreciation about all the possibilities and miracles the world has witnessed and will witness in the times to come.

This part of my life where I try to travel as much as I can, is called exploring the world. This is where I will share my enthusiasm about travelling to new places, trying different cuisines, exploring different cultures and anything else that the journey offers.

If you like this article, do share your thoughts. I would also like to hear your "why" for travelling.

Until then,
Happy Journey!
Banyan Bat.

P.S. Travelling inherently helps you increase your knowledge in the areas of your interest. Here's the evidence.

I accidentally stumbled upon this while I was visiting Biodome de Montreal in Montreal, Canada. I could not resist clicking a picture and I could not resist sharing it here :)

Smartphones, Nostalgia and a guide to buying a smartphone

I bought my first muzik(that's how they spelt it) phone in 2006 for INR 18000 :). Yeah that was a lot of money at that time,  probably from my first few salaries. It was a music phone craze at that time. I remember the joy of listening to "Chand sifarish jo karta hamari" on my first music phone.

This thing came with first of its kind in-ear earphones and a unique twisting camera. I used to clean it with the cleaning cloth of my spectacles :). I also remember keeping its plastic wrapper (the one that came with the packing) on for a long time. After all, it was precious, my precious.

As time passed, the caring got sidelined but I still enjoyed listening to music on that phone and flaunting it as a precious possession. But eventually as some more time passed, all sort of interest in that phone was gone and in a matter of couple of years, the phone was literally treated like a stone, thrown here and there when not used for calling. Yeah, headphones were gone and listing to music on this phone? huh.. no way. I needed an iPod.

So, after this phone was gone, spending another INR 18000 or so on a new phone, just in a couple of years was not an option. Budget was reduced and I went for a phone from another brand for a price of around INR 8000. Man! it felt cheap to go down on the INR stuff. That's the thing with style, standard and expenses :). Going down the ladder is a tough call.

I did not enjoy anything with that phone. Eventually, I bought the latest and greatest smartphone putting myself back in the front row of technology and smartphones. (Technically not, because I did not own the coveted phone from a great company named after a healthy fruit).

This new phone is great and has been with me for almost 5 years now. I must admire its make and the durability. But the truth remains. It never gave me the joy I felt when I bought my first phone. This phone is now the most outdated phone in the universe and is dying and I must buy a new smartphone. I wish to find a way so that my new smartphone buying experience will be as exciting and thrilling as it was back in 2006.

With a myriad of smartphones now available in the market, I was baffled. I had no idea which one to choose. I did what we do for almost everything now a days.Yes you are right, I searched on Google something like this: "smartphone buying guide". I got a bunch of results. Yes a bunch of results but no answer to my question. I was not looking for the smartest phone available in the market. I was rather looking for a phone that would make me feel as proud as I felt when I bought my first phone.

Disclaimer: Even if you buy the latest smartphone on the market, gold plated and bordered with diamonds, it will feel outdated and worthless in less time than you think. Hence, it should never be the source of your true happyness. I know there is an i in Happiness. :D

I also came across a few interesting quotes about smartphones:

"I fear the day that technology will surpass  our human interaction. The world will have a generation of idiots." - Albert Einstein

"Be smarter than your smartphone."

Not that they reflect my opinion about smartphones, but they were intriguing. Both these quotes got me thinking. Don't let your smartphone become smarter than yourself. So I thought should I buy an average phone? But how would that be any exciting? Sure I will save on some green stuff and that would feel good for some time. But eventually I will be stuck with a dumb phone for another five years or so. That should really be fine if I am not really into all this smartphone gig. I or anybody need not buy a smartphone to prove that they are smart or just because a bunch of companies are building them. It should always be my choice. So what if I challenged myself to be smarter than the smartphone I want to buy because that's how I feel. That sounds exciting. But is it feasible? Can I ever be smarter than a smartphone? Lets see.

I went on analyzing a few smartphones and I figured that all of them do the following things seamlessly one being better at something than another.

1. Contacts organization. 
2. Taking pictures and videos.
3. Helping you navigate around the world.
4. Durability, sturdiness and lightweight
5. Social Media, games and entertainment.
6. Screen resolution or the quality of what we see on the phone.

So, if I could become great at doing these things or if I could improve my human traits that resemble these smartphone features, I would be a compatible owner for that smartphone. And yeah, that will feel great. Most importantly, even though I will definitely keep growing smarter even after five years, while my smartphone eventually becomes dumb as compared to me, that would still feel great.

Therefore I decided, if I could achieve the following characteristics, I will call myself eligible for the smartphone of my dreams and I would buy it.

Contact organization.

The smartphones today are capable of keeping contact information seamlessly organized and available at the touch of a finger. The human brain that developed these so called smartphones is definitely smarter than them. But what about me? If I could remember 25 most important contacts in my contact list in and out, and am able to recall them effortlessly, I will call myself smart enough.

Taking pictures and videos.

When it comes to taking pictures and videos, trust me we are already smarter than the smartest phone on the market. When our brain and eyes work together to capture the beauty around, what emerges and gets stored in the back our our heads is simply amazing and no still image or video can match that. But capturing that image and showing it to someone else who can also appreciate what you saw is an art not everybody can claim. 

So what if you chose photography or sketching or painting? That's something you can improve. 

As I already have some interest in sketching...I am still a beginner, I chose it as a trait to focus on and improve. So if I can draw a few sketches and if I feel reasonably good about it, I am done.

Helping you navigate around the world.

This one is interesting. Navigation is at the heart of humanity. We have been navigating since I don't even know when. And the techniques that helped us navigate have evolved from the pole start to the current GPS technologies. But with these great advances in technology, somehow we have lost our own navigational capabilities that sometimes we find it difficult to even indicate the basic four directions.

So I thought why not work on some navigational skills. I decided to read and follow the paper map to navigate through a city instead of using the one available on my smartphone. I along with my friend did it while we were in New York and trust me it was a lot of fun. The sense of achievement we get is far greater than the Maps on our smartphones guiding us precisely through each step.

When I am comfortable reading a map of a new city reasonably quickly, I will call myself compatible to the smartphone world out there as far as navigation is concerned.

Durability, sturdiness and lightweight

A good smartphone is one which is durable and sturdy. But what good is it to have a sturdy smartphone in your hand when you can't even lift your grocery bag. :).

That was a little far fetched. But the idea is to achieve some challenging physical fitness goal. Once I have achieved my goal, I can check mark this trait.

Social Media, games and entertainment.

With the latest smartphones in everybody's hand, the world is now a community truly connected. With all the social media sites and various apps, we can instantly connect to anyone and even find our lost and forgotten contacts to reconnect and reunite. 

But sadly its all virtual.....

Even though we are constantly connected to each other on social media, we have lost our true human nature of social gathering. With the smartphones and all the smart devices, we hardly talk to strangers any more. Even couples have to plan to take out time for each other let alone strangers.

This does not seem to be good. Your breakfast should not be done looking at what your friend in Prague is eating in his dinner. Nor should your dinner be done looking at the pictures of your virtual friend whom you have not seen in the past 10 years enjoying his/her honeymoon.

Here my goal is a bit simple. I want to refrain from the social media apps and websites as much as I can, so that I can connect with my friends and family much like it should be. Personally. Period.

I guess in this case, the best idea is to fall back to the primal capabilities of a phone. Yeah, a simple phone call to a friend is far more enriching to the relationship than the thousand likes to the posts and shares on facebook.

Screen resolution or the quality of what we see on the phone

The smartphones today bring photos and videos to life like never before. Video calls on today's phones are so crisp and clear that we feel like we are together. But still its a virtual feeling and goes away just by a touch of a finger. 

What if our lives became as lively as the the screens of our phones. :) . I guess if we try to improve our own smart features rather than dreaming of buying the smartest phone on the market, our lives will definitely brighten up.

My smartphone should always be an aid to my own skills and capabilities not the crutches I use to navigate my life..... don't beat me for that :P

Now I feel like buying a smartphone. But I gotta do a lot of homework for that, So, I will whatsapp you or send you a facebook message, or instagram my selfie from my latest smartphone once I have one. :)

So if you like this article, grab your smartphone and hit like and share with friends. See, I know, you already have one.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,
Happy Learning!
Banyan Bat

Mission organize blog

It has been one month and ten days since my first post and I have written seven posts already. Even though its not much at this point. I never thought I would be able to go even this far. I feel great. I enjoyed writing every word in there and I hope you enjoyed reading them too.

Most of these posts were a part of my life called being a Software engineer. And I have learnt a lot in those 7 posts. If it were not for the blog, I might not have gone into details of so many things relating to the topics I touched in these posts.(Intentionally avoiding the names of topics to keep this post interesting even for those not interested in the software stuff). I will write a lot more about that part of my life.

Believe me, I am a procrastinator at heart :). If you ask me to do something, the questions that cross my mind are (In that order): So, is it necessary to do it right now? Is it really necessary? Can it be avoided? :). Yeah, you are right, I am lazy. But I have observed that since I have started this blog thing, it has given me something to be held accountable for and yeah, that feels great. It gives me a purpose to try new things.

Which means I will try different things and will bore you with the writings of those things. Simply writing posts one after the other on different topics will drive you crazy. Also, as more readers come across this blog they need to be able to find a place to start and read posts which interest them the most. (I am being optimistic here). After all,

"It doesn't hurt to be optimistic. You can always cry later." - Lucimar Santos De Lima.

So I created a navigation bar at the top of this blog. The first tab/label I added is the About label which tells you about Banyan Bat and his purpose behind this blog. The about section may be updated occasionally as the purpose and the meaning of this blog evolves over time.

The second label on the navigation bar is a category on which I have written some post. As I write posts you will see (optimism again) new categories added to the navigation bar.

So, as a reader, if you are interested in a particular category, you will be able to dive right in. Or if you are a casual reader and wanna scan through the topics, you will be able to do that too. And yeah, if you are good at all the things I write about, and many more things, you will be able to read them all at the Home label on the navigation bar. Please don't forget to guide me on the things you know and of course correct me or enlighten me even on the topics that I have written on.

Until then,
Happy Learning!
Banyan Bat

Bubbly goes to Las Vegas - Insertion sort

"I got a letter from the guy who stole my identity. He says he's giving it back, because ever since he took it, he hasn't been able to win one hand at poker"

As you already know by now Bubbly is cute. You also know that she had a thing for chocolates and suffered her share of consequences of over indulgence. She learnt her lessons and she has now learnt to control her urge for chocolates. Now she is always this beautiful smiling small Bubbly:

So no more rescuing Bubbly from her troubles. Well, hold on! Some people have this thing for troubles. They know all the means to get into trouble. Bubbly is one of them. :) But after all, she is our cute little Bubbly. We gotta save her.

Looks like Bubbly has gone too far in celebration of her happy times. Last time Bubbly was seen, she was playing poker at The Venetian, Las Vegas.

As you already know, Bubbly has issues with arranging things in order. So to help Bubbly win, our job is to make sure that she holds her cards in order and of course, hides them well from the fellow players. Considering that I am the worst Poker player, that is all I can do to help her here. 

The approach that we are going to use today to rescue Bubbly out of her newfound trouble is again something that has been around for ages and people from all the walks of life and age groups must have used it sometime in their lives.

Okay, let me come straight to the point. If you have played any cards game, you have used this technique.

Yeah, Don't give me that poker face now, I know you have been playing cards, behind the back of your parents. Don't worry. Chances are, they had done it too when they were young. :P

So, let me first congratulate you as you already know this technique and you don't even need to learn it. OK, don't be too relaxed as well because we still need to do some work. We need to draw upon our memory reserve and turn it into something Javaish, Cish, C++ish.....you get the point.

Lets say, Bubbly has following cards in her left hand:

Our job is to help Bubbly arrange these cards in ascending order for ease of access.

Step 1: 

Bubbly has got  a 3 of heart as the first card, next she has got a 2. Okay, so lets take this 2 out into the right hand.

Step 2: 

3 is bigger than 2, so let me first move 3 one position right.

Step 3: 

Now let me put 2 in the empty space.

Step 4: 

5 seems to be Ok as far as its left side is concerned.

Step 5: 

4 is less than 5. Or looking at the cards on the left, there is one card (5) bigger than 4, so let me grab 4 in the right hand.

Step 6: 

5 is bigger than 4 so let me move 5 one position right.

Step 7: 

3 is less than 4, so let me put 4 in the empty position just to the right of 3.

Step 8: 

Looking at the cards on the left of 1, starting from the immediate left card, we can see that these cards are bigger than 1. So let me take 1 in my right hand.

Step 9: 

5 is bigger than 1, so let me move it one position to the right. 4 is bigger than 1, so are 3 and 2. So all of them have to move one position right. Making the cards in the left hand look something like this:

Step 10: 

There are no more cards on the left, so let me put 1 in the empty spot. 

Here's our sorted hand of cards. Now no one can stop Bubbly from winning this Poker game.

This is nothing but insertion sort, because you are inserting each element in its sorted position.

Lets label a few things for creating our Insertion sort Algorithm:

Starting from the second element, put each element into the already sorted array on the left, in its sorted position.

To do this, we keep each element in a temporary variable, compare it with each element in the already sorted array and until we find an element smaller than the element at hand, we keep moving them one position to the right. When we get our smaller element, we put the element in the temporary variable, just after the smaller element.

Insertion sort is now under your belt.

Your little knapsack of Data Structures and Algorithms now looks something like this:

Can you compare these three sorting algorithms? Can you find out which one is the better? Ask as many questions as you can ask. Here are a few for starters:

1. What is common among these three algorithms?
2. Is one faster than other?If yes, which one?
3. Is one simpler than other?
4. What happens if the array is too big or too small?
5. What happens if the array is already sorted?
6. What happens if the array is reverse sorted?
7. What is not so common among them?

As a teaser trailer to these questions: The biggest difference between Insertion sort and the other two sorting methods we saw is that, insertion sort does not do a swap.

As usual, comments/appreciation/criticism(a constructive one of course) everything is most welcome and appreciated.

Until then,

Happy Learning!

Banyan Bat