Algorithms

This category contains all the posts related to Algorithms. For e.g.: Sorting, Hashing, Searching, Tree Traversals, Graph Theory etc.

Understanding Binary Search Algorithm

Introduction The problem of searching is very trivial. It goes like this: There is an array of elements A[1..N] and we need to find the index of a given element in the array. In case the element is not present in the array, we can choose to return a specific value (say -1) which suggests that the element doesn't exist in the array. Binary Search is a very efficient and interesting searching algorithm. Regular searching algorithms take running time proportional to the size of the input. They are called linear time algorithm O(N) to be asymptotically true. Binary Search on the other ha...

Understanding Heap Sort

[nextpage title="Introduction"] Heap Sort is one of the efficient sorting algorithms with a guaranteed worst case running time of O(NlogN). This is an in place sorting algorithm but it does not offer stable sorting. In place Sorting: A sorting algorithm which sorts the input using very small or no extra space. It means that the input data is overwritten by the resulting output data. Stable Sorting: A stable sorting algorithm is one, in which the relative order of equal keys is preserved. It means if there are non unique keys in the input data, then their relative order of occurrence in ...

Dynamic Programming – CrazyNumbers

Problem Statement We are interested in finding the count of all N digit crazy numbers. Let us define a crazy number. A crazy number is a number where the magnitude of its consecutive digits differ by 1. For e.g.: Here is a list of all 2 digit crazy numbers: The total number of 2 digit crazy numbers is 17. You can notice that in all the numbers the digits differ only by 1. Similarly for three digit numbers the count reaches 32. For four digit numbers it becomes 61 and very soon it increases exponentially to 924903595810 for a 40 digit number. It might look like the a problem wh...

Huffman Decoding

Introduction Huffman coding is an encoding mechanism by which a variable length code word is assigned to each fixed length input character that is purely based on their frequency of occurrence of the character in the text to be encoded. It is common to assign shorter codes to more frequent characters and the less frequent characters are assigned longer code words. A code word is a binary string (a sequence of zeroes and ones). A Huffman tree is made for an input string and characters are decoded based on their position in the tree. The decoding process is as follows: We start from t...

Closest Pair Points

Introduction A very interesting problem, indeed. I presume, not a complex one either. Here is what the problem statement looks like. "Given a set of N points in a plane, find the closest pair points". A question which is always asked in interviews in various forms, here we will not just look at the solution but will also understand the intuition behind the solution. In the adjoining image, we have five points (A, B, C, D, E) in the plane. As a result of the solution we need to return one pair which has the smallest distance between them. Of course there can be multiple such pairs, we a...