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.

Sorting Algorithms - Insertion Sort

Okay I know I am again writing one more blog for insertion sort. The first one I had written when I was trying to develop a assembly language library containing all the sorting algorithm functions. Now I am creating a library in C language which will have many sorting algorithm functions and much more other functions. So the first one I tried was Insertion Sort. My primary book reference is "Introduction to Algorithms - 3rd Edition: Authors - Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein". 

The way I wrote this function is first I read the concept of insertion sort from the above mentioned book. Then I tried to create a C function based on the read concept. Once done I read the actual pseudo code given in the book and if it is much better I rewrote it in my library. So my version of insertion sort was different than in the book and 99% book version will be better and it happened in my case as well so I changed my logic to match with the book.

Imagine that there is a room, and inside which there are exactly 100 students and each student has class ID. This class ID is any number from 1 to 100. Now you are asked to arrange those students in a line in front of class building in the ascending order of their class IDs. So how do you do it? You will ask students to come out one at a time. First student will stand at the front of line. Now second student comes out. You will check his class ID and compare with the already stood students class ID. If his class ID is smaller than you will ask the earlier student to go back one position and new student will stand infront now. If the new students class ID is greater than the already standing student then you will ask the new student to stand at the next position after the already standing student. This process will repeat until all the students have stood in the line. This is nothing but Insertion sort. You will take a number and try to find the position of this number in the already sorted list of number. Once you found the position you insert that number to that position in the sorted list of number.

My initial code was like this:

//Take each number and place it in correct position

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

{

int nKey = arNumbers[i];

int nPos = i;

//Find the position of the new number to be placed

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

{

if (arNumbers[j] > nKey)

{

nPos = j;

break;

}

}

if (nPos != i)

{

//Move all the numbers to the right to make the position for new number

for (int k = i - 1; k > nPos; k--)

{

arNumbers[k + 1] = arNumbers[k];

}

arNumbers[nPos] = nKey;

}

}

The above program works fine. But just that I have one extra for loop. I have one FOR loop for finding position to insert key element and one FOR loop to insert the key in the found position. But rather these two loops can be merged into to single loop and we can do both tasks together. Now below code is based on the book and in that loop is merged.

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

{

int nKey = arNumbers[i];

int j = i - 1;

while (j >= 0)

{

if (arNumbers[j] > nKey)

{

arNumbers[j + 1] = arNumbers[j];

}

else

{

break;

}

j--;

}

arNumbers[j + 1] = nKey;

}

The worst case of the algorithm arises when the array is sorted in the opposite direction. The order of growth for Insertion sort algorithm is  THETA(n^2). I will not go in detail of the proof for this. You can see that there is a loop inside a loop. First loop has to iterate n times. Inside loop also has to iterate n times. Thats why its n*n = n^2..

Code is present at location https://github.com/harsha-kadekar/LibraryOfAlgorithms.git . 

CCRevEngCC

Initially after my training I had renewed interest in learning assembly language and try to develop a dissassembler. This is way back in 2011 or 2012. Sadly still disassembler development is going on. I started development of the dissassembler but abandoned it. But few months back I have again taken it up but with new design. So in those days we 3 of us - Me, Srivatsa, Shishir had created this google site. In this all the things we learnt about assembly language, and trails for developing assembly language are put up there. 

https://sites.google.com/site/ccrevengcc/

It has very useful resources.

And yeah you can see only Shishir was successful in creating disassembler. Hopefully I will do it as soon as possible.

List Files and Folders in Command Line interface

I was reading about File Systems in an Operating Systems book and suddenly thought of writing a tool which will list me all the files and folders of an OS. I had tried something similar to this previously with a GUI without much success. It is listed in my blog as List Files and Folders.

Well that previous attempt did helped me in getting an idea how not to start the development. First lesson learnt dont try to complete the design. First develop the basic and most simple stuff and then start adding on to it.

With this approach first thing I decided was I will not bother about GUI, rather it will be on Command Line interface. As a first iteration I will just list all the files and folders and their corresponding size. Later I added paths to this like absolute path, parent folder. Then show whether it is a file or a folder. Also try to show few attributes like is it hidden, is it readonly or is it system specific File/Folder. Once this is working fine, I latter added few other attributes like alternate name of the file/folder, creation time, last access time and last write time. This is display all this in a tab separated csv format.

