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