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 :-)

As the days are passing , computers are getting faster and faster . At the same time, the amount of data that is being used is growing exponentially. Hence, we are in a path of finding how to handle, store and analyze the huge data set in a effecient manner.

One among such example is Google Books Ngram . if you just navigate to the following URL

Google Books

you will be seeing a text box asking you to enter a book name. And it will search from 5.2 million books.

Believe it or not, Google has digitized all 5.2 million books and has come up with the concept of NGRAM.

http://books.google.com/ngrams

This link will show you a default page like .

Google Books Ngram

Before getting into the page description , we need to know what is ngram . N-gram is a word in which , N is the number of times the word is being used in the books between selected years .

In graph , by default it shows the output of 3 different names, Sherlock Homes, Albert Einstein , Frankenstein . It go searches in 5.2 Million books and yields a graph with the N-gram count, which can tell you the exact amount of time the word is being used in the books on those specific years.

Even the data set is available to download and research . These kind of data analysis is used for prediction and other purpose. It yields interesting results when analyzed with selective phrases.

If your target is JUST to learn how to solve rubik cube, then the whole journey is going to be very simple . There are plenty of tutotials out there , which can help you to solve Rubik . BUT, if you are planning to be a speed cuber who can solve rubik in mere seconds then, this post is dedicated for you . I have categorized things into steps . Hope it would be helpful .

Step 1 : First Challenge is to get a good Rubik Cube :

I am not sure if am using the world’s best rubik cube, but i can assure you that you can really solve faster when you use Moyu Weilong

Step 2 : Getting Started – Pick a Method to solve

I solve rubik with Fridrich method (CFOP) . I never tried any other rubik Method , because i feel this method works really well for me . I would recommend watching this you tube tutorial which solves rubik in beginner method .

At the end of this video , you should be knowing how to solve a rubik cube . And you will be wondering How fast can i do this. Move on to Step 3 .

Step 3 : Dont get Greedy – Practice hard

Beginner method is just a heads up for the career . There are plenty of stuff out there to learn . My first rubik solve took 8 minutes . And gradually learning the algos took me down to 40 seconds . Hence , practice the beginner method well and understand the pieces, movements, orientations, layers and turns .

Step 4 : Algos – Most important part

Usally, people start learning algos in the way we do CFOP – Learning the Cross , then F2L Algorithms , then OLL algorithms and at last PLL algorithms . Even i learn the same way . But , i think following method works really well (Yes, i have tried by teaching my friends )

1. There are 21 PLL algorithms. Learning 1 a day you can avoid last 2 forumulas to complete the last layer of the cube.

2. Cross in the bottom . Practice solving cross in the bottom layer with good tricks . Make use of the inspection time and track the pieces quickly to solve cube in seconds .

3. Intuitive F2L. Trust Me. instead of putting lot of efforts in learning 40 odd F2L formulas , just try spending time on intuitive F2L. Once you understand and practise it for some time , F2L solve is damn easy .

4. OLLs – oh god . 60 odd formulas . Cut it down into groups . First learn essestial 8 algos (all edges oriented correctly ) which will cut you few RUR’UR2R’. Then try to know how you can avoid Dotted OLLs , by intelligently inserting the last F2L pair. And the rest, learning 1 a day .

Step 5 : Finger Tricks – The magic

Each layer turn just needs a flick with an appropriate finger . Learn how you can utilize the finger tricks and practise it .

Step 6 : Solve , Solve , Solve

Keep practicing the algorithms . One day you will be holding the title of “FASTEST RUBIK CUBE SOLVER IN THE WORLD”

When we store time stamp in database the column can be of type DATE TIME YEAR TO SECOND .

It Will contain day of month, month, year, time in seconds. But usually the scenarios that we Will be handling Will be pull all the data that happened this year or pull all the data that happened on particular date

on these scenarios we need to extract the columns from time stamp data.

here is the list of keywords

Day
Month
Year
Date

select DAY(activity_date) from table .

select MONTH(activity_date) from table.

select YEAR(activity_date) from table.

select DATE(activity_date) from table

say the timestamp is
2014-03-05 13:17:40

queries will return

