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 →

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 given problem into sub-problems of same type. 2. Conquer: Recursively solve these sub-problems. 3. Combine: Appropriately combine the answers. In merge sort,the input array is divided in two […]

Continue reading →

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 adjacency matrix where each cell A[i][j] represents the weight of the edge from vertex i to vertex j. If i==j,then A[i][j]=0. If there is no edge from […]

Continue reading →

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,19). Then,the sub-array or sub-sequence with maximum sum is (8,-6,21) and the maximum sum is 23. Brute Force- We can check sums of all sequences of different sizes from 1 to N.Its […]

Continue reading →