Home Technology Writing Download About Misc Contact

Algorithms


Selected software applications that showcase data structures, algorithms, and theoretical computer science work.
To see more of my work in this field, plese drop me a line.

Heap Sort


Although heap sort algorithm is slowest among the O(n log n) algorithms, it is of interest in systems involving large (very very large) data sets. Heap sort does not require extra memory storage. It operates on the same memory buffer and does in-place sorting. Heap sort can be implemented without massive recursion.

Heap sort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.
Source code for this application is available upon request. Binaries can be downloaded here.

Huffman Encoding using Binary Tree


Binary trees are extremely useful in generating Huffman codes for alphanumeric text. Huffman coding is based upon basic principle that frequency of occurance of various alphabets is different in conext of large English language text. For example, letters 't' and 'e' occur highest number of times.
So when we allocate binary codes we shall give least length code to those. Let's say that 't' gets 0 and 'e' gets 1. Now other letters follow up. 'r' has a code of 01. Left branch is designated 0 and right branch is designated 1.

Code for a Letter = string of (0,1) in exact traversal order from Root to that letter

My application builds binary tree an encoding stored on disk. And accepts input string from user to output Huffman encoding. For example, string "Huffman" is encoded "1010010001100000111000011100001011001110001101". Huffman is a variable length code so each letter gets different number of 0s and 1s.
Source code for this application is available upon request. Binaries can be downloaded here.

Tree Visualization


One of my favorite - Trees are a versatile data structures - from directories to index-based searching, and from BOM to organization charts - wherever hierarchical information needs to processed, Trees come into picture. This application addresses 2 ways of visualizing such hierarchies.
My application builds n-way tree internally as of now - which can be built from an input stream or based upon some APIs. Both algorithms are recursive and traverse trees in pre-oder, in-order, and post-order to perform various decision making. Source code for this application is available upon request. Binaries can be downloaded here.


Compare N-way Trees


Comparing two hierarchies is a generic problem required to be solved in source code control systems, CAD systems, BOM comparisons, system management and several other applications.
My application uses n-way general trees with strings as primary sorting keys. The algorithm starts with roots, and moves ahead figuring out what is missing in each tree. It also inserts place-holders for missing objects in corresponding hierarchies. Source code for this application is available upon request. Binaries can be downloaded here.