Indian Civilization

Michel Danino's lecture series of Indian Civilization. This is a must for Indians. It gives facts and figures of how and what is Indian civilization.

https://www.youtube.com/playlist?list=PL1tPjaS1KFVVaE2LLviORsxUs31e0J_r2

Name Value Dictionary

As I was developing the basic web server, I found the need for a key value or name value dictionary to store the name value pairs. Earlier as part of my MS course curriculum I had written a chained and open addressing hash tables in python. I followed the similar pattern. Along with that "The C programming Langauage" by Brian W. Kernighan and Dennis M. Ritchie book in section 6.6 also explains about creating the name value list.

I have created a chained hash table. One of the main feature of hash table or dictionary is searching or retrieving of the stored value is fast. It should be O(1). If I had used Open addressing table than I could have achieved this. But with chained hash table we are heavily dependent on the hash function. So there may be chances that search will take more than O(1). 

Okay let me first explain the dictionary function. Suppose you have key value pairs like 'employee name' and 'employee id' or 'programming languages' and 'C, C++, javascript, C#', etc. Now I need a data structure to store such key value pairs. I should be able to keep on adding and updating such key value pairs without worrying about where they get stored and memory limit. For an external user it is an infinite memory bucket, where he/she keeps on dumping key:value pairs. User can add new key:value pair, access the already stored key:value pair, update value of existing key:value pair, search for a key.

Now let me explain the implementation details. Initially when I am creating the dictionary a default sized array will be created where all name value pairs will be stored. As the array gets filled up, we try to increase the array size and rebuild the dictionary. This, we will try to do by monitoring the load factor. Example if the load factor = (Number of current nodes/Size of Dictionary Array) is greater than 0.8 then we increase the Array size and rebuild the dictionary array. You may wonder why dictionary has to be rebuilt. See our hash function which gives the index of the array, where the name value needs to be stored will use the size of the array to generate the index. So when array size changed then for the same old key, hash value will give you some other index. So literary you lost all the old nodes of dictionary. To avoid this error, once new array is created, all the old values has to be re added/hashed to this new array.

Given a key, we will pass that key to a hash function. This hash function will give you an integer which will be within 0 and array size of dictionary. This will be index in the array where we will be saving the name value pair. There are chances of collision that is two keys can lead to generation of same index. In this scenario there are many ways to handle it. we are using chained hashing. Here each entry in the array is a singly linked list. Each node in the singly linked list, represent  the name value pair. So if in an index already another name value pair is present then we will be adding to this list new name value pair. 

So when given a key, First step is to get the index using the hash function. Using this index we can get the singly list of all the keys which are having same index. Now traverse the singly list to find the exact key value pair.

This is my dictionary node. A dictionary node has a key (strName) and a value (strValue). As this node will be part of the singly linked list, we have self referencing pointer 'next'

typedef struct structDictionaryNode
{
 char* strName;
 char* strValue;
 struct structDictionaryNode* next;
}DictionaryNode;

This is my actual dictionary. LoadFactor will define when I need to rebuild by dictionary by increasing the size of buffer array. nSizeOfDictionary is the size of the buffer array that is total slots available for allocation. nCurrentSize will tell you how many key value pairs are currently present in the dictionary. So current load factor can be calculated by nCurrentSize/nSizeOfDictionary. dictionaryArray will be my buffer array, basically it is array of singly linked lists.

typedef struct
{
 float LoadFactor;
 int nSizeOfDictionary;
 int nCurrentSize;
 DictionaryNode** dictionaryArray;
}Dictionary;

This function is used to create the dictionary. As you can see we are using load factor as 0.8. Also size of the initial array is passed.

Dictionary* CreateDictionary(int nSizeOfDictory)
{
 Dictionary *dict = 0;
 int i = 0;

 if (nSizeOfDictory == 0)
  nSizeOfDictory = 10;

 dict = (Dictionary*)malloc(sizeof(Dictionary) * 1);
 if (dict == 0)
 {
  //Error handle it
  return dict;
 }

 (*dict).LoadFactor = 0.8;
 (*dict).nSizeOfDictionary = nSizeOfDictory;
 (*dict).nCurrentSize = 0;
 (*dict).dictionaryArray = (DictionaryNode**)malloc(sizeof(DictionaryNode*)*(*dict).nSizeOfDictionary);

 for (int i = 0; i < (*dict).nSizeOfDictionary; i++)
  (*dict).dictionaryArray[i] = 0;


 return dict;
}

