# Subset Sum Problem (Part II)

Given a set of numbers,our task is to find the number of subsets that sum to a particular value. Example- Set of numbers- {1,3,2,5,4,9} Sum=9 Subsets that sum to 9- {1,3,5} {5,4} {9} {3,2,4} Thus,number of subsets that sum to 9 = 4. Algorithm- The idea is to find the number of possible sums with […]

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

A doubly linked list is a linked linear data structure,each node of which has one or more data fields but only two link fields known as left link (LLINK) and right link (RLINK).The LLINK field of a given node points to the node on its left and RLINK field of a given node points to […]

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

# Path Finding

Given an undirected,unweighted graph and two vertices u and v,the task is to find the path between these two vertices.u can be considered as the source vertex and v as the destination vertex. Example- Number of vertices-5 Number of edges-4 Given vertices are 2 and 4. Edges- 1 2 1 3 3 4 4 5 […]

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