insertionSortCard

Best example of insertion sort is sorting deck of cards. .. As you see in the figure, say we have 2,4,5 10 and 7 clubs in our hand and we have to sort it .
As we know, we will take 7 clubs and place it between 5 and 10 clubs. Hence, for each card we need to swap the cards before it and place the key card in place .

 

Before the analysis , lets have a look at pseudo code of insertion sort. For input array A

 


INSERTION-SORT(A)

for j <-- 2 to length [A]

do key <-- A[j]

i <-- j - 1

while i > 0 and A[i] > key

do A[i + i] <-- A[i]

i <-- i - 1

A[i + 1] <-- key

&nbsp;

 

I tried implementing the same in C++. Here is the code

 

 

#include <iostream>

using namespace std;

int main()
{
int arr[] = {5,2,4,6,1,3};
int arrSize =  sizeof(arr)/sizeof(arr[0]);
int key;
int i;
for(int j=1; j<arrSize; j++)
{
        key = arr[j];
        i = j - 1;
        while(i >= 0 && arr[i] > key)
        {
                arr[i+1] = arr[i];
                i = i - 1;
        }   

        arr[i+1] = key;

}

for(int i=0; i<arrSize; i++)
cout << arr[i] << " " << endl;
return 0;
}

Output is :

insertionSortOutput

Before we start our analysis of the insertion sort, we will see how many times each statement runs.

 


INSERTION-SORT(A)

for j <-- 2 to length [A] ----------------------------  runs n times

do key <-- A[j] --------------------------------------  runs n-1 times

i <-- j - 1     --------------------------------------  runs n-1 times
                                                       n
while i > 0 and A[i] > key --------------------------- ∑ tj
                                                       j=2
                                                       n
do A[i + i] <-- A[i]  -------------------------------- ∑ tj - 1
                                                       j=2

                                                       n
i <-- i - 1 ------------------------------------------ ∑ tj - 1
                                                       j=2
A[i + 1] <-- key ------------------------------------- n-1

&nbsp;

Now, lets get into the analysis part.
Okay, In each statement , we do some operations as well i.e – increment, decrement, counter — all those are considered to be constants. Hence we name constants from c1 to c7
And also, tj is the function which does while loop operation .
If the input is already sorted, there would be no in-swapping takes place. i.e. While loop will never be executed. Since while loop is inside FOR loop which runs from 2 to n , we enclose it with sigma j = 2 to n.
Hence the equation would be
What could be the Best case ?? — A sorted input
and what could be the worst case input . — Input sequence in reverse order.

 

These 3 screenshots will explain how insertion sort is O(n) in best case and O(n square) in worst case. 

 

 

BestCase

insertion_sort

worst case

 

This you tube video will be helpful to understand the same

https://www.youtube.com/watch?v=yXwFrc5GS6A — click the view the video 

 

Learning Year – 2014 !!!!

Posted: December 31, 2014 in Uncategorized

Started of the year with lot of resolutions ….. 

 

resolution

Speed Cubing

rubiks

In Feb, i entered into a new world called speedcubing. Never heard it before. Never solved a rubik cube before. Feb 18, 2014 was a start. Initially, i just started off with “how to solve rubik cube” video in you tube. When i started practicing it , things started to be serious and fun as well.
badmephisto.com- took me from 8 minutes to 28 seconds. Thanks and salute to badmephisto.

 

How to Solve Rubik’s Cube Blindfolded

blindfold

 

 Everytime, when i see a blindfolded solve in internet , it always looked like a magic. I thought , i would never make it. But, this link made me understand that i was wrong. Memos, formulas and other stuff .. Ufff.. Nov 18, 2014 i got my first rubik blindfold solve.

Coursera 

mooc

 

One of the interesting medium to learn about softwares and related stuff is coursera. Enrolled in many courses , but didnt finish even one with certificate :P.
however, it was a very good learning experience . R programming was new to me. STarted with the basics of data analytics and also some python stuff.

 

Jquery

jquery

Everytime when i take javascript , i could not move more than 5 pages in book . Jquery changed that interest. Started watching my favorite programmer – Alex’s video in youtube for jquery and completed till 40/200. It was a wonderful start for basics and was very helpful while programming front end stuffs.

 

Project Euler Problems

 

projecteuler

 In early december, moved back to that old black console (c++) and started solving problems on project euler. Initially , the problems were easier and simillar. But, when i moved on things were getting complex and there were lot of Project Euler Problemsthinking and learning involved. Got more ideas on sieves, searching, sorting, dynamics and other stuff. solved 50 problems on it and ranked less than 500 in india out of 8k odd people.

 

Creating Android App

  android

 

Is that very difficult to create an android app ? Wanted an alarm and remainder app in my own way. And i designed it with online help.

 Learn German

 

germasn

 

 

 Duolingo made it as a routine and learnt it for 30 days . Few words in German got set into my mind .

Chess Cube 

chesscube

One more addictive website.. chesscube.. Hmmm.. what to say.. Restricted myself to one game a day.. Very interesting to play with unknown persons. But, it eats lot of time. Also, went thro some videos of Akobian (French Defense, Ruy Lopez) just to maintain my cubits in chesscube. and also used chess android app level 4. 4/12 was too low .. but i wanted to play level 4 until i gain good confidence on it.