This is the hash function used to find the actual index where the node needs to be placed in the dictionary array.

unsigned hash(int nSizeOfTable, char *s)
{
 unsigned hashval;
 for (hashval = 0; *s != '\0'; s++)
  hashval = *s + 31 * hashval;
 return hashval % nSizeOfTable;
}

Every time you want to add a name value pair, we use below function. Also you can see, as we add a key we will verify if this addition has resulted in exceeding the load factor. If so then we are rebuilding the dictionary. If loadfactor is exceeded, then we are creating new dictionary with double the previous size.

int AddNameValueToDictionary(Dictionary *dict, char *strKey, char *strValue)
{
 int nReturnValue = 0;
 DictionaryNode *pHead = 0, *pCurrent = 0;
 int i = 0;
 float fTemp = 0.0;
 int bFoundKey = 0;

 if (dict == 0 || strKey == 0 || strValue == 0)
 {
  nReturnValue = ERR_INVALID_PARAMETERS_DICT;
  return nReturnValue;
 }

 if (IsKeyExistsInDictionary(dict, strKey) == 1)
 {
  pHead = (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)];
  if (pHead == 0)
  {
   //Actually Error
   (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)] = CreateADictionaryNode(strKey, strValue);
   (*dict).nCurrentSize++;

  }
  else
  {
   while (pHead != 0)
   {
    if (strcmp((*pHead).strName, strKey) == 0)
    {
     //Update Value
     free((*pHead).strValue);
     (*pHead).strValue = (char*)malloc(sizeof(char)*strnlen_s(strValue, MAXVALUESIZE) + 1);
     memset((*pHead).strValue, '\0', strnlen_s(strValue, MAXVALUESIZE) + 1);

     i = 0;
     while (strValue[i] != '\0')
     {
      (*pHead).strValue[i] = strValue[i];
      i++;
     }

     bFoundKey = 1;
     break;
    }
    else
    {
     pHead = (*pHead).next;
    }
   }

   if (bFoundKey == 0)
   {
    //Actually Error
    pHead = (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)];
    pCurrent = CreateADictionaryNode(strKey, strValue);
    (*pCurrent).next = pHead;
    (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)] = pCurrent;
    (*dict).nCurrentSize++;

   }
  }



 }
 else
 {
  pHead = (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)];

  if (pHead == 0)
  {
   (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)] = CreateADictionaryNode(strKey, strValue);
   (*dict).nCurrentSize++;
  }
  else
  {
   pCurrent = CreateADictionaryNode(strKey, strValue);
   (*pCurrent).next = pHead;
   (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)] = pCurrent;
   (*dict).nCurrentSize++;
   
  }

 }

 fTemp = (*dict).nCurrentSize;
 fTemp = fTemp / (*dict).nSizeOfDictionary;


 if (fTemp > (*dict).LoadFactor)
 {
  nReturnValue = RebuildDictionary(dict, (*dict).nSizeOfDictionary * 2);
 }

 return nReturnValue;
}

It is common in dictionary operations to know if a key is already present in the dictionary. Following function will return 1 if key is found in dictionary, else 0.

int IsKeyExistsInDictionary(Dictionary *dict, char *strKey)
{
 int bFound = 0;
 int i = 0;
 DictionaryNode *pHead = 0, *pCurrent = 0;

 for (i = 0; i < (*dict).nSizeOfDictionary; i++)
 {
  pHead = (*dict).dictionaryArray[i];
  if (pHead != 0)
  {
   pCurrent = pHead;
   while (pCurrent != 0)
   {
    if (strcmp(strKey, (*pCurrent).strName) == 0)
    {
     bFound = 1;
     break;
    }

    pCurrent = (*pCurrent).next;
   }
  }
 }

 return bFound;
}

This function rebuilds the dictionary with the new size.

