DS1 FIBONACCI AND PATH

Question 1

FIBONACCI SEQUENCE PROBLEM

Answer 1

f0=0, f1=1, fn=fn-1+fn-2
ways to get fn:
-recursive way:
O(2^n) time complexity, n storage

-1 array and 1 loop:
fib(n){
f[0]=0; f[1]=1;
for(i=2;i<=n;i++){f[i]=f[i-1]+f[i-2];}
return f[n];
}
O(n) time complexity, n storage

-no array 3 variables:
fib(n){
if(n<2){return n;}
int a=0; int b=1; int f;
for(i =2;i<=n;i++){f=a+b; a=b; b=f;}
return f;
}
O(n) time complexity, storage unchanging (3)

Question 2

GRID PATHS

Answer 2

n*n grid
count optimal paths from (0, 0) to (i, j)
from a point to neighboring point there is only 1 optimal path so:
-opt[i][j] = opt[i-1][j] +opt[i][j-1]
number of optimal paths to (i,j) are the sum of optimal paths to neighboring points towards the direction of starting point (hence we do -1)
if we call this recursively until one of the coords becomes zero we have that (0, 0) to (a, 0) or (0, b) has only one optimal path (straight line)
code:
opt(grid n, point (i,j)){
//(x, 0)
for(int i = 0;i<n;i++)
{p[i][0] = 1}
//same for j for case (0, x)
for(int i =1;i<n;i++)
{for int j=1;j<n;j++)
{p[i][j] = p[i-1][j] + p[i][j-1];} //loop calculates them and we can make it stop at desired coords
}
}
probably O(n^2 time complexity)

Question 3

SEARCH EXAMPLE

Answer 3

unsorted list: O(n)
sorted list: O(logn)
search engines are one of the most important applications of data structures
time sensitive and relevance sensitive