Blogging  

blog

And at last, blogging.. Couldn’t post much.. Thats gonna be my new year resolution. Will try to share as much as i can . !!!

 

newyear

Happy Learning !!!

On an occasion i had a file with words listed one by one and i wanted to sort the file in lexicographic order. Since i work in linux machines , its just 1 command . `cat filename | sort ` to sort it in lexicographic order. But i wanted to do it in c++.  I tried googling for suggestions and found out that radix and bucket sort would help me out. And then i tried implementing the concept of Radix MSD to arrive the result. Sharing the code. I have added inline comments in the program. Hope it helps  (Note: i just wanted to arrive with the solution.. Not much concerned about efficiency of the program :-))

#include <iostream>
#include <map>
#include <vector>
#include <fstream>

using namespace std;

int main()
{

	vector<string> words;

	map<char,vector<string> > bucket;
	map<char,vector<string> > ::iterator it;
	bucket.clear();
	vector<string> tempVec;

	// initializing map with null vector and empty for variable length string
	bucket[' '] = tempVec;
	char ch;
	//for(int i=97; i<123; i++)
	for(int i=65; i<91; i++)
	{
		ch = i;
		bucket[ch] = tempVec;
	}

	words.push_back("jump");
	words.push_back("sit");
	words.push_back("carry");
	words.push_back("run");
	words.push_back("site");
	words.push_back("runner");


	/*cout << "init" << endl;
	  for(int k=0; k<words.size(); k++)
	  cout << words[k] << "  ";
	  cout << endl;*/

	// finding the maximum character
	int max = 0;
	for(int i=0; i<words.size(); i++)
	{
		max = (max > words[i].length())?max:words[i].length();
	}

	// loop from max char till first char 
	for(int i=max-1; i>=0; i--)
	{
		//cout << "Running for Phase " << i << endl;
		// loop through the entire vector
		for(int j=0; j<words.size(); j++)
		{
			string word = words[j];
			int temp_len = word.length();
			// there may be possibility that word boundary is less than max
			if(temp_len < i)
			{
				// push into the "" bucket
				//cout << "Pushing " << word << " into bucket " << "[empty]" << endl;
				bucket[' '].push_back(word);
			}
			else
			{
				// index exists .. Hence check the char
				char temp_char;
				temp_char = word[i];

				// insert into map with temp_char, word
				bucket[temp_char].push_back(word);	
				//cout << "Pushing " << word << " into bucket " << temp_char << endl;

			}


		}
		// end of this loop, all the words are inserted into corresponding buckets
		// clear the input vector -- because we are going to change the order
		words.clear();

		// iterate through the keys and write the order into input vector
		for(it=bucket.begin(); it!=bucket.end(); it++)
		{
			tempVec = it->second;
			for(int k=0; k<tempVec.size(); k++)
				words.push_back(tempVec[k]);

			tempVec.clear();
		}

		/*cout << "After bucket insertion words are  " << endl;
		  for(int k=0; k<words.size(); k++)
		  cout << words[k] << "  ";
		  cout << endl;
		 */


		// now we have the correct order of the phase .. hence clear the bucket
		tempVec.clear();
		for(it=bucket.begin(); it!=bucket.end(); it++)
		{
			it->second.clear();
		}

		//cout << endl;


	}
	cout << "Answer is " << endl;
	for(int k=0; k<words.size(); k++)
		cout << words[k] << endl;


	return 0;
}

[ALGORITHM]
1. Read the words and push into vector
2. find the max value by iterating the vector and finding length of all words
3. Iterate from max to 0
4. take each words first letter and push into corresponding bucket
5. Iterate through the buckets and save it as input word list order
6. After 0th Iteration , input vector will have the result.

[EXPLANATION]

step – 1
words pushed into vector

jump, sit, carry, run, site , runner

step – 2

finding the maximum length string
it would be runner – 6

step – 3

Iterating from index 5 to 0

ITERATION – 5 :
Note : if the word length is less than index , we need to push in empty bucket(‘ ‘)

‘ ‘ – jump,sit,carry,run,site
r – runner

Hence, array order will be – jump, sit, carry, run, site

ITERATION – 4 :

4th index of the words carry and runner are [y] and [e]

‘ ‘ – jump, sit, run, site
e – runner
y – carry

Hence, array order will be – jump, sit, run, site, runner, carry

ITERATION – 3 :

3rd index for the words jump, carry, site, runner [p],[r],[e],[n]

‘ ‘ – sit, run
e – site
n – runner
p – jump
r – carry

Hence array would be sit, run, site, runner, jump, carry

ITERATION – 2 :

2nd index for the words sit, run , site, runner, jump, carry are [t],[n],[t],[n],[m], [r]

m – jump
n – run, runner
r – carry
t – sit, site

Hence array would be jump, run, runner, carry, sit, site

ITERATION – 1

1st index for the words jump, run, runner, carry, sit, site are [u],[u],[u],[a],[i],[i]
a – carry
i – sit , site
u – jump, run, runner