int RebuildDictionary(Dictionary *dict, int nNewSize)
{
 int nReturnValue = 0;
 int i = 0;
 int nOldSize = 0;
 DictionaryNode *pHead = 0, *pCurrent = 0;

 DictionaryNode** pNewArray = (DictionaryNode**)malloc(sizeof(DictionaryNode*)*nNewSize);
 DictionaryNode** pOldArray = (*dict).dictionaryArray;
 nOldSize = (*dict).nSizeOfDictionary;
 (*dict).nSizeOfDictionary = nNewSize;
 (*dict).dictionaryArray = pNewArray;
 (*dict).nCurrentSize = 0;

 for (i = 0; i < nOldSize; i++)
 {
  pHead = pOldArray[i];

  while (pHead != 0)
  {
   pCurrent = pHead;
   pHead = (*pCurrent).next;

   (*pCurrent).next = 0;
   nReturnValue = AddNodeToDictionary(dict, pCurrent);
   if (nReturnValue != 0)
   {
    //Error handle it
   }
   
  }
 }

 free(pOldArray);
 pOldArray = 0;

 return nReturnValue;
}


This function will delete a particular node or name value pair from the dictionary. 

int DeleteKeyFromDictionary(Dictionary *dict, char *strKey)
{
 int nReturnValue = 0;

 int i = 0;

 DictionaryNode *pHead = 0, *pCurrent = 0, *pPrev = 0;

 pHead = (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)];
 if (pHead != 0)
 {
  pCurrent = pHead;
  while (pCurrent != 0)
  {
   if (strcmp((*pCurrent).strName, strKey) == 0)
   {
    if (pPrev == 0)
    {
     (*dict).dictionaryArray[hash((*dict).nSizeOfDictionary, strKey)] = (*pCurrent).next;

    }
    else
    {
     (*pPrev).next = (*pCurrent).next;

    }
    free((*pCurrent).strName);
    free((*pCurrent).strValue);
    free(pCurrent);
    dict->nCurrentSize--;
    break;
   }

   pPrev = pCurrent;
   pCurrent = (*pCurrent).next;
  }
 }
 else
 {
  //Should I have to intimate user??
 }

 return nReturnValue;
}


These functions will delete entire dictionary.

int DeleteDictionaryNodeArray(DictionaryNode **dArray, int nSizeOfArray)
{
 int nReturnValue = 0;
 int i = 0, j = 0;
 DictionaryNode *pCurrent = 0, *pHead = 0;

 for (i = 0; i < nSizeOfArray; i++)
 {
  if (dArray[i] != 0)
  {
   pHead = dArray[i];
   while (pHead != 0)
   {
    if ((*pHead).strName != 0)
    {
     free((*pHead).strName);
     (*pHead).strName = 0;
    }

    if ((*pHead).strValue != 0)
    {
     free((*pHead).strValue);
     (*pHead).strValue = 0;
    }

    pCurrent = (*pCurrent).next;
    free(pHead);
    pHead = pCurrent;

   }

   dArray[i] = 0;
  }
 }

 free(dArray);
 dArray = 0;

 return nReturnValue;
}


int DeleteDictionary(Dictionary *dict)
{
 int nReturnValue = 0;
 int i = 0, j = 0;
 DictionaryNode *pCurrent = 0, *pHead = 0;

 if (dict != 0)
 {
  if ((*dict).dictionaryArray != 0)
  {
   nReturnValue = DeleteDictionaryNodeArray((*dict).dictionaryArray, (*dict).nSizeOfDictionary);
   (*dict).dictionaryArray = 0;
  }

  (*dict).LoadFactor = 0;
  (*dict).nCurrentSize = 0;
  (*dict).nSizeOfDictionary = 0;

  free(dict);
  dict = 0;
 }

 return nReturnValue;
}

Given a key, get the corresponding value stored in dictionary. This is a very important function of dictionary.

DictionaryNode* GetNodeFromDictionary(Dictionary *dict, char *strKey)
{
 DictionaryNode *pNode = 0;

 pNode = dict->dictionaryArray[hash(dict->nSizeOfDictionary, strKey)];

 while (pNode != 0)
 {
  if (strcmp(pNode->strName, strKey) == 0)
  {
   break;
  }
  
  pNode = pNode->next;
 }

 return pNode;
}