5
3
2014
03/05/2014

In my past post , i explained the insertion sort with c++ code

http://shrinathsuccess.wordpress.com/2014/03/09/insertion-sort-c/

The major overhead in the insertion sort algorithm is swapping. For each element we are performing j-i swaps if the sequence is in descending order. Swaps are much costlier and we also need a new variable involved for swapping. If we could reduce the number of swapping then we will hit with the better performance.


#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
        cout << "Enter number of elements" << endl;

        int n,i,j;
        cin >> n;
        int a[n];
        int c = 0;
        srand(time(NULL));
        for(i=n; i>0 ; i--)
        {
                a[c] = i;
                c++;
        }
        cout << "Array Before Sorting" << endl;
          for(int i=0 ; i<5; i++)
          cout << a[i] << endl;
        for(i=1 ; i<n ; i++)
        {
                int key = a[i];

                for(j=i ; j>0 ; j--)
                {
                        if(a[j-1] > key)
                        {
                                a[j] = a[j-1];
                        }
                }
                a[j] = key;
        }

        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

TRIAL :

5 4 3 2 1

i = 1
key = 4
j = 1 , 1> 0

if(a[0] > key) => if(5 > 4)
a[1] = a[0] => 5 5 3 2 1

j=0 ; 0>0 – false
end of inner for loop
a[0] = key => 4 5 3 2 1
i=2
key = 3
j = 2

i = 2
key = 3
j = 2 ; 2 > 0
if(a[1] > key) => if(5 > 3)
a[2] = a[1] => 4 5 5 2 1

j=1 ; 1>0
if(a[0] > key) => if(4 > 3)
a[1] = a[0] => 4 4 5 2 1

j=0 ; j>0 – false
a[0] = 3 => 3 4 5 2 1

and the loop goes on like this ….

Instead of swapping the elements we perform assignment operation and at the end of the loop we assign the key back to the right place.

Special thanks to Nithin for pointing this out – https://www.facebook.com/nithin.kalathingal.5

WHAT IS LINKED LIST :

Linked list is a data structure which contains a set of elements linked to its successor.

WHERE TO USE LINKED LIST :

When there is a need of lot of insertions and deletions , linked list is preferred over Array .

One simple example is this : Say we have array of 1000 numbers . 2 to 1001 . Now we need to insert 1 at the beginning of the array. Its not so simple, we need to shift all the numbers from 2 to 1001 one step right for inserting one element at the beginning.

Linked list over comes this problem. Just allocate memory and play with pointers to give connections. 1 will be inserted at the beginning.

WHERE NOT TO USE LINKED LIST :

There are certain scenarios where in we need more number of searches than insert and delete. On such occasion arrray gives us a better result.

HOW TO IMPLEMENT LINKED LIST :

In this post we will be discussing 12 basic set of items on linked list

1. Structure of Linked List

2. Creating One node Linked List

3. Creating 3 Node Linked List

4. Creating N Node linked List

5. Inserting a node at front of linked list

6. Inserting a node at end of linked list

7. Inserting a node at N point of linked list

8. Deleting first element from list

9. Deleting last element from list

10. Deleting random element from list

11. Searching linked list

12. Copying Linked list

STRUCTURE OF LINKED LIST

                       Structure Of Linked List

A linked list contains data element along with the pointer which points to the next element.

struct node
{
     int data;
     struct node* next;
};

Creating One node Linked List:

                                         Single Node Linked List

Lets create a simple one node linked list . For creating a node , we need to follow three steps.

  1. Create a new node pointer
  2. Allocate memory and insert element
  3. Point the pointer to appropriate position
#include  // for cout
#include  // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);

int main()
{
        // create head pointer
        struct node* head = NULL;

        // allocate memory to it
        head = (struct node*) malloc(sizeof(struct node));

        // insert the data
        head->data = 1;

        // point the next pointer
        head->next = NULL;

        // printing the list
        print_ll(head);
        return 0;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

Output of single node linked list

CREATING 3 NODE LINKED LIST

                                    three_node_ll

Now, we know the size of linked list. So, lets create a function that will build 3 nodes in a linked list.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* three_node_ll();

int main()
{
        // call the function to create the list
        struct node* head = three_node_ll();
        // printing the list
        print_ll(head);
        return 0;
}

struct node* three_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;
        struct node* third = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));
        third = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 1;
        head->next = second;

        second->data = 2;
        second->next = third;

        third->data = 3;
        third->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

