Algorithms

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

Solving 0/1 Knapsack problem using Dynamic Programming

Introduction A knapsack is a bag with straps, usually carried by soldiers to help them take their valuables or things which they might need during their journey. The 0/1 knapsack problem is a very famous interview problem. The problem statement is as follows: Given a set of items, each of which is associated with some weight and value. Find the subset of items which can be carried into the knapsack with weight limit W. It is required that the cumulative value of the items in the knapsack is maximum value possible. In simple words, it asks you to pick certain items from the set of items ...
Read More

Solving 0/1 Knapsack problem using Recursion

Introduction A knapsack is a bag with straps, usually carried by soldiers to help them take their valuables or things which they might need during their journey. The 0/1 knapsack problem is a very famous interview problem. The problem statement is as follows: Given a set of items, each of which is associated with some weight and value. Find the subset of items which can be carried in a knapsack of capacity W (where W is the weight). It is required that the cumulative value of the items in the knapsack is maximum value possible. In simple words, it asks you to pick certain items from the...
Read More

Find Interleaving Strings using Dynamic Programming

Introduction This problem is already discussed in the post here. This post attempts to solve the same using the dynamic programming approach. Here is a brief description of the problem. Given three strings A, B and C such that A is "ab", B is "ade" and C is "adabe" find if C is an interleaving of A and B or not. Interleaving means constructing the third string C using the characters of A and B such that the characters in A and B preserve their relative ordering in C. In the above example C is an interleaving of A and B. Approach to Find Interleaving Strings using Dynamic Programming How ...
Read More

Solving Sudoku using Backtracking

Introduction This post is the continuation of the backtracking series. Sudoku can be solved using multiple algorithms based on Neural Networks and Genetic Algorithms by doing exhaustive searches in the solution space. However, here we are focusing on solving Sudoku using backtracking algorithm. For people who are unaware of the Sudoku puzzle, please check out Wikipedia for details. For a brief description read below: A Sudoku puzzle is a 9 * 9 grid. Few cells in the grid contain random numbers between 1 and 9 (both inclusive) A fully solved Sudoku must contain numbers through 1-...
Read More

Print all paths of robot through the grid

Introduction This is a supplement to the previous post where we were interested in just one path of a robot from top left corner to the bottom right corner. In this post we will print all paths of robot moving through a given grid containing few blocked cells. The algorithm for this solution remains the same, we just need few tricks to get that right. Here, I will explain the idea behind printing all paths of robot through the grid. Approach Here, let us discuss what different we need to do to print all the paths. As we can recall from the previous post, the moment we reached the destina...
Read More