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...
Read More

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 ...
Read More

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...
Read More

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...
Read More

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...
Read More

Tries for Text Processing

Introduction Now that we have talked so much about efficient ways of pattern finding using Boyer Moore and KMP algorithm. Let us try and understand other aspects of Text Processing as well. This post will mostly focus on using tries for text processing, storing text efficiently and also discuss about data structures which may make more sense when we talk about storage and retrieval of text based on some given criteria. Here are some real world problems which often demand quicker answers: Ever wondered why you are able to search a word in a dictionary so fast? How do you think one w...
Read More

Pattern Finding – KMP Algorithm

Introduction Now that you are fully equipped with the Boyer Moore Algorithm and have a notion of Pattern Finding. I would suggest you to get deeper into pattern finding. You can read about the benefits of pattern finding in my previous post about Boyer Moore. This post will try to make you familiar with all the thought processes which you can use to exploit the known properties of texts and patterns using KMP Algorithm. However, Boyer Moore seems to be slightly intuitive, this one is a real geeky way of finding patterns. Knuth Morris Pratt Yes! this is what KMP stands for, you can learn ...
Read More