char* GetValueFromDictionary(Dictionary *dict, char *strKey)
{
 char *strValue = 0;

 DictionaryNode *pNode = GetNodeFromDictionary(dict, strKey);
 if (pNode != 0)
 {
  strValue = pNode->strValue;
 }

 return strValue;
}


Complete code can be found at git - https://github.com/harsha-kadekar/BasicHttpServerClient
Code is present in file SupportingDataStructures.c and SupportingDataStructures.h files.

Atbash Cipher

I think this is the easiest ciphers. In the plain text if we get 'A' then we replace it with 'Z' character. Similarly 'B' -> 'Y', 'C' -> 'X'.... I guess you get the idea, so each time you get a character you replace with the character from the end of English alphabet sequence. So here is the lookup table you can use to implement this cipher

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

I used following code implement this cipher.

int AtbashCipher(char* strPlainText, int nSize, char* strCipherText)

{

int nReturnValue = 0;

if (nSize <= 0 || strPlainText == NULL || strCipherText == NULL)

{

return ERR_INVALIDINPUTPARAMETERS;

}

for (int i = 0; i < nSize; i++)

{

//Idea here is replace A->Z, B->Y, C->X .....

if (strPlainText[i] >= 65 && strPlainText[i] <= 90)

{

//Capital Letters

strCipherText[i] = 90 - (strPlainText[i] - 65);

}

else if (strPlainText[i] >= 97 && strPlainText[i] <= 122)

{

//small Letters

strCipherText[i] = 122 - (strPlainText[i] - 97);

}

}

return nReturnValue;

}

I guess same function can be used for decrypting the cipher text. Will be testing it soon and updating this blog.

Is it a strong cipher? Definitely not. This is even looks like a special case of caeser cipher with key value = 25.

Okay code is present in git -> https://github.com/harsha-kadekar/NetworkSecurityAlgos

To understand Atbash cipher I read website -> http://practicalcryptography.com/ciphers/classical-era/atbash-cipher/

Suppose plain text is "Harsha Kadekar" then cipher text would be "Szihsz Pzwvpzi"

Socket communication in windows

There are many website which teach you socket communication in windows using winsock. So if you have come to this site looking for some tutorial I would recommend you to go directly to microsoft website. Then why I am writing this blog you ask - well this is kind of a remembrance post of what I did in socket communication. 

I have started developing a basic Http server [If you have followed my previous posts then sorry for one more started project]. In this first step is establishing the socket communication between client and server. So as of now I am able to do the socket communication between server and client. Basically server will wait for a client connection, once connected to client will wait to receive a message from the client. Then displays the received message. It will send a message to client and finally closes the connection. For handling client connections it is creating a new thread each time a new connection is created with client. To test server I have created a basic client. Client will connect to the server, send a message and wait for message from server. Once received, it will display that message and closes the connection.

Steps for socket connection from server side- 

1. Create a socket
2. Bind to the socket
3. Wait for client connections i.e. listen to connections
4. Accept those connections
5. Send/Receive messages from/to that connection
6. Shutdown the connection
7. Close the socket

Before creating the socket we need to initialize the winsock which we do using WSAStartup function. Then we need to define the address, protocal and socket types for which socket being created. Once these are defined then we will create a socket. Once socket is created, that socket has to be binded to the address and port like 8080 port. After this server will listen for new connections from the clients. Using accept function call we accept the new client connection. Once accepted we can send messages to client as well as receive messages from client. Once done we shutdown the connection, close the socket and cleanup the winsock using WSACleanup.

WSAStartup(MAKEWORD(2, 2), &wsData)

structServerAddrInfo.ai_family = AF_INET;

structServerAddrInfo.ai_socktype = SOCK_STREAM;

structServerAddrInfo.ai_protocol = IPPROTO_TCP;

structServerAddrInfo.ai_flags = AI_PASSIVE;

nReturnValue = getaddrinfo(NULL, "8080", &structServerAddrInfo, &structServerAddrResult);

