User:Ahalya96/sandbox

Algorithm Templates :

Fibonacci:

a. Problem

Compute the nth Fibonacci number

b. Subproblem

${\textstyle {\begin{array}{lcl}F[i]=i^{th}{Fibonaccinumber}\\ComputeF[n]\\\end{array}}}$

c. Recurrence

$F_{n}=f(n)={\begin{cases}0,&{\text{if }}n=0{\text{,}}\\1,&{\text{if }}n=1{\text{,}}\\F_{n-1}+F_{n-2},&{\text{if }}n\geq 2.\end{cases}}$

Tiling Problem :

a. Problem

Given a board that is of dimensions 2 x n , find how many ways it can be tiled using 2 x 1 tiles.

b. Sub Problem

Count(n) = number of ways to tile a 2 x n board

Compute Count(n)

c. Recurrence

Failed to parse (unknown function "\begin{cases}"): {\displaystyle Count[n]=\begin{cases} n & \text{if n = 1 or 2} \\ C(n - 1) + C(n - 2) & \text{if $n > 2$}\\ \end{cases}}

d. Algorithm

numOfWays(n , hmap){

if (n in hmap)

return hmap[n]

else

hmap[n] = numOfWays(n - 1 , hmap) + numOfWays(n - 2, hmap)

return hmap[n]

}

e. Complexity

If the algorithm is written using dp the time complexity is O(n)

Permutation Coefficient :

a. Problem

Compute the nth Fibonacci number

b. Subproblem

${\textstyle {\begin{array}{lcl}F[i]=i^{th}{Fibonaccinumber}\\ComputeF[n]\\\end{array}}}$

c. Recurrence

$F_{n}=f(n)={\begin{cases}0,&{\text{if }}n=0{\text{,}}\\1,&{\text{if }}n=1{\text{,}}\\F_{n-1}+F_{n-2},&{\text{if }}n\geq 2.\end{cases}}$