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

A Silly Mikstake ... Selection sort

Did you ever do a mistake and suffer the consequences? And feel guilty of your predicament? In that moment of guilt, you decide that you are not going to do that mistake ever again. You are full of confidence that sure as hell, you are not going to repeat it again. It was a pain in the @$$ after all.

As time passes, you forget the consequences altogether and you are there again. Where? Yeah right there, in the little predicament of yours :). What would this be called? A silly mistake, right? and what would you call yourself? Silly of course.

In the last post we met bubbly and saw how crazy she is about chocolates. Yeah yeah I know you went through all that pain to get her out of trouble. There she is again. Yeah that's why we call her silly now.

Last time when we rescued bubbly, the ordeal she went through was tough on her and us alike. A lot of swapping around in her belly. And if we have to do it again and again, we must find a better way to deal with it.

So this time I needed to look for a solution which was a bit smarter and less painful. I looked around to see if any smarter way already exists. To my surprise, it was there all along. I myself must have used it in my childhood. You too must have used it or at least seen it working.

Baffled? Don't Be!

Ever seen how a kid selects her/his chocolate when presented with multiple options?

When it comes to chocolates, kids have two things in common:

1. They want the biggest(Bigger the better).
2. They don't trust the world around.

So in this untrustworthy world of adults, how would a kid get the best and biggest chocolate she can? Trust me, kids know better. So lets say a kid is presented with the same chocolates that Silly (a.k.a Bubbly) ate.

The kid would anyway grab the first chocolate she gets. She will hold on to it tight (as if the world is against her. I love the look on the face of a kid at that moment. Who doesn't? ) while she compares it with the next available chocolate. 

And if she finds another chocolate bigger than the one she already has, she will grab that chocolate. But wait, technically the kid has not decided on the chocolate yet. She will continue to grab the chocolate she thinks is bigger than the earlier ones. So at the end, when she has the biggest chocolate with her, she will then give up the small chocolate(Yeah I know, she wont give anything back).

The analogy may not be 100% accurate or correct, but it conveys one important method to sort. Selection sort. Well it revolves around selecting the right candidate.

Lets summarize the steps:

1. Grab the first item you get.
2. Compare it with the rest of them looking for the smallest item(Note: I hope you are not a kid and won't always go for the motto: The bigger the better).
3. Swap only at the end when you know that this is the biggest smallest item.

Lets apply a child's mind and see how far we can go:

The problem and the goal are similar to the last time. Here they are for your quick reference:

The problem: Silly has eaten chocolates out of order (AGAIN!!!!!) causing her scales to be stretched. This is painful and uncomfortable for her.

What needs to be done: We need to find a way to rearrange the chocolates in such a way that the smallest chocolate is in the smallest scale and the largest chocolate is in the largest scale: What we want is a happy Silly as shown in the following image:

Operation rescue Silly again begins

Agreed that misplaced chocolates in Silly's tummy are painful to her, but so are frequent swaps. Our goal here is to relieve Silly out of her pain with less pain in the process.

So as usual we start with the first(smallest) scale. Mark the first chocolate(3). Hold on to it temporarily. I did not mean to get technical just yet but for ease of association, you can relate it to putting the first chocolate in a temporary variable and marking it's scale for future reference. As a kid, you hold this chocolate in your left hand. Thats much better to imagine. :)

The situation looks something like this:

Now lets compare this chocolate(temp = 3) with the chocolate in the next scale(2). As 2 is smaller than 3, we release the value 3 and grab chocolate 2 making temp = 2. We also change our future reference mark.

Next, compare temp = 2 with the chocolate in the third scale(5). 5 is greater than 2 so we are good here. No changes and we move on.

Next we compare temp = 2 with the chocolate in the forth scale(4). 4 is greater than 2 so again no changes. Lets move on.

Lets compare temp = 2 with the chocolate in the fifth scale(1). 1 is smaller than 2 so we need to change the chocolates. grab 1 in the left hand or make temp = 1 and yeah, don't forget to mark the scale for future reference.

This was our last element and hence, we have completed our first pass through Silly's scales and we have found the smallest chocolate which will go in the first scale of Silly. So just one swap here. Swap the chocolate in the first scale(3) with the one in the marked scale which happens to be the fifth scale in our case.

So after our first pass through Silly's stomach, we have put the smallest chocolate in the smallest scale, and that too using only one swap.

As the first scale is already sorted, in the next move we will only pass through unsorted 4 scales and then in the next pass only through 3 scales, subsequently sorting chocolates forward. So Silly starts feeling much better after each pass with fewer swaps. See below the improvement in Silly's condition after each pass:

Pass 2:

Pass 3:

 I have deliberately not highlighted the swapped scales here. If you are really interested, you would find it out by doing the mental passes yourself. That should ideally strengthen the understanding.

Pass 4:

Pass 5:

As you can see, Silly has got her relief just after the third pass, but still our algorithm has no way to find it out. It has to continue with the passes, although no swaps will be needed.

Now, hopefully you are clear with the steps required to do a selection sort on a bunch of numbers. You already knew that. Just needed some association.

As you must have also noticed, when we helped Bubbly out of her trouble last time, each comparison could cause a potential swap. So if we consider the worst scenario where the items are arranged in an exactly opposite order, each comparison in each pass would require a swap.

While here, when we rescued Silly, we did just one swap in one pass through Silly's tummy. Even in the worst case, we would require a single swap in one pass. And there may be passes where we don't even do a single swap. This drastically reduces the number of swaps required.

Hence, even though the number of passes and comparisons in both Bubble sort and Selection sort tend to be on same lines, the number of swaps is drastically reduced in Selection sort.

As usual, write your own code, be creative, associate with your personal life and recall periodically and most importantly, have fun!

Will Silly repeat her mistake again? Will we be able to rescue her again? Will we be able to reduce the troubles she goes through each time? To find out, stay tuned.

Did you know?

While I was deciding the names for my caterpillars, I thought lets name then based on the sort algorithms, so for Bubble sort, I had Bubbly, for Selection sort, I initially chose Sili and for insertion sort I chose XXXXX (We are not there yet :P) . Although finally Silly better suited her personality. Just out of curiosity, I did a Google search on Sili and found out some amazing facts:

In a country called Samoa (I did not know there was a country named Samoa), there is a village called Sili.

And by the way, Samoa is home to the Flying fox. The bat. Yes bat, Bat, BAT, The Bat, THE BAT....come on you know I love bats :).

The large flying fox is among the largest species of bat. It weighs 0.65–1.1 kg (1.4–2.4 lb) and has a wingspan of up to 1.5 m (4 ft 11 in). Its head-body length is 27–32 centimetres (11–13 in) - source is our beloved Wikipedia.

After all, learning does lead to more learning.

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

Until then,

Happy Learning!

Banyan Bat