scListenSocket = socket(structServerAddrResult->ai_family, structServerAddrResult->ai_socktype, structServerAddrResult->ai_protocol);

nReturnValue = bind(scListenSocket, structServerAddrResult->ai_addr, structServerAddrResult->ai_addrlen);

nReturnValue = listen(scListenSocket, SOMAXCONN);

scClientSocket = accept(scListenSocket, NULL, NULL)

nReturnValue = recv(scClientSocket, szRecieveMsg, 512, 0);

nReturnValue = send(scClientSocket, sTestMessage, 35, 0);

nReturnValue = shutdown(scClientSocket, SD_SEND);

closesocket(scClientSocket);

WSACleanup();

Steps for socket connection in client:

1. Create socket
2. Connect to server
3. Send/Receive messages to/from server
4. Close socket

Similar to server here also first we need to call WSAStartup function. Once done create a socket that can connect to server using same port and server address. Once connected to server client can send messages to server as well as recieve messages from the server. Once all done, it can close the socket created. Finally call the WSACleanup()

nReturnValue = WSAStartup(MAKEWORD(2, 2), &wsData);

structClientaddr.ai_family = AF_INET;

structClientaddr.ai_protocol = IPPROTO_TCP;

structClientaddr.ai_socktype = SOCK_STREAM;

nReturnValue = getaddrinfo(sServerName, "8080", &structClientaddr, &structServeraddrInfo);

scConnectSocket = socket(structAddrIterator->ai_family, structAddrIterator->ai_socktype, structAddrIterator->ai_protocol);

nReturnValue = connect(scConnectSocket, structAddrIterator->ai_addr, structAddrIterator->ai_addrlen);

nReturnValue = send(scConnectSocket, sTestMessage, strnlen_s(sTestMessage, 33), 0);

nReturnValue = recv(scConnectSocket, szRecieveMessage, 512, 0);

closesocket(scConnectSocket);

WSACleanup();

I agree, I have not explained it in deep, may be sometime later. Code of this can be found at gitbhub

https://github.com/harsha-kadekar/BasicHttpServerClient

Breaking Caesar Cipher by brute force

I started learning about cryptography. Given a data we do some transformation or certain steps on the data such that data looses or hides its original form. Any person who sees that new form does not recognizes whats its original form. This is encryption. Again we can use certain steps on new form of data to get back the original form of data. This is decryption. 

PlainText --> Encryption Engine -> Cryptic Text

Cryptic Text --> Decryption Engine -> Plain Text.

Ciphers are nothing but those encryption engines which will generate the cryptic message given a plain message. There are different types of ciphers. I will be explaining one of the oldest ciphers. Caesar Cipher. Yes as name suggests it was used by Julius Caesar. This is a simple cipher. Given a plain text, each character in that message will be replaced by another symbol. There is a concept of key. Key place a very important role is conversion of text to cryptic text as well as reversing the cryptic text to plain text. So key will be present with the person who is preparing the cryptic text. And also the same key will be present with the person to whom the message needs to b passed.

English alphabet has totally 26 characters. Now in Caesar cipher, these English alphabet will be replaced again by English alphabet. Example if character is 'b' and key is 3 then b will be replaced by 'e'.  Suppose character is 'z' then it will be replaced by 'c'. So number of possible keys are 25 i.e. number of English alphabet -1. Basically it means I can replace a character x with 25 other characters.

for (int i = 0; i < nSize; i++)

{

if (strPlainText[i] >= 65 && strPlainText[i] <= 90)

{

//Capital letters

nTemp = strPlainText[i] + *pKey;

if (nTemp > 90)

{

nTemp = nTemp - 26;

}

strCipherText[i] = nTemp;

}

else if (strPlainText[i] >= 97 && strPlainText[i] <= 122)

{

//small letters

nTemp = strPlainText[i] + *pKey;

if (nTemp > 122)

{

nTemp = nTemp - 26;

}

strCipherText[i] = nTemp;

}

else

{

strCipherText[i] = strPlainText[i];

}

}

