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 →

Linked Lists

Linked list is one of the fundamental,simplest and most common data structures in C programming language.A linked list is a data structure consisting of a group of nodes which together represent a sequence.Each node comprises of data and a link to the next node in the sequence. Advantages of Linked List over an array- 1.Linked […]

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 →

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

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 →