# 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 […]

# 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 […]

# Longest path in a tree

Given an unweighted and undirected tree,the task is to find the length of the longest path (from one node to another) in that tree.The length of a path in this case is number of edges we traverse from source to destination. Example- Number of nodes=3 Number of edges=2 Edges- 1 2 2 3 Output- 2 […]

# 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 […]

# 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- […]

# 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 […]

# 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} […]

# 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 […]