In simple words this is doing ch = (pt + k)mod 26. where pt is the character from plain text, k is the key and ch is character from cipher text. In code I am trying to first check whether character obtained is a small letter alphabet or capital letter aplhabet. If not then it is a numeric or some other symbols. Those characters are not touched. If it is a smaller letter than it will be replaced by cipher text of smaller letter. If it is a capital letter I am replacing the with cipher text of capital letter. 

Deciphering is a simple step. pt = (ch - k)mod26. ch is the character from cipher text, k is the key and pt is the character from plain text. 

for (int i = 0; i < nSize; i++)

{

if (strCipherText[i] >= 65 && strCipherText[i] <= 90)

{

nTemp = strCipherText[i] - nKey;

if (nTemp < 65)

{

nTemp = 26 + nTemp;

}

strPlainText[i] = nTemp;

}

else if (strCipherText[i] >= 97 && strCipherText[i] <= 122)

{

nTemp = strCipherText[i] - nKey;

if (nTemp < 97)

{

nTemp = 26 + nTemp;

}

strPlainText[i] = nTemp;

}

else

{

strPlainText[i] = strCipherText[i];

}

}

Breaking the cipher - Now if I have the text but I don't have the key. In this case I know that possible keys are from 1-25. Try all these on the cipher text. They check the answer which makes the correct sense of the text. 

for (int i = 1; i < 25; i++)

{

memset(strKey, '\0', 5);

sprintf_s(strKey, "\n%d\n", i);

fwrite(strKey, sizeof(char), strnlen_s(strKey,6), fpOutputFile);

for (int j = 0; j < nSize; j++)

{

if (strCipheredText[j] >= 65 && strCipheredText[j] <= 90)

{

nTemp = strCipheredText[j] - i;

if (nTemp < 65)

{

nTemp = 26 + nTemp;

}

strPlainText[j] = nTemp;

}

else if (strCipheredText[j] >= 97 && strCipheredText[j] <= 122 )

{

nTemp = strCipheredText[j] - i;

if (nTemp < 97)

{

nTemp = 26 + nTemp;

}

strPlainText[j] = nTemp;

}

else

{

strPlainText[j] = strCipheredText[j];

}

}

fwrite(strPlainText, sizeof(char), strnlen_s(strPlainText, nSize), fpOutputFile);

memset(strPlainText, '\0', nSize+1);

}

As you can see, I am trying all the 25 keys and storing the result in a file. 

If plain text was "Harsha Kadekar" and key was 13 then cryptic text was "Unefun Xnqrxne"

Actual code is present in github -> https://github.com/harsha-kadekar/NetworkSecurityAlgos.git

And I am learning from book -> Cryptography and Network Security: Principles and practices by William Stallings.

Comparing running time for various algorithms

I was trying to compare different algorithms based on input size. I have implemented all these algorithms in C. Following table gives you how the order of growth is affecting practical implementation.

n	Bubble Sort	Insertion Sort	Merge Sort	Selection Sort
100	0 ms	0 ms	0 ms	0 ms
1000	0 ms	0 ms	0 ms	0 ms
10000	250 ms	62 ms	0 ms	94 ms
50000	6546 ms	1563 ms	16 ms	2328 ms
100000	26687 ms	6266 ms	47 ms	9291 ms

0 means it has taken very less or negligible time.

So it looks like Merge sort is clear winner. Followed by insertion sort, selection sort and finally Bubble sort.

Same thing I applied for Matrix Multiplication.

N	Brute Force (n^3)	Strassen
128	16 ms	1391 ms
512	656 ms	68078 ms
1024	7297 ms	474781 ms
10000	3.64 hours	Did not stop even after 24 hours
		(Actually even if it had stopped answer would be wrong as 10000 is not power of 2)

As you can see it looks like Strassen is not yet all beating brute force in any way. Then I came across following points in Wikipedia (https://en.wikipedia.org/wiki/Strassen_algorithm)

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations.[1]However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less)

Similar things are discussed in some of the coding forums ->  http://stackoverflow.com/questions/13559928/why-is-my-strassens-matrix-multiplication-slow?rq=1

So based on above comments I changed implementation. I kept Crossover value as 32. That is if sub matrix size is 32x32 than Strassen's algorithm instead of calling its own algorithm with smaller size, it will call Brute force algorithm to do the lower size matrix multiplication.