Programming Aspect:

To represent a file or folder I have following structure -
typedef struct structFileFolder
{
WCHAR* strFileFolderName;
__int64 Size;
WCHAR* strAbsolutePath;
WCHAR* strParent;
WCHAR* strAlternameName;
SYSTEMTIME* sysTimeCreation;
SYSTEMTIME* sysTimeLastAccess;
SYSTEMTIME* sysTimeLastWrite;
DWORD dwAttributes;
bool isFolder;
bool isReadonly;
bool isHidden;
bool isSystem;
bool isEncrypted;
bool isCompressed;
bool isArchived;
}FileFolderInfo;

I have 3 main functions - 

extern "C" __declspec(dllexport) int ListFiles(char* strOption);
int ListFilesinPath(WCHAR* strPath, WCHAR* strParentPath);
int ListFilesOfDirectory(FileFolderInfo* folderInfo);

As you can see ListFiles function is exposed to outside world. This is the entry point for the file listing. strOption can be 3 things - ALL, a folder path, a file.
ALL means it will loop through all drives and list corresponding files and folders.
If it is not ALL it will check if it is a file or a folder. based on that it will take action.
It will actually call ListFilesinPath function. This intern will call ListFilesOfDirectory recursively to list all the files and folders. For iterating through the files I am using FindFirstFile, FindNextFile and FindFileData of Win32 API.

For creation time, last access time and write time, FindFileData has it in FILETIME structure. So I am converting to SYSTEMTIME when storing it in my FileFolderInfo structure. But when I am displaying I am converting it to a string format of type dd-MM-yyyy hh:mm:ss.

Also all the file attributes like isFolder, isReadOnly, isHidden, isSystem, isEncrypted, isCompressed, isArchived are derived from dwAttributes only.

To dynamically allocate memory and initialize FileFolder Info I have following function.
FileFolderInfo* GetFolderFileInfo();

Similarly to deallocate the memory for the same structure, I have following function
int CleanUpFolderFileInfo(FileFolderInfo* folderInfo);

For folders FindFileData does not provide you size. So we have to iterate through all the contents of the folder and add the size of each of these contents to get the size of the folder.

Following things are displayed about the file - it is similar to what structure is storing
File/Folder Name
Absolute Path of File/Folder
Parent Folder
Alternate Name of File/Folder
Is it a File of Folder
Is it Read Only
Is it Hidden
Is it System specific File/Folder
Is it Compressed
Is it Encrypted
Is it Archived
File/Folder Creation time
File/Folder Last access time
File/Folder Last Write time
File/Folder Attribute double word.

So code is present in the following github location -
https://github.com/harsha-kadekar/Disassembler.git

Actual code is present in two files - SystemStatistics.h and SystemStatistics.cpp of the project ProcessDissector.

These files will be later updated about other system statistics functions like listing process, services etc.

PE File of windows

PE file or Portable Executable File is a format of executables, dll and object files. In a high level this is a mixture of different structures. Each structure having specific information of that file. Also these structures will have information about where to look next for further information.

Some of the tutorials and articles which will explain about these PE files are

https://msdn.microsoft.com/en-us/magazine/ms809762.aspx

https://msdn.microsoft.com/en-us/magazine/bb985992.aspx

https://msdn.microsoft.com/en-us/magazine/cc301808.aspx

Iczelion's tutorial

I am trying to develop a disassembler and one of the model tool for disassembler is DumpBin. Among the different options there is an option called /ALL like DumpBin c:\testPE.exe /ALL 

This will go through the PE file read all the structures of that PE file and display the relevant information for you. I decided to write dll which will do the similar function. Anyways that would help me disassembler also like export functions, picking the code sections etc. While developing this tool learned a lot about PE file structures. I will go through it one by one. Before that I just prepared a high level image of the PE File hope it might help you to understand it

