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

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

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

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

# 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 11 13 Increasing Sub-sequences- 1 4 5 5 9 11 13 10 11 13 4 5 9,etc Longest Increasing Sub-sequence– 1 4 5 9 11 13 Length of […]

# 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 as she pleases, horizontally, vertically, or diagonally. Naive Algorithm- Backtracking Algorithm- If queens are at (i,j) and (k,l) coordinates,then they can attack […]

# 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 number from 1 to N is checked if it is prime or not. To check if a number is prime or not,check its […]

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