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 →

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 trees that may be extracted from it.A spanning tree has N vertices and N-1 edges.This is because of the property of trees.A minimum cost spanning tree is a […]

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 →

Fibonacci Numbers

Fibonacci is the most famous sequence in the programming world. It is defined by the following recursive formulation: f(n)=f(n-1) + f(n-2) where f(0)=0 & f(1)=1. The first few numbers of the sequence are: 0,1,1,2,3,5,8,13,21,34,55…… Program to find the N-Th Fibonacci number can be implemented iteratively or recursively very easily.But,for large values of N,we need an […]

Continue reading →

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 First Traversal- It traverses the successors of the start node,generation after generation in a horizontal or linear fashion. Algorithm- BFT(s) { //s is the start vertex of the traversal […]

Continue reading →

All about Factorial(!)

In mathematics,the factorial of any positive number N is the product of the positive integers less than or equal to N.It is denoted by ‘N!’. Example- 5!= 5*4*3*2*1 =120 Also,0!=1. In C/C++,no data type can store the value of factorial of a number greater than 20.To find the factorial of greater numbers easily,JAVA/Python can be […]

Continue reading →

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 expansion of (1+x)^n.It also represents an entry in Pascals Triangle. Properties- 1. nCk=(n!)/[(k!)*(n-k)!] 2. nCn=1 3. nC0=1 4. nCk=(n-1)C(k)+(n-1)C(k-1) 5. nCk=(n)C(n-k) The task is to find the value […]

Continue reading →