Prims Algorithm
Let G=(V,E) be an undirected,connected and weighted graph.A sub-graph T=(V,E’) of G is a spanning tree of G if T is a tree.There may be several spanning t...
Tag: algorithm
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 mai...
BFS & DFS
A traversal is a systematic walk which visits the nodes of the graph in a specific order. Two Types:- 1.Breadth First Traversal 2.Depth First Traversal Breadth ...
Binomial Coefficient
Binomial Coefficient is represented by nCk which means number of ways of choosing k objects from n objects.It is the coefficient of x^k term in the polynomial e...
Longest Increasing Sub-sequence
Given a sequence of numbers,we need to find the longest increasing sub-sequence from the given input(not necessary continuous). Example- Input- 1 10 4 5 3 2 9 1...
N Queens Problem (Backtracking)
Given a chess board of size n*n,the task is to find all the ways to place n queens so that they don’t attack each other. In chess, a queen can move as far...
Sieve of Eratosthenes
The task is to find all the primes between 1 to N.Numbers are called prime if they do not have any factors other than 1 and the number itself. Brute Force- Each...
Merge Sort
Merge Sort is an example of a divide and conquer algorithm. A Divide and Conquer algorithm solves a problem using following three steps- 1. Divide: Break the gi...
Floyd Warshall Algorithm
The problem is to find shortest distances between every pair of vertices in a given edge weighted directed graph. The graph is represented in the form of an adj...
Largest Sum Contiguous Subarray
We have a sequence of integers and we need the maximum sum from the continuous sub-sequences. Example- Let the sequence of integers be (3,-4,5,-7,8,-6,21,-14,-9...