N	Brute Force (n^3)	Strassen
64	0 ms	16 ms
128	16 ms	16 ms
256	125 ms	110 ms
512	1078 ms	937 ms
1024	14468 ms	6282 ms

Clearly Strassen is overtaking brute force. Now I tried with crossover value as 16. Again Strassen was very close to Brute force but could not beat it. For value 128, Strassen was able to beat Brute force only after N size of 512.

In my case Strassen algorithm takes 2-3 times more memory than Brute Force like for n = 1024 i.e. 1024*1024 matrix brute force took 21 MB where as Strassens algorithm took 48 MB.

Sorting Algorithms - Merge Sort

Now merge sort is based on the divide and conquer concept. Idea is to divide the problem into smaller sub problems and solve those sub problems. Once you are able to solve those sub problems, join them together to get the solution for the bigger problem. Now in case of merge sort we divide the problem into exactly two halves. Take that halves and again divide them into two halves again. Like this we will go until exactly one element is left in each of the sub problems. Now we start merging them by comparing each elements. The one having smaller element will be placed first and bigger one will be placed after that. Below diagram will help you to understand it.

First image is of division work. It shows how the problem is divided into smaller sub problem.

Once we are successful in dividing the problem into smaller sub problem now its time to conquer it that is to merge them. Below image shows how it will be merged.

For division purpose in coding we are using recursive function. Recursive functions are those which will call itself again and again with modified parameters until a predefined goal is met. Below is the code snippet for this

int MergeSortAlgo(int* pIntArray, int nStart, int nSize)
{
int nReturnValue = 0;
int nMid = -1;

nMid = nSize / 2;
if (nMid > 0)
{
//This is divide part of the algorithm. That is we are dividing the array into smaller sub arrays.
MergeSortAlgo(pIntArray, nStart, nMid);
MergeSortAlgo(pIntArray, nStart + nMid, nSize - nMid);
//This is conquering part of the algorithm. Here once after division of the array we are trying to merge them into one.
MergeArray(pIntArray, nStart, nSize);
}

return nReturnValue;
}

As you can see MergeSortAlgo is called repeatedly by itself with different parameters. It is dividing the problem into two which is done in step nSize/2.

Once all division is done it is going further to Merge those divided sub problems. Below is the code which is doing exactly that

int MergeArray(int *pIntArray, int nStart, int nSize)
{
int nReturnValue = 0;
int nMid = nSize / 2;
int nFirstStart = nStart;
int nSecondStart = nStart + nMid;
int nFirstEnd = nStart + nMid - 1;
int nSecondEnd = nStart + nSize - 1;

int i = nFirstStart, j = nSecondStart, k = 0;

int* pTempArray = 0;
pTempArray = (int*)malloc(nSize*sizeof(int));
if (pTempArray == 0)
{
//Error Dynamic memory not allocated.
return ERR_DYNAMICMEMNOTALLOC;
}
else
{
while (k < nSize && (i <= nFirstEnd && j <= nSecondEnd))
{
if (pIntArray[i] < pIntArray[j])
{
pTempArray[k++] = pIntArray[i++];
}
else
{
pTempArray[k++] = pIntArray[j++];
}
}

while (i <= nFirstEnd)
pTempArray[k++] = pIntArray[i++];

while (j <= nSecondEnd)
pTempArray[k++] = pIntArray[j++];

i = 0, j = 0, k = 0;

for (k = 0; k < nSize; k++)
pIntArray[nStart++] = pTempArray[k];

free(pTempArray);

}

return nReturnValue;
}

Nothing special here. First I have allocated a temporory space whose size is sum of arrays of sub problems. Then I comparing one element of Sub problem1 and one element of Sub problem2. Whichever is smaller will be placed in the temparory array. This is repeated for every elements.

Okay the order of growth of merge sort is Theta(nlogn) log base is 2. How do we get this well wait for my post on Masters Theorem.

Code is present in location https://github.com/harsha-kadekar/LibraryOfAlgorithms.git
I am learning from "Introduction to Algorithms" book 3rd edition. Authors - Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford  Stein.