User:Ahalya96/sandbox
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]