#OK to post homework
#William Wang, 9/5/2020, Assignment 1

#1
#Print out (into a .txt file, by copying and pasting) some random lines, e.g. diff (x^3, x)

diff(x^3, x);
                                 2
                              3 x 

int(3*x^2, x);
                                3
                               x 


#2 
#Human Problem: Let F(n) be the set of lists using {1,2} that add up to n. For example, F(0) = {[]}, F(1) = {[1]}, F(2) = {[1,1,1],[1,2],[2,1]}. Write down F(6).

#F(6) = {[1,1,1,1,1,1],[2,1,1,1,1],[1,2,1,1,1],[1,1,2,1,1],[1,1,1,2,1],[1,1,1,1,2],[2,2,1,1],[2,1,2,1],[2,1,1,2],[1,1,2,2],[1,2,1,2],[1,2,2,1]}

#3
#a. What Maple line converts L1: [Mercury, Venus, Earth] to L2: [Mercury, Venus, Earth, Mars]?

L1 := [Mercury, Venus, Earth]
                 L1 := [Mercury, Venus, Earth]

L2 := [op(L1), Mars]  
              L2 := [Mercury, Venus, Earth, Mars]


#The list L2 is defined to be the list containing all the elements in L1 extracted using the op() command, along with the element 'Mars'.

#b. Why do we initialize WALKS(m,n) with either m or n or both negative to be the empty set?
#c. Why do we initialize WALKS(0,0) to be the singleton set{[]}?

#WALKS(m,n) with a negative m, negative n, or both negative is initialized to be the empty set, because there is no way to reach a point (m,n) with a negative m or negative n when the only steps allowed are in positive directions. WALKS(0,0) is initialized to be the set {[]} because there is one way to get from (0,0) to (0,0), which is to do nothing. These two initializations also serve another purpose, which is to serve as the base cases of WALKS function. Looking closely at the code, it is apparent that the WALKS function is a recursive function, and thus needs base cases to prevent the function form making more recursive calls when it is no longer appropriate to do so.

#4
#Write a Maple procedure F(n) that inputs a non-negative integer n and outputs the set of lists in {1,2} that add up to n. Compare the output of F(6) to the one that you found above by hand.

#F(n) takes a non-negative integer n and outputs the set of all distinct ways to take either 1 or 2 steps to get to the nth step

F:=proc(n) local W1,W2,w1,w2:
option remember:

if n<0 then
 RETURN({}):
fi:

if n=0 then
 RETURN({[]}):
fi:

W1:=F(n-1):
W2:=F(n-2):

{seq([op(w1),1],w1 in W1), seq([op(w2),2],w2 in W2)  }:

end:

F(6)
 {[2, 2, 2], [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], 

   [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1], [1, 1, 1, 1, 2], 

   [1, 1, 1, 2, 1], [1, 1, 2, 1, 1], [1, 2, 1, 1, 1], 

   [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]}

#The same as the one found by hand


#5
#Write a Maple procedure NuF(n) that inputs a non-negative integer n and outputs the number of lists in {1,2} that add up to n. Make sure that nops(F(n))=NuF(n) for n=1..10. What is NuF(1000)? Why would Maple complain if you tried to do nops(F(1000))?

NuF:=proc(n) local W1,W2,w1,w2:
option remember:

if n<0 then
 RETURN(0):
fi:

if n=0 then
 RETURN(1):
fi:

W1:=NuF(n-1):
W2:=NuF(n-2):

W1+W2:
end:

NuF(6)
                               13

evalb(seq(NuF(n), n=1..10)=seq(nops(F(n)), n=1..10))
                              true

NuF(1000)
7033036771142281582183525487718354977018126983635873274260490508\

  71545371181969335797422494945626117334877504492417659910881863\

  63265450223647106012053374121273867339111198139373125598767690\

  091902245245323403501


#Also equivalent:
fibonacci(1001)
7033036771142281582183525487718354977018126983635873274260490508\

  71545371181969335797422494945626117334877504492417659910881863\

  63265450223647106012053374121273867339111198139373125598767690\

  091902245245323403501


#Maple will complain if you try to do nops(F(1000)) because nops(F(n)) counts the number of operands in F(n), and for large values of n like n=1000, Maple needs to figure out what all of those lists are, then count them individually.