An Inspirational talk by Arvind


This one experience I had to share it openly because, each and every point what Arvind bhaiya (brother) told applies to me a lot. Thanks to Arvind bhaiya for spending a lot of his time with us.

For those, who don’t know Arvind, he is my senior who is an active Foss Member in my college. He is currently pursuing his masters here in Amrita University and he got a chance to continue his masters in Amsterdam. He will be leaving from India in a few weeks.

Most of the points what he mentioned applies to me in most of my daily life. Even some of the experiences which he mentioned are very similar to my kind, and thanks to him, that I got a solution after all for all my failures till now.

The thing what I learnt from his session is that no matter how many times you fail, never give up, and do try to rectify the mistakes what you did previously. In my case, I got the realization a bit lately after messing up one full year doing nothing, not only I didn’t make any progress and in addition to that I messed up my academics so badly.

Yeah, what Aravind bhaiya said is correct, when ever you have some problems you have to share it with some one like family members or friends. So that you can get a solution within no time. Instead of that if you don’t share it with anyone, you will end up messing things like me.

I never do prefer anyone to repeat the mistake again like this. Never think there is no one to help you around with your problems, there is always someone to help you, but never think no one is there to help you out during hard times. Always there is someone to help out and never think that you never have any friends. That is one of the worst things which you can ever think, and if you think so you are the most stupid guy in the world. Unless you open up to some one, you can never be happy at what ever you do. Without knowing this thing, I did misunderstand my mentor and always thought I was right. I am really sorry for the way, I behaved with you till now.

And when it comes to computer games, again what he said is exactly correct. I am a freaking hardcore gamer, the example what he gave is nothing when compared to what I did and the solution what he gave to us, also completely applies to me. And friends, yeah it did work for me. I did format my system and now I did reduce the usage of my computer completely. I don’t say that using computer is not wrong, but using it for purposes which will not be of any use for us.

Let me give me an example of what I did, a live example: I did played games even before the night of my final exam also. You know, how much I was addicted to gaming, one night I sat and completed a game sitting for 15 hours continuously not even for getting for food and after that I faced the consequences of it which are worse than anything. Trust me gaming is one poison if you can’t keep it in a control.

Finally what I learnt from the session was, never ever give up, even when you are in tough times. You always have a way to come out of the situation, if not do search for the solution and do go express your situation to some one, so that you can get a solution.

Aravind bhaiya, thanks a lot for the session, it really helped me understanding my mistakes. I think I should have met any of the seniors long back and should have explained my problem. Really thanks for a worthy session.

Oh yeah, forgot to say, let’s all congratulate Aravind bhaiya, because he will be leaving for his Masters to Amsterdam. Hope you will have a really good time over there during your masters.

Insertion Sort Algorithm


Insertion Sort

A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quick sort, heap sort or merge sort algorithms. However, insertion sort algorithm provides several advantages:

  • Simple Implementation
  • Efficient for smaller data sets.
  • Efficient for data sets that are already substantially sorted: the time complexity is O(n+d), where d is the number of inversions.
  • More efficient in practice than most other simple quadratic algorithms such as selection sort and bubble sort algorithms.
  • Stable – doesn’t change the relative order of elements with equal keys

Input

A sequence of n numbers ( a1, a2, a3, ………, a)

Output

A sorted array of elements ( a1′, a2′, a3′, ……., an’ ) of the input sequence such that a1′ <= a2′ <= a3′ <= ………. <= an’

Algorithm

Algorithm for Insertion sort (n elements) is given below:

for j ← 2 to length[A]
    do key ← A[j]
        Insert A[j] into the sorted sequence A[1 - (j - 1)]
        i ← j - 1
        while i > 0 and A[i] > key
            do A[i+1] ← A[i]
            i ← i – 1
        A[i + 1] ← key

Explanation

Let us take the example of a list of numbers { 5, 2, 4, 6, 1, 3 }. Now if we take a look at the above algorithm, the index j indicates the current card  being inserted into the array. At the beginning of each iteration of the ” outer for loop ” which is indexed by j, the sub-array consisting of the elements A[1 ….. (j -1)] constitute the currently sorted hand, and elements A[j+1 …. n] correspond to the pile of cards still on the table. In fact, elements A[1 …. (j – 1)] are the elements originally in the positions 1 ( indexed 0 ) through (j – 1), but now in sorted order.

Analysis of Insertion Sort

Insertion Sort Algorithm      Cost Time
for j ← 2 to length[A] c1 n
do key ← A[j] c2 n-1
Insert A[j] into the sorted sequence A[ 1…. (j – 1) ]  – n-1
i ← i – 1 c4 n-1
while i > 0 and A[i] > key c5 Σ Σj to n = pow(2, tj)
do A[i+1] ← A[i] c6 Σ Σj to n = pow(2, tj-1)
i ← i – 1 c7 Σ Σj to n = pow(2, tj-1)
A[i + 1] ← key c8 n-1

We start by presenting the Insertion Sort procedure with the time cost of each statement and the whole number of times each statement is executed. For each j = 2, 3, 4, 5, ………, n, where n is length[A] i.e. length of the array. We let “tj” be the number of times the while loop test in line 5 is executed for that value of “j”. When for or while loop exists in the usual way the test is executed one time more than the loop body. We assume that comments are not executable statements and so they take no time. The running time of the algorithm is the sum of running times for each statement executed; a statement that takes “ci” to the total running time. To compute T(n) , the running time of Insertion sort , we sum the products of the cost and times columns, obtaining:

T(n) = c1(n) + c2(n-1) + c4(n-1) + c5(n-1) + c8(n-1)

T(n) = (c1 + c2 + c4 + c5 + c8) n – (c2 + c4 + c5 + c8)

