#OK to post homework 
#Zhizhang Deng, 09/22/2020, Assignment 1
1. 
===== CODE BELOW =====
diff(x^3, x);
                                 2
                              3 x 
diff(x^4*log(x)*sin(x), x);
           3                 3           4             
        4 x  ln(x) sin(x) + x  sin(x) + x  ln(x) cos(x)

Pi;
                               Pi
eval(pi);
                               pi
evalf(Pi);
                          3.141592654
(5 + 10) + 5/30;
                               91
                               --
                               6 

int(x^5, x);
                              1  6
                              - x 
                              6   

===== CODE END =====

2. 
F(6) = {(1, 2, 1, 2),
(1, 2, 2, 1),
(1, 1, 1, 1, 1, 1),
(1, 1, 2, 1, 1),
(2, 2, 1, 1),
(2, 2, 2),
(2, 1, 1, 2),
(2, 1, 2, 1),
(1, 1, 1, 1, 2),
(2, 1, 1, 1, 1),
(1, 1, 2, 2),
(1, 2, 1, 1, 1),
(1, 1, 1, 2, 1)}


3. 
(0). the {} set assemble line is responsible for adding that last element 
(1). because it is impossible to walk to -x, -y by walking N or E, thus we define it as illegal by saying it is not possible. Further more, in a case of current point (0, >0) or (0, >0), this empty set stop the recursion from happening indefinitely. 
(2). first part is the same as (1). it take us 0 walk to walk to 0,0 if we are already there. the reason this is not an empty set, instead a single ton set is because it is still a valid point, and we should allow the current recursion to understand that we can start from 0,0 so recursion will still append N, E to our answer 


4. 
===== CODE BELOW =====
F := proc(n) local F1, F2, f1, f2, permuted_f1_item, permuted_f2_item; 
option remember; with(combinat); 
if n <= 0 then 
	RETURN({}); 
end if; 
if n = 1 then 
	RETURN({[1]}); 
end if; 
if n = 2 then 
	RETURN({[2], [1, 1]}); 
end if; 

F1 := F(n - 1); 
F2 := F(n - 2); 

# the idea: 
# we only need to consider to add 1 to F1 to make it equal to n, or add 2 to F2 to make it equal to n
# however, there are many insertion points that we can try to add this 1 or 2 to, so we need to try them all, that's why i used the permute function. After adding them all, the '{}' set will automatically remove the duplicate which will then make our final answer 

RETURN(
	{
		seq(seq([op(permuted_f1_item), 1], permuted_f1_item in permute(f1)), f1 in F1), 
		seq(seq([op(permuted_f2_item), 2], permuted_f2_item in permute(f2)), f2 in F2)
	}
); 
end proc;
===== CODE END =====

5. 
Umm, when I actually starts to think about question 5. I realized maybe I overcomplicated question 4. What I observed by trying multiple F(n) with simpler F function (which i dont permutate, i just insert the 1 or 2 at the end of F1, F2), is that it magically still covers all the cases[like what you did in the N,E walk]). which I am having trouble figuring out intuitively why, i can't prove it yet. but the following procedure is done by assuming that I just need to add 1 or 2 at the end of F1, F2 and it would cover all cases for all n

===== CODE BELOW =====

NuF := proc (n) local F1, F2; 
if n <= 0 then 
	RETURN(0) 
end if; 
if n = 1 then 
	RETURN(1) 
end if; 
if n = 2 then 
	RETURN(2) 
end if; 
F1 := NuF(n-1); 
F2 := NuF(n-2); 

# the idea: assumming that adding 1,2s at the end of F1, F2 would cover all cases (i.e. no need for permutation)

RETURN(F1+F2) 
end proc

===== CODE END =====
NuF(1000) is 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
F(1000) would have problems as it requires much more computation power and memory space to remember all the set along the road. NuF(1000) on the other hand only need to store numbers
In terms of recursion depth both NuF and F(1000) is probably the same, but the way option remembers works is kind of building a hashmap to cache all previous computations which is very very memory intensive as all of the results in F(n) is already a set.