Algorithms

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

Pattern Finding – Boyer Moore

Introduction String matching problems are important part of many Programming Contests and also find applications in real world problems. Imagine you are asked to implement a text editor. What are few of the most common operations in a text editor? Copy and Paste. Search and Replace. The performance of your text editor will completely depend on how efficiently it can search and/or replace patterns in a huge text. Basics of Pattern Finding In a given pattern matching problem, we have two strings one is called the text T and the other is called the pattern P. The task is to find th...
Read More

Solving Recurrences – Master Method

Introduction This post is to be read in continuation to the Divide and Conquer methodology for e.g. the Merge Sort problem. This post is an extension over the problem of solving recurrences or recurrence equations. There are several ways of solving recurrences namely Substitution Method, Master Method and Recurrence Tree method. The most confusing one or may I say relatively complex one is the Master Theorem. Here we will discuss the same. Master Theorem What does it solve? Not all the recurrences can be solved using the Master Theorem, but it still solves a large family of recurrences....
Read More

Dynamic Programming – Longest Palindromic Sequence

[nextpage title="Introduction"] Palindromes are fascinating character sequences in a string. A palindrome is a string which reads the same when read from either of the ends. This post in particular talks about palindromic sub sequences. To know more about a sub sequence, please check my post on Longest Common Sub sequence. A palindromic sequence means a sequence of characters which is a palindrome. Now, we must understand it clearly that we are talking about a sub sequence and not a substring. Understanding the Longest Palindromic Subsequence problem better It is really easy to say if...
Read More

Interleaving Strings

Problem Statement This is a question from one of the interview experiences. The statement, "Given three strings A, B and C find if C is an interleaving of A and B." Interleaving is defined as below: A string C is said to be an interleaving of two strings A and B if C contains a sub sequence of A and B such that the relative order of characters in A and in B are preserved in C. For e.g. : A - ABCD B - BACDX C - ABACDXBCD The Idea - Interleaving Strings Here I am not giving any solution which is less than O(M*N) solution where M is the length of the shortest string among A and B...
Read More

Minimum Spanning Tree Prim’s Algorithm

Introduction What is the minimum length of the network cable we require if we have to connect 100 computing machines in a building distributed across multiple floors? How do I guarantee that there can be no other minimum length possible than what I derive? Why is it even important to find the minimum length? The history of the problem You can read the classic problem solved by MST Applications of Minimum Spanning Tree Defining Spanning Trees A spanning tree is always defined for a weighted Graph G(V,E) where the weights are positive. This means that all the edges carry some positive we...
Read More

Shortest Path using Dijkstra’s Algorithm

Introduction This is the third post in the Graph Traversals – Online Classes. After learning how to move through a graph, we might be interested in learning more. One interesting problem is determining the shortest path between two vertices of a graph. The problem can be extended and defined in many other forms. I prefer to call it "minimizing the cost". For e.g. When we measure the cost in terms of the distances between vertices, it can be called as the Shortest Path. When we measure the cost in terms of the money spent between vertices, it can be called as the Cheapest Path. Whe...
Read More

Depth First Traversal

Introduction This is the second post in the Graph Traversals – Online Classes. I Recommend you to look at the first post Breadth First Traversal as it contains more explanation and details and I will keep this post smaller just around the depth first concept. Depth First Traversal The Idea In this traversal, we choose a start vertex and keep moving forward along the length of the graph until there is no undiscovered vertex in that path. Once reaching a dead end, we back track to all the visited vertices and check if we have any vertex which has an adjacent undiscovered vertex. We kee...
Read More