This running time can be expressed as an+b for constants a and b that depend on the statement costs ci , it is thus linear function of n. If the array is in reverse sorted order that is decreasing order the worst case results. We must compare each element A[j] with each element in the entire sorted sub-array A[1 …. (j-1)] and so tj = j for j = 2, 3, ……, n.

Σ(j=2 to n) j = [n(n+1) / 2 ] -1

Σ(j=2 to n) (j-1) = [n(n-1)/2]

We find that in the worst case , the running time of insertion sort:

T(n) = c1 n + c2(n-1) +c4( n-1) +c5 ( (n(n+1)/2)-1) + c6 ( n(n-1) / 2) + c7 (n(n-1)/2) +c8 (n-1)

T(n) = ([c5 /2] + [c6 /2] + [c7 /2]) n x n + (c1 +c2 +c4 +[c5/2]-[c6/2]-[c7/2]+c8) – (c2 + c4 + c5 +c8)

The worst case running time can be expressed as an2 + bn + c for constants a , b and c that again depend on the statement costs ci; it is thus a quadratic function of n.

Complexity of Insertion Sort

The complexity of any algorithm can be expressed in three ways:

  • Best case complexity
  • Average case complexity
  • Worst case complexity
Best case Complexity

The best case complexity can be calculated where the array is already sorted or the required element is in the first position. Calculating the best case complexity gives us the lower bound of the time. In this case, the insertion sort algorithm has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

Best case complexity = O(n)

Worst case Complexity

The worst case complexity can be calculated by assuming that the element is in the last position or the element is not even present in the array. In this cases every iteration of the inner loop will scan and shift the entire sorted sub-section of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2))

Worst case Complexity = O(n²)

Average case Complexity

The average case complexity can be calculated by taking the average of the best case and the worst case complexities of any algorithm.

FOSSMeet’14 @ NIT-Calicut


Hello amigos’!!! It’s been a long time since my last blog post. The following post I should have posted long back when we went for the FossMeet. This happened in ,

This time FossMeet was simply awesome because nothing went as we planned and all things changed in within no time. 😉 Though we didn’t get enough people from my batch-mates, it is fulfilled by the juniors. 🙂

We started from our college by bus around at 9 PM and thought of sleeping in the bus. But things will never happen the way we think right? Right after the bus left the campus gate all of us started singing songs and dancing in the bus. It was like a remix of songs me because in the front it goes with Malayalam songs with my batch-mates and in the back it was Hindi songs from my juniors. That way we spent almost all the time in the bus by singing songs. 😛

The next day it was really a horrible situation for us, because we didn’t do the registrations in advance, because of that reason we slept for 3 hours near the NIT Calicut campus in the bus . Though we tried to get the accommodation, it didn’t happen since the accommodation all starts at 6 AM in the morning.

Day 1 (14/02/14):

We had to split among ourselves because we planned to cover all the talks and workshops which we can attend. And all of us planned to attend Jackson’s talk on How to contribute to Gnome which was scheduled in the afternoon. I went to attend the Git hub workshop. Though it was a beginner level workshop, I had fun during the workshop. In the middle of the workshop it was Jackson calling me saying get all the juniors along with you to my talk. 

Jackson’s Talk

First of all, congrats to Jackson for his talk. Though it was his first talk, he made it really a good one. His talk was on the topic How to Contribute to Gnome-music. That was a really good talk for almost all the beginners who are interested in contributing to Open Source.  After his talk, during the QA time, we had a small discussion which led to a debate on the topic What do you mean by a good programmer. After his talk was over, we again dispersed in groups to go attend the remaining workshops.

Unfortunate accident

It was around 4 PM when we heard the news that a student of NIT Calicut passed away because of a wall fell on him while he was playing. After that incident, the organizers of FossMeet decided to cancel the event. May his soul rest in peace.

Then it was a really tough time for us to decide what should we do the next day. We had a discussion among ourselves and decided to go to the nearby places like planetarium, beach, etc.

Foss Rocks :)

Day 2 (15/02/14):

We decided to go to the planetarium in Calicut. It was around 10 AM when we left the NIT Campus to the planetarium. It was real fun in the planetarium. It was an amusement park as well as planetarium. There we had a lot of snaps. And after that we went to the planetarium for the show. Guess what the show was in Malayalam 😦 but had fun watching the video listening to music. 😀

Myself, Tony and Sakshi

Next it’s time to refuel our stomach :P. So decided to go to Paragon the best hotel for chicken biryani 😀 . It was really tasty (yum yum :P). After refueling our stomach’s, we thought of having some music without getting bored in the bus. Thanks for Jackson who decided to buy Honey Singh Songs, with which we had a real blast in the rest of the bus journey. 😉 That is when all of us started singing and dancing together for the songs which are being played in the background. 😛

Next we went to the Calicut beach :D, thought of having some swim in the beach, but got strict instructions from Tony not to enter the water. I thought, I would get bored there staring at the water and the waves, but thanks to the juniors we played kabbadi. There we had some snaps and then started from the beach at 6 PM back to the college.

Return Journey:

After a day full of fun, finally it is time for us to get back to college. In the middle we had a pit stop at a dhaba near to Calicut for refueling. 😛 After that again it was songs and dance in the bus. I had a real good time in the bus journey, got a chance to interact with all the juniors and how they feel here and all. Myself and Juniors had some real fun during that discussion. 😀

That’s it buddies, this is how FossMeet’14 happened for us. It was really awesome and had some real fun. Thanks for Tony, Tina and Anu for getting the permissions and all the arrangements. Forgot to say, thanks to each and every one who made the FossMeet trip one of the most best trips for me.