three_node_output

CREATING N NODE LINKED LIST

In the previous case, we know the definite size of linked list . But , now we need to build a list based on the input given by the user. Hence , we need to write a generic function which will insert the numbers into list dynamically.It is easy to push elements at the front of the list . It comprises of 3 steps.

  1. Allocate memory for the new node and insert data into it.
  2. Point the next pointer to old head
  3. Change head to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
void n_node_ll(struct node*&,int);
int num_of_nodes;

int main()
{
        cout << "Enter number of nodes to be created " << endl;
        cin >> num_of_nodes;
        struct node* head = NULL;
        // call the function to create the list
        for(int i=0 ; i<num_of_nodes; i++)
        {
                n_node_ll(head,i+1);
        }
        // printing the list
        print_ll(head);
        return 0;
}

void n_node_ll(struct node*& head, int d)
{
        // allocate memory and insert data
        struct node* newNode = (struct node*) malloc(sizeof(struct node));
        newNode->data = d;
        // point next pointer to old head
        newNode->next = head;
        // point head to new node
        head = newNode;
}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

INSERTING NODE AT FRONT OF LINKED LIST

n_node_ll

Say, we have linked list with 2 elements . 4 and 3 . Now we need to push 5 into the list at the front .

As explained in the previous code , it will be done with same 3 steps.

#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_front(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();
        // inserting number 5 at the front
        insert_at_front(head,5);
        // printing the list
        print_ll(head);
        return 0;
}