First thing to do is read the file, create the file mapping and obtain the view of that mapped file. This gives you the memory location of first structure of PE file - IMAGE_DOS_HEADER. This is nothing but MS-DOS stub. There are two important members of this structure. First one is e_magic. It should have value as IMAGE_DOS_SIGNATURE which is "MZ". Second one is e_lfanew. This is the offset, if you add this offset to the base image address you will get the address where IMAGE_NT_HEADERS is located. This image nt header is a collection of two headers (file header and optional header) and characteristics. Characteristic should have value IMAGE_NT_SIGNATURE that is "PE\0\0". File header has information like on which machine architecture this PE file will execute, whether this PE file is an executable or a dll, how many sections are present in this PE file, certain characteristics of the PE file like symbols is stripped or not like that. Optional Header has information like whether this is a 32bit or 64 bit application, what type of subsystem it needs like GUI or command line, then dll characteristics like can be relocated at run time, stack size, heap size, code size, then Data Directory array. There are 16 entries in the Data Directory array. Each one gives you two information - relative virtual address [RVA] of the directory location and size of the directory. Directories like export directory, import directory, resource directory, debug directory, etc. If you go to export directory you can find the information regarding functions which are exported by this PE file. similarly if you go to import directory you can find information related to all those functions which are imported by this PE file.

After NT Headers you will get IMAGE_SECTION_HEADERs. In the File Header it gives the information of number of section. Those many IMAGE_SECTION_HEADER structure will follow. Code section, initialized data section, uninitialized data section - these are the few sections. Each section header has information like name of section, virtual size, virtual address , size of raw data and pointer to raw data. Also each sections characteristics like whether it can be executed, or read or written to or even removed if not necessary are present in the Section Header.

Suppose I want to read the contents of that section from the PE File then do the following 3 steps
1. Open the file
2. In the Section header there is a field - PointerToRawData. Move your file pointer to the location which is pointed to by that field.
3. Read all the values upto the length mentioned by "SizeOfRawData" field present in Section header.

 Finding export function details -
0th element of the Data Directory will give you information regarding location and size of Export table. It gives a RVA and this needs to be converted to an offset with respect to base image. The offset is pointing to IMAGE_EXPORT_DIRECTORY which has information like module name, number of functions, address of functions, address of names, address of Name ordinals. Address of function is an RVA which is pointing to array of RVAs of function addresses. Address of Names is an RVA which is pointing to array of strings. Address of Name ordinals is an RVA which is pointing to array of words. Suppose I want to find a particular exported function abc then I will go through the array of strings of AddressOfNames. Let us assume that I found the function at index I in AddressOfNames. Using the same index pick the value present in AddressOfNameOrdinals array. This value will form the index for AddressOfFunctions.

Finding import Function details -
2nd element in the Data Directory [index is 1] will give you information about where to find Import Table.  This offset will point to array of IMAGE_IMPORT_DESCRIPTOR. One for each dll/PE file from which functions have been imported. Last element of the array is an empty image_import_descriptor. So to find how many dlls from which we have imported count till you find an empty image_import_descriptor. Each Image_import_descriptor has following information like library name, whether forward chaining is enabled or not then address of functions and name of functions. There are two fields both points to same thing initially OriginalFirstThunk and First Thunk both are RVAs which point to array of IMAGE_THUNK_DATA structures. Using the AddressOfData field we can identify whether the function was imported by name or through ordinal.  If IMAGE_ORDINAL_FLAG32 == (AddressOfData & IMAGE_ORDINAL_FLAG32) then it is through ordinal. AddressOfData & 0x7FFFFFFF will give you ordinal number. Else it is through function name. Function field is a RVA which points to IMAGE_IMPORT_BY_NAME structure. This has the name of the function.
Initially both OriginalFirstThunk and FirstThunk field of IMAGE_IMPORT_DESCRIPTOR will be pointing to same IMAGE_THUNK_DATA which intern has function names. As these functions are loaded I guess FirstThunk field afterwards will be having address of functions rather than function names.
IMPORT_TABLE link from First Thunk



SAME IMPORT TABLE link from Original First Thunk



IMPORT Table after PE file loaded (First Thunk) has been replaced.
  







My Code is present in Github - https://github.com/harsha-kadekar/Disassembler.git
In that solution of the dll can be found in folder ProcessDissector

Please note image has been taken from these following links -
http://www.codeproject.com/Articles/14360/Injective-Code-inside-Import-Table  - For import table
https://msdn.microsoft.com/en-IN/library/ms809762.aspx - For export table.