Jump to content

User:Ahalya96/sandbox

From Wikipedia, the free encyclopedia

Algorithm Templates :

[edit]

Fibonacci:

[edit]

a. Problem

[edit]

Compute the nth Fibonacci number

b. Subproblem

[edit]

c. Recurrence

[edit]

d. Dependency

[edit]

e. Algorithm

[edit]

f. Complexity

[edit]

Tiling Problem :

[edit]

a. Problem

[edit]

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

[edit]

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

Compute Count(n)

c. Recurrence

[edit]

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

[edit]

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

[edit]

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


Permutation Coefficient :

[edit]

a. Problem

[edit]

Compute the nth Fibonacci number

b. Subproblem

[edit]

c. Recurrence

[edit]

d. Dependency

[edit]

e. Algorithm

[edit]

f. Complexity

[edit]