void insert_at_front(struct node*& head,int d)
{
        struct node* current = head;

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to old head
        newNode->next = head;

        // change head of the list to new node
        head = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 4;
        head->next = second;

        second->data = 3;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

insert_at_front

INSERTING A NODE AT END OF THE LIST

insert_at_end

For adding the node at the tail end we need to follow these steps

  1. Iterate through the list and find the point the last element in the list
  2. Create new node and insert data to it
  3. Point the next pointer of new node to null since it is going to be the last element
  4. Link the old last element pointer to new node
#include <iostream> // for cout
#include <stdlib.h> // for malloc

using namespace std;

// create the struture of linked list

struct node
{
        int data;
        struct node* next;
};
void print_ll(struct node* head);
struct node* two_node_ll();
void insert_at_end(struct node*&,int);

int main()
{
        // call the function to create the list
        struct node* head = two_node_ll();

        // inserting number 3 at the end
        insert_at_end(head,3);

        // printing the list
        print_ll(head);
        return 0;
}
void insert_at_end(struct node*& head,int d)
{
        struct node* current = head;
        while(current->next != NULL)
        {
                current = current->next;
        }

        // create node and allocate memory
        struct node* newNode = (struct node*)malloc(sizeof(struct node));

        //insert data into the memory
        newNode->data = d;

        // point the next pointer to null since its the last element
        newNode->next = NULL;

        // change head of the list to new node
        current->next = newNode;
}

struct node* two_node_ll()
{
        // create 3 pointers for 3 nodes
        struct node* head = NULL;
        struct node* second = NULL;

        // allocate memory for 3 nodes
        head = (struct node*) malloc(sizeof(struct node));
        second = (struct node*) malloc(sizeof(struct node));

        // insert data into 3 nodes and point the sequence in right order
        head->data = 5;
        head->next = second;

        second->data = 4;
        second->next = NULL;

        return head;

}

void print_ll(struct node* head)
{
        struct node* current = head;
        cout << "List contains" <<endl;
        while(current != NULL)
        {
                cout << current->data << endl;
                current = current->next;
        }
}

output_insert_at_end

 

 

 

 

WHAT IS INSERTION SORT :

Insertion sort is a sorting algorithm which sorts the input data by putting elements into the sorted array one at a time .

It compares the next element in the array and puts it in the right place .

                                   Insertion Sort Graph


WHY INSERTION SORT :

When there are couple of sorting algorithms available why should i hit insertion sort ???

When the number of elements to be sorted is much lower , insertion sort gives us a very good result compared to others. Hence use it when the data set is low.

HOW INSERTION SORT WORKS :

Lets take an input tape with 5 elements in descending order.

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

2 3 4 5 1

1 2 3 4 5

On each iteration , it takes one element at a time and compares with the next element and places it in the right position.

First Iteration we take 4 as Key element . compare it with 5 . Since 4 is lesser we swap 4 and 5.

Second Iteration we take 3 as Key element . compare it with 5. 3 is lesser than 5 . Swap it . Yes, 3 is lesser than 4 also . Hence continue the swap until you place the element in the right place.

CODE FOR INSERTION SORT :


#include <iostream>
using namespace std;
void swap(int &a, int &b);

int main()
{
        // initializing the variables
        int a[10000];
        int c = 0;
        int n;

        // insert elements in descending order
        cin >> n;
        for(int i=n ; i>0; i--)
        {
        a[c] = i;
        c++;
        }

        // print the array before sorting
        cout << "Array Before Sorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;

        // insertion sort logic starts here
        for(int i=0 ; i<n-1; i++)
        {
                int key = a[i+1];
                int pos = i+1;
                for(int j=i; j>=0 ;j--)
                {
                        if(a[pos] < a[j])
                        {
                                swap(a[pos],a[j]);
                                pos--;
                        }
                }
        }
        // insertion sort logic ends here. Printing the array after sort.
        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

void swap(int &a, int &b)
{
        int t;
        t = a;
        a = b;
        b = t;

}

EXPLANATION :

for(int i=0 ; i<n-1; i++)

Each time we need to pick an element and put it in the right place. Hence we need a loop that runs through an array.

int key = a[i+1];
int pos = i+1;

On each iteration we choose one element as key and place it in the right place.
Hence , we are choosing the element which is in i+1 place as key and noting down its position in variable pos.

for(int j=i; j>=0 ;j–)

This innner for loop helps to compare the previous elements . we need to check till the first element and place the key element at the right place.

if(a[pos] < a[j])
{
swap(a[pos],a[j]);
pos–;
}

This condition checks with the previous element . If it is greater then it swaps the element .

TRIAL

Lets run this program for 5 elements .

Now input tape contains 5 4 3 2 1

First Iteration :

i=0 , key = 4, pos = 1
j=0 , 0>=0 is true hence
if(4<5) swap(4,5); pos– => pos = 0
Now, input tape contains : 4 5 3 2 1

Second Iteration:

i=1, 1<5, key = 3 and pos = 2 j=1, 1>=0
if(3<5) – true swap(3,5); Now input tape contains 4 3 5 2 1 pos — => pos =1

j– => j=0
j=0; 0>=0
if(3 < 4) – true swap(3,4) pos– = > pos = 0
Now input tape contains 3 4 5 2 1

Simillary loop goes on sorting .

BEST , WORST AND AVERAGE CASES

The program given above is for worst case . since the elements are in descending order . In this case, we need to compare all the elements with 2 for loops . The time complexity will be quadratic

For Best case scenario put the elements in the sorted order.

 for(int i=0 ; i<5; i++)
        a[i] = i+1;

Eventhough the elements are in the sorted order, the outer for loop will be running for n comparisons. Hence the best case is O(N);

AVERAGE CASE :

Generate random numbers and insert it into array .

#include <stdlib.h>
 srand(time(NULL));
         for(int i=0 ; i<5; i++)
        {
                a[i] = rand() % 10 + 1;
        }

Even in this case, the time complexity goes quadratic.
Hence the insertion sort is suitable only for the nearly sorted low data elements.
Below table shows the best worst and average case analysis of the program.

N Best Worst Average
1024 0.004 0.008 0.008
2048 0.016 0.032 0.02
4096 0.048 0.116 0.084
8192 0.164 0.468 0.312
16384 0.62 1.92 1.248
32768 2.47 7.704 4.94
65536 9.8 30.372 19.876
131072 39.428 125.43 83.756