Subset Sum Problem

Given a set of positive integers and a value sum,the task is to find if there is a subset with sum equal to the given value. Example- Given set of numbers- {3,34,4,12,5,2} Sum=9. The output will be ‘True’ because 4+5=9. Algorithm- The problem can be divided into two sub-problems- 1.By including the last element. 2.By […]

Continue reading →

All Permutations

Given a string,the task is to print all the permutations of the string. A permutation is a rearrangement of the elements of an ordered list S.A string of length N has N! permutations. Example- Let the string be S=”abc”. Length of the string=3 Number of permutations=3!=6 Permutations- abc acb bac bca cab cba Algorithm- Basic […]

Continue reading →

Applications of DFS

One of the applications of DFS is to find the number of connected components in a graph.In graph theory, a connected component of an undirected graph is a sub-graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the super-graph. Algorithm- A depth […]

Continue reading →

Longest Common Subsequence

Given two sequences,the task is to find the length of longest sub-sequence present in both of them. A sub-sequence is a sequence that appears in the same relative order, but not necessarily contiguous.For example- “abc”,”fit”,”abfi”,etc are sub-sequences of “abcfit”.A string of length n has 2^n different possible sub-sequences. Example- String 1- “BATTING” Length-7 String 2- […]

Continue reading →

Activity Selection Problem

Activity selection problem is an example of greedy algorithm.Greedy algorithms look for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step will provide the most obvious benefit.The advantage of using a greedy algorithm is that solutions to smaller sub-problems of the problem can be straightforward and easy to understand.The disadvantage is that […]

Continue reading →

Dijkstra’s Algorithm

Given a network of cities and the distances between them,the task is to find the shortest path from a city(source) to all other cities connected to it.The network of cities with their distances is represented as a weighted digraph.It is also known as single-source,shortest path problem. Algorithm- N is the number of vertices labeled {0,1,2,3….N-1} […]

Continue reading →

Minimum Cost Path (DP Example)

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems and optimal substructure.When applicable,the method takes far less time than naive methods that don’t take advantage of the sub-problem overlap. A problem is said to have overlapping sub-problems […]

Continue reading →

Magic Square

A magic square is an arrangement of numbers in a square grid, where the numbers in each row, and in each column, and the numbers in the forward and backward main diagonals, all add up to the same number.A magic square of order N means it has N rows and N columns.It contains all integers […]

Continue reading →

Largest multiple of 3

Given an array of digits,the task is to find the largest multiple of 3 that can be formed from array elements. Example- Input array is {4,8,0}.Then,the largest number formed using these digits and divisible by 3 is 840. Properties of multiples of 3- 1.Sum of the digits of the multiple is divisible by 3. Example- […]

Continue reading →