Hence array would be , carry, sit, site , jump, run, runner

ITERATION – 0

0th index of the words are [c], [s], [s], [j], [r], [r]

c – carry
s – sit, site
j – jump
r – run, runner

Hence OUPUT : carry, sit , site , jump, run, runner

Good bye wake me up

Posted: November 19, 2014 in Health
Tags: , , ,

Are you the kind of person who keeps almost 10 to 15 alarms in your phone just to get up in the right time?

Are you the person to snooz alarm 5 to 10 times before getting up?

Forget it. . Thinks have changed.

Have you ever heard this quote “if you wanna get up in first alarm, just keep the alarm  clock away from your bed”

Now an android app made it real. From now there is no wake up alarm for us . Only we have a
WALK UP ALARM.

You can keep the phone near the bed , but once the alarm triggers it can be switched off only if you walk ten steps with your phone. Otherwise it ll be keep ringing.

I personally tried it today and i got up in the first ring . Thank you walk me up team for a great innovation.

 “Are we really utilizing our time EFFICIENTLY ?”

Yesterday i watched “the last lecture” video by Mr. Randy Pausch that triggered few things in my mind. Do we really know , what we will be doing tomorrow 5.30 . Atleast, do we plan for that. For majority of us, answer is no. Atleast, for me !!!

After watching the video, i thought of finding a way through which i could find the golden time that am wasting through outt my life. Simple google search on apps lead me to 2 important android apps.

1. Routinely – https://play.google.com/store/apps/details?id=com.braavos.apps.routinely&hl=en

2. Schedule Planner – https://play.google.com/store/apps/details?id=com.intersog.android.schedule&hl=en

For ios users we have daily routines app which does the same stuff.

Firstly, the app routinely helps us to decide on what are all the things that we really need to do on daily basis . Hence, we can come up with our own list and check it up after completing it on day to day basis.

Second one is quiet interesting. Schedule Planner app helps us to list our stuff by dividing into categories. There are two tabs. Planned and Actual. You can plan your work, and you can move it to actual after performing it. In the pro version, we can edit our categories. Using this app for 1 week, we can easily find out on how we are wasting our time. and how we can manage it on useful stuff.

I could really see some changes in my learning process. You can try and share your comments as well.

It was a dream for me to learn 3 x 3 blindfold. Since , i was not good in memory skills , i thought it would never happen. But , after watching this video, everything changed and i learnt blindfold in a day .

Just in case, if you dont get a good clarity after seeing Zane C’s Video , i would really recomment to watch Badmephisto video given below

Since there are plently of methodologies covered in the video , i would like to stress more on the memorization part. Initially, the memorization part will take more time than to solve the pieces .

There are many ways through which you can memorize the piece orientation. People who are good in memory , use visual memory to memorize the pieces. But, visual memory wont last for a long time. And , it really needs good memory to remember all piece orientations.

Some People use objects to remember each piece. Even for this, we need a good memory because there will be around 15 to 20 object we need to remember with a connection.

Especially for the people like me, the third method is so suitable . We will label each piece with a Letter. Starting from UB as A we will move anti clockwise . In this case , you need not remember all the labels initially,

UB – A
UL – B
UF – C
UR – D

FU – E
FL – F
FD – G
FR – H

RU – I
RF – J
RD – K
RB – L

BU – M
BR – N
BD – O
BL – P

LU – Q
LB – R
LD – S
LF – T

UF – U
UL – V
UB – W
UR – Y (Not X , because we can form more words in Y than X )

For the initial solves, its fine to remember only 6 pieces

UB – A
FU – E
RU – I
BU – M
LU – Q
UF – U

From these pieces, we can appropriately move in anti clockwise direction and increase the alphabet .

Similarly, we can do it for Corners :

UBL – A
UFL – B
….
….
….
….
….
DBL – Y

Hence, we just need to remember a letter , rather than remembering the position.

And also, once you form sequence of letters , we can form words with it. For Ex:

C D L M T S W can be randomly made as

CoDe LiMiT SoftWare (am a CS Engg :P)

Hence, we can simply say :

2 sentences = a blind fold solve.

All we need is to move one piece at a time and create words with the corresponding notation.

Very new to python Programming . I tried installing python 2.7 in my linux machine (ubuntu). Unfortunately , python 3 was already installed in the system.

For parsing the twitter tweets using python, i had to install oauth2 in my machine. i spent almost 2 to 3 hours doing it . Got almost 5 different kind of packages from internet and tried installing it.

Also installed additional libraries. PIP and all stuffs . But still, it didnt work. I got the same error as below

Traceback (most recent call last):
File “twitterstream.py”, line 1, in
import oauth2 as oauth
ImportError: No module named oauth2

At last , i found that the error was occuring because of the 2 differnt python versions in my system.

Then i started locating python directory and checked where it is pointing to. when i checked /usr/bin/python , it was pointing to python 2.7.

Instead of running the script as

python script_name.py

i changed it to

/usr/bin/python script_name.py

And yes, it worked. Sometimes we complicate few easy stuffs :-)